1
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ How can there be uncountably many sentences? $\endgroup$ May 29, 2010 at 22:42
  • $\begingroup$ 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. $\endgroup$ May 29, 2010 at 22:59
  • $\begingroup$ 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). $\endgroup$
    – S. Carnahan
    May 29, 2010 at 23:48
  • 1
    $\begingroup$ 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. $\endgroup$ May 30, 2010 at 0:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kiochi
    May 30, 2010 at 20:34

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ May 30, 2010 at 0:17
  • $\begingroup$ 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? $\endgroup$ May 30, 2010 at 0:21
  • $\begingroup$ By the way if someone would give me one more down vote it seems I can pick up the "peer pressure" badge... $\endgroup$ May 30, 2010 at 0:24
  • $\begingroup$ I rewrote parts of my answer while you were writing your comment. Does the new write up answer your question? $\endgroup$ May 30, 2010 at 0:28
  • $\begingroup$ 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. $\endgroup$ May 30, 2010 at 0:47
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ +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/… $\endgroup$ May 30, 2010 at 0:36
  • $\begingroup$ 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. $\endgroup$ May 30, 2010 at 1:07
  • $\begingroup$ 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. $\endgroup$ May 30, 2010 at 2:06
  • 1
    $\begingroup$ There are only countably many formulas in the language of arithmetic. Each formula is finite. $\endgroup$ May 30, 2010 at 2:10
  • 2
    $\begingroup$ 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. $\endgroup$ May 30, 2010 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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