Completion of ZFC

I attended a talk given by W. Hugh Woodin regarding the Ultimate L axiom and I wanted to verify my current understanding of what the search for this axiom means. I find it to be a fascinating topic but the details are so far beyond my grasp.

Given the language of set theory, one can write down a multitude of first-order sentences. By Godel's Incompleteness Theorem, it is known that from the ZFC axioms one can only derive the truth-values of a (small) fragment of these sentences.

In the past, it was hoped (by Godel, among others) that the Large Cardinal Axiom hierarchy would provide an infinite ladder of axioms of increasing strength such that any first-order sentence in the language of set theory would be either provable or refutable from ZFC + LCA for some suitable LCA.

However, it is now known (?) that the LCA hierarchy (pictorially represented as the vertical spine of the set-theoretic universe V) is not enough to settle all such questions. In particular, there is an additional horizontal "degree of freedom" due to Cohen forcing: for instance, when it comes to CH, it is known (or merely believed?) that both CH and ~CH are consistent with the LCA hierarchy.

Now, let a "completion of ZFC" be an assignment of truth-values to every first-order sentence in the language of set theory, such that a sentence is true whenever ZFC proves that sentence; moreover, for the other sentences (i.e. those which are undecidable in ZFC) the assignment of truth-values must be consistent.

My understanding of Ultimate L is that it picks out a unique completion of ZFC as being the "correct" one; that is, even though Cohen forcing allows us to have models (and therefore completions) of both ZFC + CH and also of ZFC + ~CH, Ultimate L eliminates the horizontal ambiguity and provides us with a unique completion of ZFC in which the truth-values of first-order sentences only depend on the vertical LCA hierarchy.

Is my understanding correct? And how do we know that there are (infinitely) many different completions of ZFC in the first place? Could it be that there is no way to consistently assign truth-values to all first-order sentences, i.e. that no completion exists?

Also, how would we know that Ultimate L + LCA picks out a unique completion (as opposed to a class of completions)? And would it be a valid completion (does consistency of ZFC + Ultimate L follow from Con ZFC)?

I would appreciate answers to any of the above questions, as I can't find anything on this topic in the literature. Thank you!

-

I am not sure which statement you heard as the "Ultimate $L$ axiom," but I will assume it is the following version:

There is a proper class of Woodin cardinals, and for all sentences $\varphi$ that hold in $V$, there is a universally Baire set $A\subseteq{\mathbb R}$ such that, letting $\theta=\Theta^{L(A,{\mathbb R})}$, we have that $HOD^{L(A,{\mathbb R})}\cap V_\theta\models\varphi$.

(At least, this is the version of the axiom that was stated during Woodin's plenary talk at the 2010 ICM, which should be accessible from this link. See also the slides for this talk--Thanks to John Stillwell for the link.)

I do not think you will find much about it in the current literature, but Woodin has written a long manuscript ("Suitable extender models") that should probably provide us with the standard reference once it is published.

As stated, this is really an infinite list of axioms (one for each $\varphi$). The statement is very technical, and it may be a bit difficult to see what its connection is with Woodin's program of searching for nice inner models for supercompactness. (That was the topic of his recent series of talks at Luminy; I wrote notes on them and they can be found here.)

Keeping the discussion at an informal level (which makes what follows not entirely correct), what is going on is the following:

Gödel defined $L$, the constructible universe. It is an inner model of set theory, and it can be analyzed in great detail. In a sense (guided by specific technical results), we feel there is only one model $L$, although of course by the incompleteness theorems we cannot expect to prove all its properties within any particular formal framework. Think of the natural numbers for an analogue: Although no formal theory can prove all their properties, most mathematicians would agree that there is only one "true" set of natural numbers (up to isomorphism). This "completeness" of $L$ is a very desirable feature of a model, but we feel $L$ is too far from the actual universe of sets, in that no significant large cardinals can belong to it.

The inner model program attempts to build $L$-like models that allow the presence of large cardinals and therefore are closer to what we could think of as the "true universe of sets"; again, the goal is to build certain canonical inner models that are unique in a sense (similar to the uniqueness of ${\mathbb N}$ or of $L$), and that (if there are "traces" of large cardinals in the universe $V$) contain large cardinals.

The program has been very successful, but progress is slow. One of the key reasons for this slow development is that the models that are obtained very precisely correspond to specific large cardinals, so that, for example, $L[\mu]$, the canonical $L$-like model for one measurable cardinal, does not allow the existence of even two measurable cardinals ($L$ itself does not even allow one).

Currently, the inner model program reaches far beyond a measurable, but far below a supercompact cardinal. Woodin began an approach with the goal of studying the coarse structure of the inner models for supercompactness. This would be the first step towards the construction of the corresponding $L$-like models. (The second step requires the introduction of so-called fine-structural considerations, and it is traditionally significantly more elaborate than the coarse step.)

The results reported in the talks I linked to above indicate that, if the construction of this model is successful, we will actually have built the "ultimate version of $L$", in that the model we would obtain not only accommodates a supercompact cardinal but, in essence, all large cardinals of the universe.

If we succeed in building such a model, then it makes sense to ask how far it is from the actual universe of sets.

A reasonable position (which Woodin seems to be advocating) is that it makes no sense to distinguish between two theories of sets if each one can interpret the other, because then anything that can be accomplished with one can just as well be accomplished with the other, and differences in presentation would just be linguistic rather than mathematical. One could also argue that of two theories, if one interprets the other but not vice versa, then the "richer" one would be preferable. Of course, one would have to argue for reasons why one would consider the richer theory "true" to begin with. This is a multiverse view of set theory (different in details from other multiverse approaches, such as Hamkins's) and rather different from the traditional view of a distinguished true universe.

Our current understanding of set theory gives us great confidence in the large cardinal hierarchy. $\mathsf{ZFC}$ is incomplete, and so is any theory we can describe. However, there seems to be a linear ordering of strengthenings of $\mathsf{ZFC}$, provided by the large cardinal axioms. Moreover, this is not an arbitrary ordering, but in fact most extensions of $\mathsf{ZFC}$ that have been studied are mutually interpretable with an extension of $\mathsf{ZFC}$ by large cardinals (and those for which this is not known are expected to follow the same pattern, our current ignorance being solely a consequence of the present state of the inner model program).

So, for example, we can begin with the $L$-like model for, say, a Woodin cardinal, and obtain from it a model of a certain fragment of determinacy while, beginning with this amount of determinacy, we can proceed to build the inner model for a Woodin cardinal. Semantically, we are explaining how to pass from a model of one theory to a model of the other. But we can also describe the process as establishing the mutual interpretability of both theories. Of course, if we begin with the $L$-like model for two Woodin cardinals, we can still interpret the other theory just as before, but that theory may not be strong enough to recover the model with two Woodin cardinals.

From this point of view, a reasonable "ultimate theory" of the universe of sets would be obtained if we can describe "ultimate $L$" and provide evidence that any extension of $\mathsf{ZFC}$ attainable by the means we can currently foresee would be interpretable from the theory of "ultimate $L$".

The ultimate $L$ list of axioms is designed to accomplish precisely this result.

Part of the point is that we expect $L$-like models to cohere with one another in a certain sense, so we can order them. We, in fact, expect that this order can be traced to the complexity of certain iteration strategies which, ultimately, can be described by sets of reals. Our current understanding suggests that these sets of reals ought to be universally Baire. Finally, we expect that the models of the form $$HOD^{L(A,{\mathbb R})}\cap V_\theta$$ as above, are $L$-like models, and that these are all the models we need to consider. The fact that when $A=\emptyset$ we indeed obtain an $L$-like model in the presence of large cardinals, is a significant result of Steel, and it can be generalized as far as our current techniques allow.

The $\Omega$-conjecture, formulated by Woodin a few years ago, would be ultimately responsible for the $HOD^{L(A,{\mathbb R})}\cap V_\theta$ models being all the $L$-like models we need. (Though I do not quite see that formally the "ultimate $L$" list of axioms supersedes the $\Omega$-conjecture). Also, if there is a nice $L$-like model for a supercompact, then the results mentioned earlier suggest we have coherence for all these Hod-models.

The theory of the universe that "ultimate $L$" provides us with is essentially the theory of a very rich $L$-like model. It will not be a complete theory, by the incompleteness theorems, but any theory $T$ whose consistency we can establish by, say, forcing from large cardinals would be interpretable from it, so "ultimate $L$" is all we need, in a sense, to study $T$. Similarly, only adding large cardinal axioms would give us a stronger theory (but then, this strengthening would be immediately absorbed into the "ultimate $L$" framework).

It is in this sense that Woodin says that the "axiom" would give us a complete picture of the universe of sets. It would also be reasonable to say that this is the "correct" way of going about completing $\mathsf{ZFC}$, since any extension can be interpreted from this one.

[Note I am not advocating for the correctness of Woodin's viewpoint, or saying that it is my own. I feel I do not understand many of the technical issues at the moment to make a strong stance. As others, I am awaiting the release of the "suitable extender models" manuscript. Let me close with the disclaimer that, in case the technical details in what I have mentioned are incorrect, the mistakes are mine.]

Edit: (Jan. 10, 2011) Here is a link to slides of a talk by John Steel. Both Woodin's slides linked to above, and Steel's are for talks at the Workshop on Set Theory and the Philosophy of Mathematics, held at the University of Pennsylvania, Oct. 15-17, 2010. Hugh's talk was on Friday the 15th, John's was on Sunday. John's slides are a very elegant presentation of the motivations and mathematics behind the formulation of Ultimate $L$.

(Jul. 26, 2013) Woodin's paper has appeared, in two parts:

W. Hugh Woodin. Suitable extender models I, J. Math. Log., 10 (1-2), (2010), 101–339. MR2802084 (2012g:03135),

and

W. Hugh Woodin. Suitable extender models II: beyond $\omega$-huge, J. Math. Log., 11 (2), (2011), 115–436. MR2914848.

He is also working on a manuscript covering the beginning of the fine structure theory of these models. I will add a link once it becomes available.

John Steel has a nice set of slides discussing in some detail the multiverse view mentioned above: Gödel's program, CSLI meeting, Stanford, June 1, 2013.

For more on why one may want to accept large cardinals as a standard feature of the universe of sets, see here.

-
Does Ultimate L have any bearing on GCH? – Harry Gindi Nov 22 '10 at 10:50
@Harry Gindy: $L$ proves the GCH. @Andres: What a nice answer! – Carlo Von Schnitzel Nov 22 '10 at 14:50
@alephomega: Thanks! – Andrés Caicedo Nov 22 '10 at 15:20
@Harry: As alephomega pointed out, the $L$-like models satisfy GCH. The reason $L$ does can be traced back to a technical condition called "condensation", a suitable form of which holds for the larger $L$-like models. Since "Ultimate L" is essentially given as a limit of these models, GCH should hold there as well. – Andrés Caicedo Nov 22 '10 at 15:23
Thank you for this long and thoughtful answer! I am more intrigued than ever! – Alex Lupsasca Nov 23 '10 at 5:34

Alex, you ask a lot of questions, and I'm in no position to say much about Ultimate L. I'll just address this initial matter:

And how do we know that there are (infinitely) many different completions of ZFC in the first place? Could it be that there is no way to consistently assign truth-values to all first-order sentences, i.e. that no completion exists?

The existence of these completions of ZFC follows from Lindenbaum's lemma, a standard ingredient of proofs of the completeness theorem for first-order logic, at least assuming ZFC to be consistent. This also speaks to your second question there: it could be that no completion of ZFC exists, but only if ZFC itself is already inconsistent.

-
Thank you for bringing my attention to Lindenbaum's lemma; that does indeed answer one of my questions. Thank you :) – Alex Lupsasca Nov 23 '10 at 14:38

Ultimate L does not pick a unique completion of ZFC: Since we still want to have a recursively enumerable system of axioms, the theory generated by these axioms it will be incomplete by Gödel incompleteness.

But I share your view of a vertical direction (large cardinals) and a horizontal component (CH or its negation and various other statements that are independent over ZFC but don't have more consistency strength).

Even though we cannot hope to get a reasonable theory that is actually complete, we can try to go as far as possible in consistency strength by allowing large cardinals (note that since the large cardinal axioms seem to form a linear scale, there seems to be a distinguished direction to increase the consistency strength of our theory). At the same time, we want to keep control about the structure of sets. Hence, we are looking for a universe that is somehow canonical but still knows all the large cardinals. The canonicity would decide what is going on in the horizontal direction to a large extend, like $V=L$ does.
The existence of large cardinals would provide strength and decide things decided by large cardinals in the "right" way (for example, projective sets (sets of reals obtained by iterating projection and complementation, starting from Borel sets) should be Lebesgue measurable snce this is implied by large cardinals).

-
Thank you for your answer :) As for your first paragraph: Ultimate L does not pick a unique completion of ZFC because of Godel incompleteness; but assuming that the LCA hierarchy is indeed linearly ordered, then doesn't Ultimate L + LCA pick out a unique completion? That is, I thought that the two together remove both the horizontal and vertical ambiguity. – Alex Lupsasca Nov 23 '10 at 14:41
As I said in my answer: No consistent, recursively axiomatizable theory that extends ZFC is complete by Gödel's incompleteness theorem. And you definately want to have a procedure that tells you whether or not a given sentence is an axiom of your theory in order to do reasonable mathematics. (Maybe you could get away with a recursively enumerable set of axioms, but that also cannot give you a complete theory.) An example of a statement that is not decided by V=ultimate L is the statement "V=ultimate L is consistent" (this is assuming it actually is consistent. – Stefan Geschke Nov 23 '10 at 22:45
(Maybe you could get away with a recursively enumerable set of axioms, but that also cannot give you a complete theory.) Stefan, can you explain why non-recursively axiomatizable theory cannot be complete? In my understanding, Godel's incompleteness theorem would not apply to non-recursively axiomatizable theory. – Lianna Nov 24 '10 at 2:42
@Lianna: Any theory which has a recursively enumerable axiomatization, in fact has a recursive axiomatization, and then Gödel applies yet again. Why is this true? Given a recursive enumeration A_1, A_2, ... of axioms, it's a short exercise to think of an alternative axiomatization of the same theory which can be recursively enumerated in increasing order (of Gödel numbers of formulas). But any set which has an increasing recursive enumeration is recursive. This crafting of an alternative axiomatization is sometimes called "Craig's trick". – Ed Dean Nov 24 '10 at 5:07
@Ed Dean: Yes of course Godel's incompleteness applies to recursively enumerable theory. That's clear, but that's not my question. Stefan comment seems to imply that Godel's incompleteness applies to non-recursively theory as well, he says: "Maybe you could get away with a recursively enumerable set of axioms, but that also cannot give you a complete theory". I don't understand this statement because Godel's incompleteness would not apply to NON-recursively enumerable theory. – Lianna Nov 24 '10 at 11:19

Regarding the "horizontal degree of freedom", I highly recommend taking a look at Joel David Hamkins' slides. Among the many ideas there is that the horizontal degree of freedom might be considered not just moving from "left to right", but from "inner to outer".

Also, keep in mind that by a result of Scott, the constructible L and large cardinals are in direct conflict: L cannot have a measurable cardinal or any cardinal with consistency strength stronger than measurability. So it is perhaps not right to identify "moving towards L" with "following the lead of large cardinals" -- at a certain point they diverge in an unmistakable manner.

-
Here is the correct link: lumiere.ens.fr/~dbonnay/files/talks/hamkins.pdf – arsmath Dec 30 '10 at 8:27

Alex: Even if assuming that the LCA hierarchy is linearly ordered, still there is no hope to prove the consistency of LCA by Godel's incompleteness theorem. Therefore there is no consistency proof for the Ultimate L + LCA as well. If we never know for sure whether or not the Ultimate L + LCA is consistent, how can we be sure that the Ultimate L + LCA is correct?

-

protected by S. Carnahan♦Jul 26 '13 at 22:01

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.