Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let T be a true theory of arithmetic to which the incompleteness theorems apply. Consider two sentences in the language of T to be equivalent if they are provably equivalent over T. How many equivalence classes are there, under this relation, that contain a true-but-unprovable sentence?

share|improve this question
How can there be uncountably many sentences? –  Mariano Suárez-Alvarez May 29 '10 at 22:42
It seems you can easily construct (by nested recursion) sets of sentences that are false and grow like an infinite binary complete tree. I'll have to rethink that; for now I'll remove the comment, as it's not essential to the question. –  Halfdan Faber May 29 '10 at 22:59
I thought Gödel gives you a sentence for each choice of code, and there are countably infinitely many of those (assuming your language is a reasonable size). –  S. Carnahan May 29 '10 at 23:48
It would be reasonable to try cooking up nontraditional Goedel numberings that would not be provably isomorphic in the theory; I would try the same sort of construction as for non-acceptable Goedel numberings. But there are simpler solutions to the original question as Francois Dorais and I have indicated. –  Carl Mummert May 30 '10 at 0:36
Haldan, the reason your construction won't give you uncountably many false sentences is because each sentence is finite. Usually the language will only have finitely many symbols, so sentences will be finite strings of finitely many symbols. Clearly then you can have only countably many such. –  Kiochi May 30 '10 at 20:34
show 2 more comments

2 Answers

up vote 6 down vote accepted

Note: The top part answers an old version of the question, which is now irrelevant.

Given a axiomatizable theory T of arithmetic, the set of all statements independent of T is the complement of a computably enumerable set. When nonempty (e.g. when T extends PA) this set is countably infinite. (Trivially, if φ is such then so is φ∧∃x(x=x), etc.) However, there is no general algorithm to produce the shortest element of such a set, never mind counting them. (The requirement that the sentence be true is negligible since negation only adds a constant number of symbols depending on syntactic conventions.)

That said, some variants of your question have been actively studied. Hilbert's Tenth Problem says that there are Diophantine equations that have no integer solutions, but this fact is not provable from T. The question of the minimum number variables and minimum degree such diophantine equations have been studied. Over Z, Skolem showed that degree 4 is sufficient and Zhi-Wei Sun showed that 11 variables is sufficient. It is unknown whether these results are optimal.

Now that I reread your question, I think you wanted to have infinitely many logically inequivalent statements each of which is independent of T. This is true when T has no axiomatizable complete extension, which is guaranteed Gödel's Theorem when T is a consistent axiomatizable theory that extends PA.

Indeed, if there were only finitely many statements φ1,...,φk independent of T, up to T-provable equivalence. Then we could get an axiomatizable extension of T by adding to T each such φi or its negation ¬φi while maintaining consistency. (For example, when the standard model satisfies T, we can pick whichever is true in the standard model.) Since we're only adding finitely many new axioms, the result would be an axiomatizable complete theory even if our finitely many decisions were very complex; this would contradict Gödel's Theorem.

share|improve this answer
Francois, Thanks, Yes I wanted to exactly exclude such trivial extensions, such as you mention, so that when you have a non-decidable proposition φ and admit countably infinite decidable extensions such as φ∧∃x(x=x). The idea is to remove all sentence additions that are decidable and do not change the truth interpretation. –  Halfdan Faber May 30 '10 at 0:17
Francois, Thanks, I think you got it... Yes, when you add the undecidable statement to the axiom scheme, you find a new undecidable statement by diagonalization. This can continue ad infinitum. However, are you sure that all these sentences are undecidable in all extended axiom schemes? –  Halfdan Faber May 30 '10 at 0:21
By the way if someone would give me one more down vote it seems I can pick up the "peer pressure" badge... –  Halfdan Faber May 30 '10 at 0:24
I rewrote parts of my answer while you were writing your comment. Does the new write up answer your question? –  François G. Dorais May 30 '10 at 0:28
Francois, Thanks, I like your answer. I'm still thinking. However, did you understand my previous comment? If we assume there is one and only one sentence φ and find a new undecidable proposition φ2 by diagonalization in the axiom scheme extended with φ, will φ2 then be undecidable in the original axiom scheme? In general probably not, since it was explicitly constructed to state that it couldn't be proved in the extended axiom scheme. –  Halfdan Faber May 30 '10 at 0:47
show 1 more comment

The original question can be read sensibly as follows: Let T be a true theory of arithmetic to which the incompleteness theorems apply. Consider two sentences in the language of T to be equivalent if they are provably equivalent over T. How many equivalence classes are there, under this relation, that contain a true-but-unprovable sentence? This avoids the issue of sentences like φ∧∃x(x=x), which I think is what the question means by "with decidable tautologies or decidable sentences disregarded".

The answer is trivial, though, assuming T is a true theory: there are still countably many such equivalence classes, which is as many as there possible could be. "True theory" means "satisfied by the standard model".

First, T + Con(T) is strictly stronger than to T. Also T + Con(T) is a true theory, and the incompleteness theorems apply to it, so it is strictly weaker than (T+ Con(T)) + Con(T +Con(T)). Continuing this way gives an ω-chain of stronger and stronger true theories extending T, each of which adds only a finite number of (true) axioms to T.

There is a more non-trivial fact that regardless whether T is a true theory, if T is essentially incomplete then the Lindenbaum algebra of sentences modulo provability over T is the countable atomless Boolean algebra, so it has all sorts of structure. This is because any coatom [φ] in this algebra would correspond to a complete, consistent, effective theory T + φ, which cannot exist.

share|improve this answer
+1, Carl. Of course you know this, but some readers may be interested in knowing that your construction can be iterated into the transfinite up to $\omega_1^{CK}$. This is discussed in this old answer of mine - mathoverflow.net/questions/12865/… –  François G. Dorais May 30 '10 at 0:36
Carl, thanks for formulating my question with exactly the interpretation I had in mind. I will take the liberty of adding the reformulation to the question itself, if you don't mind. –  Halfdan Faber May 30 '10 at 1:07
Well, I took several down votes for objections to my claim that the set of sentences without semantic equivalence classes is uncountable. This is, however, actually true. For any statement P we add the infinite set of infinite statements of the form P & 0=0 & 1=1 & .... As this is isomorphic to the infinite set of infinite binary strings, it is trivially uncountable. With the equivalence classes everything becomes countable. A minimal sentence is simply the shortest sentence in the equivalence class. –  Halfdan Faber May 30 '10 at 2:06
There are only countably many formulas in the language of arithmetic. Each formula is finite. –  Carl Mummert May 30 '10 at 2:10
If you mean to use infinitary logics, you have to say so explicitly, because the default is ordinary first-order logic. But that would break other things in your question. In the context of infinitary logic, it is not obvious that the incompleteness theorem would hold. Also, because the usual axioms of PA are finite formulas, and the usual inference rules cannot generate infinitary formulas, you'd have to change something in order for any infinitary formula at all to be provable. –  Carl Mummert May 30 '10 at 11:17
show 1 more comment

Your Answer


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.