Completion of ZFC - MathOverflow

Completion of ZFC

2010-11-22T05:23:55Z

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!

Answer by Ed Dean for Completion of ZFC

2010-11-22T05:39:28Z

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.

Answer by Stefan Geschke for Completion of ZFC

2010-11-22T05:47:25Z

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).

Answer by Andres Caicedo for Completion of ZFC

2010-11-22T08:05:46Z

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.

Our current understanding of set theory gives us great confidence in the large cardinal hierarchy. ZFC is incomplete, and so is any theory we can describe. However, there seems to be a linear ordering of strengthenings of ZFC, provided by the large cardinal axioms. Moreover, this is not an arbitrary ordering, but in fact most extensions of ZFC that have been studied are bi-interpretable with an extension of 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 certain fragments of determinacy while, beginning with these 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 bi-interpretability of both theories. Of course, if we begin with the $L$-like model for 2 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 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 won't 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 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.

Answer by Hilmi for Completion of ZFC

2010-11-23T15:41:25Z

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?

Answer by Karl S for Completion of ZFC

2010-12-03T04:14:26Z

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.