# “Completeness modulo Godel sentences”?

So this has been bugging me for roughly four years. When I was an undergraduate, I attended a colloquium in which the speaker was a 'cheerleader' for AD (the axiom of determinacy- an alternative to the axiom of choice).

In addition to the standard results of all sets being measurable, and the settling of the continuum hypothesis ($ZF+AD \implies¬ CH$), the speaker also made a quite extraordinary claim.

$ZF+AD$ is complete modulo Godel sentences

Now it wasn't until I got home and looked through my notes that this struck me as odd, but fairly soon thereafter, a flurry of questions occured to me:

Is this actually true? What does 'modulo' mean here? How on earth would one go about proving such a thing? What would it mean if one did? Does this mean that GIT is actually 'just a cheap trick'? Or is this just the same as saying 'consistent modulo inconsistencies'? Can one hope for similar results in other systems?

Some of these are evidently more answerable than others, and evidently that's rather a lot of questions to be covered in a single answer: so I'll plump, in summary, for the question:

What the Dickens is this all about?

-
I must echo your scepticism about "complete modulo Gödel sentences". Perhaps what the speaker meant was a more humble claim like "ZF + AD settles many questions undecidable in ZF" – which is certainly true as I understand it: AD implies the negation of AC, Con(ZF), a weak form of CH... – Zhen Lin Mar 4 '12 at 12:39
Mathematicians have a strange relationship with colloquia. In our papers, we often hesitate or refuse to say anything that is not literally true and precise, because such things lead to criticism. Even conjectures are used sparingly. But in colloquia, which are emphemeral and not put down in writing, we sometimes feel free to express our opinions a little more, and say things that are not precise enough for print. – Carl Mummert Mar 4 '12 at 13:31
Whether ZF+ADimplies CH or non-CH depends what exactly you mean by CH; there are at least two natural definitions, which are equivalent under ZFC, but not under ZF+AD: Cantor proposed the conjecture that there are only two kinds of infinite subsets of the reals: countable, and equinumerous with the continuum. This version of CH follows from ZF+AD. Under AC, it is reasonable to ask if the reals can be well-ordered in type $\omega_1$; this second version of CH is false under ZF+AD. (But the reason is not "cardinality", rather the fact that there is no well-order of the reals at all. – g.castro Mar 4 '12 at 13:41

Having worked on determinacy and followed closely the work of Woodin, Steel, and others in the area, I think I understand what was meant by the statement. But it is imprecise. I think perhaps the speaker was being rather informal. Let me modify the sentence in two crucial ways:

1. First, perhaps $\mathsf{AD}$ was mentioned because $\mathsf{AD}^+$ is more technical and difficult to state in a talk, but any statement of that kind should have been made about $\mathsf{AD}^+$ rather than $\mathsf{AD}$ itself.

2. Perhaps the statement was not meant about the theory of the universe of sets under $\mathsf{ZF}+\mathsf{AD}$, but rather about its inner model $L({\mathbb R})$. Or maybe a specific inner model that (in particular) satisfies $V=L({\mathcal P}({\mathbb R}))$.

Let me try to explain this a little. $\mathsf{AD}$ is an extremely powerful theory. If it holds, then it relativizes down to $L({\mathbb R})$, and moreover if choice holds and there are enough large cardinals in the universe, then again it holds in $L({\mathbb R})$. For this reasons it is understood that $L({\mathbb R})$ is a natural model to study determinacy, but it is a "minimal" model, far from being the only reasonable model. After all, strong versions of determinacy such as $\mathsf{AD}_{\mathbb R}$ actually fail in $L({\mathbb R})$ while they may hold in larger models. [The study of these models is closely tied up to the inner model program, so it is not just for curiosity's sake. See this MO question, and Grigor Sargsyan's paper "Descriptive inner model theory" for details.]

$L({\mathbb R})$ comes equipped with a rich fine structure. When determinacy holds in $L({\mathbb R})$, the combination of its rich combinatorial theory and the fine structure of the model allows us to prove several consequences that we do not know how to derive in general from just $\mathsf{AD}$. Namely, we can prove that in that situation, $\mathsf{AD}^+$ holds in $L({\mathbb R})$.

$\mathsf{AD}^{+}$ is a strengthening of $\mathsf{AD}$ introduced by Woodin, and it is understood to be the "right" version to work with when we look not just at $L({\mathbb R})$ but, more generally, at models of the form $L({\mathcal P}({\mathbb R}))$. In these models, $\mathsf{AD}^+$ allows us to prove much of the structure theory that we know holds in $L({\mathbb R})$. Just assuming $\mathsf{AD}$ does not seem enough to accomplish this. It is actually open whether $\mathsf{AD}$ implies $\mathsf{AD}^+$ in abstract. While this is settled, any question that is not specifically about sets "low" in the definability hierarchy is addressed under $\mathsf{AD}^+$. (For "low" sets we have that determinacy implies the nice coding theorem that tells us that solving the question in $L({\mathbb R})$ implies its solution in all larger models of determinacy.) $\mathsf{AD}^+$ also carries on this structure to other "natural" models of more complicated form.

All these caveats are needed:

1. If we only assume $\mathsf{AD}$ rather than $\mathsf{AD}^+$ there are many natural questions we do not know how to settle. Perhaps they are independent. Unless we are working in $L({\mathbb R})$, but then we actually have $\mathsf{AD}^+$ at our disposal anyway.

2. $\mathsf{AD}^+$ is a theory about reals and sets of reals. We can by forcing modify the universe at a sufficiently high cardinal $\kappa$ in many ways that will not affect ${\mathcal P}({\mathbb R})$, so $\mathsf{AD}^+$ is preserved, and yet we can change the combinatorics at $\kappa$ in crucial ways. So $\mathsf{AD}^+$ is not enough to have a "complete" theory. Unless we work in an $L({\mathcal P}({\mathbb R}))$ model to begin with.

3. Anyway, even assuming $\mathsf{AD}^+$, there are natural combinatorial questions that are not settled in these models, questions about the structure of $\omega_1^\omega$, for example. But in $L({\mathbb R})$ none of these issues are present.

So, in summary, I think the speaker was talking about the theory of $L({\mathbb R})$. In that case, it is true that any question we come up with seems to have a definite answer under the assumption of $\mathsf{AD}^+$ (or, in this case being the same, $\mathsf{AD}$). Yet, there are always two exceptions to a statement like this. Perhaps it helps to think of an analogy that is better understood:

In $L$, we seem to be able to solve just about any combinatorial question we ask. Gödel showed that choice holds in $L$ and so we assume $\mathsf{ZFC}$ to begin with. (Of course, we only need to assume $\mathsf{ZF}$, but that's silly. Similarly, we assume $\mathsf{AD}^+$ in $L({\mathbb R})$ although we can always start just with $\mathsf{AD}$, cite three or four papers so we actually get $\mathsf{AD}^+$, and then actually go on to do what we want.)

But this purely empirical observation that the theory $L$ is "complete" under $\mathsf{ZFC}$ obviously needs to be qualified, because things like "there are precisely 3 weakly compact cardinals" are not settled by the theory. So, we either qualify the completeness by saying "modulo large cardinals" or by assuming that all possible large cardinals that can be in $L$ are actually present. (Essentially, any large cardinal consequence compatible with $V=L$ of the existence of $0^\sharp$.)

But this is not enough, because we can play with arithmetization and get Gödel- or Rosser-like sentences that are independent. Sure. But this is not what we mean when we talk about "combinatorial statements".

So the common thing to say is that,

under large cardinals, modulo Gödel sentences, it is an empirical fact that the theory of $L$ is completely settled.

What we mean is that we have confidence, based on years of experience, that any combinatorial question we ask, we can solve in $L$, as long as we have as many large cardinals in $L$ as needed.

Just as commonly, we expect that assuming a strong forcing axiom such as $\mathsf{MM}$ (Martin's maximum) will have a similar effect, as long as the combinatorial problem being asked is about $\mathsf{ORD}^{\omega_1}$. So, it is common practice when facing a difficult combinatorial problem to first see how it goes under the assumption of $V=L$, and under the assumption of $\mathsf{MM}$. (The answers may very well be different.)

What we have with determinacy is precisely the same phenomenon: It is an empirical fact that any combinatorial question can be settled in $L({\mathbb R})$ assuming determinacy, and as rich a large cardinal structure as needed (essentially, whatever large cardinal structure would be provided in $L({\mathbb R})$ by the assumption that ${\mathbb R}^\sharp$ exists in $V$).

Again, this is an empirical fact, meaning that it is what we have observed in practice, but it is not a theorem. We just expect that faced with a question that is not about a Gödel- or Rosser-like trick, we should be able to solve it in $L({\mathbb R})$ if determinacy holds.

So what the speaker said is a weak statement ("practice seems to indicate this to be the case") that can be falsified at any moment. But doing that would be quite interesting and, truth be told, currently out of our reach: Producing a statement that $V=L$ does not settle even under large cardinals would require a completely novel method of obtaining independent results. We do not know of anything like that. See also here.

In the case of $L({\mathbb R})$, we would need a statement that is compatible with the existence of large cardinals in $V$, and yet independent. This would require a method for changing the theory of $L({\mathbb R})$. Of course we can change the model, by adding reals, but under large cardinals, forcing cannot change this theory so, again, we would need a completely novel technique.

(Is there an a priori way of knowing whether a combinatorial question is really combinatorial or a Gödel-like statement cleverly disguised? If not, then the speaker's statement is of course even weaker yet. Harvey Friedman's work is very much an attempt to show that there can be no such way, that incompleteness lurks in all natural combinatorial settings.)

-

It is very hard to answer without being at the colloquium, and without seeing anything in writing by the speaker. But one thing that could possibly have been meant is that this.

AD has been shown to answer many questions that are undecidable in ZF, such as the continuum hypothesis and other independent statements. The phenomenon is so striking that the speaker may feel that the only sentences that are not amenable to proof in the system are those that have some self-referential aspect, like the Goedel sentence. Of course this is not a claim amenable to proof, it is just an opinion that one might form after seeing a large number of questions that are undecidable from ZF become decidable in ZF plus AD.

One difficulty with Goedel sentences is that they are very simple, syntactically: they can be written with just a single universal quantifier over the natural numbers. Thus, in systems that classify formulas by the number of quantifiers, Goedel sentences always come out near the bottom, so these classification systems are not useful for giving sufficient criteria for a sentence to be provable or disprovable in set theory. There is no known syntactic method to separate "Goedel sentences" (i.e. ones that have some implicit or explicit self-reference) from "non-Goedel-sentences" in any reasonable way. But many mathematicians feel that there is nevertheless some sort of distinction between these kinds of sentences. That speaker appears to be alluding to that distinction.

-