4
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Why the downvotes? If there is something wrong with the question please at least leave a comment so I can understand what needs to change. $\endgroup$ – DaggerOfMesogrecia Apr 10 '17 at 16:38
  • $\begingroup$ I don't know why the downvotes are there; but simply put : 1- there are many "natural" (i.e. not constructed for this purpose) systems that are not subject to Gödel's theorem's hypotheses (for instance Presburger's arithmetic, Tarski's geometry, etc.); 2- you cannot bind the cardinality of the "system" if you want there to be an infinite "system" : by the compactness theorem, if a first order theory has an infinite model, then it has models of all infinite cardinalities. $\endgroup$ – Max Apr 10 '17 at 16:56
  • $\begingroup$ Gödel's Theorem applies to any system that allows one to algorithmically verify if a certain statement is an axiom, to algorithmically verify whether a statement follows by a rule of inference from some given statements, and that is powerful enough to express basic arithmetic of the natural numbers ... $\endgroup$ – Hagen von Eitzen Apr 10 '17 at 16:59
  • $\begingroup$ Unrelated to the question, but @Max, that's not entirely true. By including lots of constants in your language (say $\omega_\alpha$ many) and saying in your theory that they are pairwise different, you can make sure that all models have cardinality at least $\omega_\alpha$. But you're right of course when one restricts attention to countable theories. $\endgroup$ – martin.koeberl Apr 10 '17 at 17:09
  • $\begingroup$ @Mauro ALLEGRANZA I'm not proposing limiting the "amount of arithmetic" I'm proposing increasing the expressiveness of a system such that it's statements can no longer be represented as elements within the system. $\endgroup$ – DaggerOfMesogrecia Apr 10 '17 at 17:24
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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