# How to show the existence of an infinite set of independent undecidable sentences?

How to show the existence of an infinite set of independent undecidable sentences?

By "independent" I mean that no implication between any two elements is provable. A finite set that satisfies the condition is {Con(T), ~Con(T)}. But we can't add Con(T+X) for any sentence X to this set because that implies Con(T). Nor can we add ~Con(T+X) because ~Con(T) implies it.

If T is complete, then it has no undecidable sentences at all, so we assume that T is incomplete and therefore also consistent. So T could be ZFC, ZF, PA, Q, etc. Does there exist such an infinite set for any of those cases?

-
In what theory? –  Asaf Karagila May 12 '11 at 19:43
ZFC for example. And is the answer the same for ZF, PA, Q? –  Dan Brumleve May 12 '11 at 19:52
An incomplete theory is not automatically consistent. It is unknown whether or not ZFC is consistent, but it is certain incomplete (for example CH). –  Asaf Karagila May 12 '11 at 22:00
My understanding is that "consistent" means there is at least one sentence which is not a theorem, and "complete" means that for every sentence, either it or its negation is a theorem. So incomplete implies consistent. Should I specify that the theory is based on FOL? –  Dan Brumleve May 12 '11 at 22:52
When you say, "no one sentence implies any other," I think you should mean that no such implication is provable. Otherwise, you're open to the fact that among any two statements, either the first implies the second or conversely, since $(p\to q)\vee(q\to p)$ is a tautology. –  JDH May 13 '11 at 1:07

There is a general way to make this sequence of independent sentences over any effective, essentially incomplete theory. A theory $T$ is essentially incomplete if it is consistent and no consistent computable extension of $T$ is complete. Q, PA, ZF, and ZFC are examples of effective, essentially incomplete theories.

Assume that $T = T_0$ is effective and essentially incomplete. Then since $T$ is incomplete, there is a sentence $S_0$ such that $T + S_0$ and $T + \lnot S_0$ are both consistent. Let $R_0 = S_0$.

Now $T_1 = T + \lnot S_0$ is effective, and it is incomplete because $T$ is essentially incomplete. So there is a sentence $S_1$ such that both $T + \lnot S_0 + S_1$ and $T + \lnot S_0 + \lnot S_1$ are consistent. Let $R_1 = \lnot S_0 \land S_1$. Then $R_0$ cannot imply $R_1$ over $T$, and $R_1$ cannot imply $R_0$ over $T$, because both $T + R_0$ and $T + R_1$ are consistent.

Now $T_2 = T + \lnot S_0 + \lnot S_1$ is incomplete, because it is consistent and $T$ is essentially incomplete. So there is a sentence $S_2$ such that $T_2 + S_2$ and $T_2 + \lnot S_2$ are both consistent. Let $R_2 = \lnot S_0 \land \lnot S_1 \land S_2$ and let $T_3 = T_2 + \lnot S_2$. Then none of $R_0$, $R_1$, $R_2$ imply the others over $T$, and $T_3$ is again effective and incomplete. Continue inductively to generate an independent sequence of sentences $R_0, R_1, R_2, \ldots$.

The phenomenon in this proof can be stated more abstractly as: the Lindenbaum algebra of any effective, essentially incomplete theory is atomless.

It is interesting to analyze what the sentences $S_0$, $S_1$, etc. all say. The proof that the theories named above are essentially incomplete is constructive, and so we can actually construct examples of the sentences $S_i$. We have to use Rosser's variation of the incompleteness theorem, because theories such as $T_1$ will not be $\omega$ consistent. $S_i$ says, in informal terms, "if there is a proof of $S_i$ in $T_i$ then there is a shorter proof of $\lnot S_i$ in $T_i$". So $R_1$ says, informally, "There is a proof of $S_0$ in $T$ such that no proof of $\lnot S_0$ in $T$ is shorter, and if there is a proof of $S_1$ from $T + \lnot S_0$ then there is a shorter proof of $\lnot S_1$ from $T + \lnot S_0$."

-

Since my previous proof was both erroneous as well irrelevant after you specified a theory I will give somewhat of my own knowledge to this topic.

Firstly if $\tau$ is independent of $ZFC$ then it clearly independent of $ZF$. For that matter we have an easy way to produce infinitely many sentences:

$$\psi_n = \text{Between the sets }\mathcal P^n(\omega)\text{ and }\mathcal P^{n+1}(\omega)\text{ there are no other cardinalities}$$

That is the Continuum Hypothesis with relevance to $\beth$ numbers. Since the cardinality of the power set has to grow, and Easton's theorem tells us that we can set it to grow almost anyway we would like (we could have $2^{\aleph_0}=\aleph_1$ and $2^{\aleph_1} = \aleph_{583}$) we have that these are strictly independent of each other, and clearly of $ZFC$.

-
Perhaps it would be simpler to consider the statement, "the GCH holds at $\aleph_n$," which has a similar analysis. –  JDH May 13 '11 at 0:59
@JDH: You are absolutely right, I see little point in editing the answer at this point, with your comment present. –  Asaf Karagila May 13 '11 at 11:09