Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
1  
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
2  
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
2  
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

2 Answers 2

up vote 10 down vote accepted

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$."

share|improve this answer

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

share|improve this answer
3  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.