What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic - MathOverflow

What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic

2010-05-29T22:31:27Z

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?

Answer by François G. Dorais for What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic

2010-05-29T23:51:59Z

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 φ₁,...,φ_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.

Answer by Carl Mummert for What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic

2010-05-30T00:28:18Z

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.