System of Axioms that violate Godel's Incompleteness Theorem

443 Views Asked by At

As I understand it, Godel's incompleteness theorem will only apply to any system for which the set of all statements in the system can be mapped to a set unique elements in that system (The Godel numbers of the statements).

If this understanding is correct, would it not therefore be possible to design a system such that the cardinality of the set of all possible statements within a system was greater than the cardinality of the set of all possible elements in a system which would then not be bound by the incompleteness theorem? (Perhaps through some infinite set of operators or if not that then through some other means)

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, you can do this in many ways.

The most obvious is to take the language of arithmetic $L=\{+,\times, 0, 1, <\}$ and add a whole ton of junk to it. For example, we could add uncountably many constant symbols $c_i$ ($i\in I$, $I$ appropriately large). The resulting language $L'$ would be bigger than the standard model $\mathbb{N}$ of arithmetic, so there would be no way of representing each $L'$-sentence by an element of $\mathbb{N}$ as in Goedel numbering. And there are lots of similar tricks we can play.

However, there are a few points to make.

  • This is not the most natural way of getting a theory to which Goedel does not apply. More naturally, we could take a theory which is too weak (e.g. Presburger arithmetic; and there are even "intermediate" theories of arithmetic which are strong enough to express their own consistency, but weak enough to not be be subject to Goedel's second theorem, and in fact prove their own consistency). Another approach would be to take theories which are too strong (e.g. the complete theory of arithmetic, for which consistency isn't even expressible in the language of arithmetic), or are too complicated (e.g. we can give a non-recursive definable presentation of Peano arithmetic which proves its own consistency).

  • The theories we get from this language-expansion may still be incomplete, for essentially the same reason as PA! For example, let $L'$ be as above, and consider $PA$ as a theory in this language (so we add no new axioms governing the $c_i$s). Then $Con(PA)$ is still unprovable in this setting. Moreover, even if we add some axioms to $PA$, as long as we do so in a "nice" way we'll still hit up against incompleteness. E.g. let $PA'$ be $PA$ together with "$c_i\not=c_j$" for all $i\not=j$ (note that any model of $PA'$ must be uncountable!). Then every finite fragment of $PA'$ is interpretable in $PA$, and in fact $PA$ proves the consistency of each finite fragment of $PA'$ appropriately construed; so no finite fragment of $PA'$ proves $Con(PA)$ by Goedel. But this in turn means that $PA'$ doesn't prove $Con(PA)$, by Goedel's completeness theorem. So at the end of the day, you still have to add some interesting axioms after expanding your language, and you have to do so in a sufficiently complicated way as to get around Goedel; so really this approach, although it does appear to block Goedel coding, isn't the way to go about things.