17

Smullyan (1991, 2001) has argued forcefully that Tarski's undefinability theorem deserves much of the attention garnered by Gödel's incompleteness theorems. That the latter theorems have much to say about all of mathematics and more controversially, about a range of philosophical issues (e.g., Lucas 1961) is less than evident. Tarski's theorem, on the other hand, is not directly about mathematics but about the inherent limitations of any formal language sufficiently expressive to be of real interest. Such languages are necessarily capable of enough self-reference for the diagonal lemma to apply to them. The broader philosophical import of Tarski's theorem is more strikingly evident. - wikipedia

Can someone give an example of a "proof" which incorrectly uses Gödel's incompleteness theorem when it should instead use Tarski's undefinability theorem and point out the mistake? For example, I frequently hear the claim "Peano arithmetic is incomplete/inconsistent" justified by an appeal to Gödel - what's wrong with this?

Xodarap
  • 2,778
  • 14
  • 25

1 Answers1

17

There isn't anything wrong with justifying a claim that Peano Arithmetic is either inconsistent or incomplete by reference to Gödel's Incompleteness Theorems; the claim is a direct application of the first Incompleteness Theorem.

Gödel showed that any formal system of adequate expressive power for doing formal arithmetic was either inconsistent or incomplete in the sense that there would be sentences in the language of that system which that system could neither prove nor refute.

Tarski's theorem showed that no consistent formal language could define its own truth predicate. A a special case of that, no consistent formal system of arithmetic can include a predicate which applies to all and only the true sentences of arithmetic in the language of that formal system (and, on the intended interpretation of that language).

Smullyan's point, as I understand it, is that:

1) With the result that arithmetical truth cannot be defined in a system of arithmetic, Tarski "almost" got Gödel's results.

2) Much of the (somewhat sloppy) philosophical discussion about Gödel's theorems takes them to be showing that there are unprovable arithmetical truths. However, Gödel's proofs of his theorems were expressed purely syntactically in that they made no reference to truth but only to formal provability within a purely syntactically defined formal system. Indeed since Tarski gave the first satisfactory definition of truth for formal systems in 1936, whereas Gödel's results were published in 1931, there was no formally tractable notion of truth available to Gödel. Essentially, Gödel found a clever way in which to interpret arithmetical sentences as being about formal proofs in arithmetic and constructed a sentence that "said" of itself that it was not provable within the system of arithmetic. If the system is consistent that sentence will be true. However, Gödel's conclusion was not that there were unprovable truths; rather it was that every system adequate for arithmetic is either inconsistent or would have arithmetical sentences the system did not decide. This in no way invokes a concept of truth.

3) The point of Gödel's theorems is that arithmetic is not mechanistically decidable. Tarski's point is that no consistent system can define a truth predicate for the language in which it is articulated. Of the two, Tarski's seems to have richer philosophical import. (For instance, no formal model of English could define "true in English" while Gödel's results do not seem to apply to English at all.)

I am unaware of any example "proof" where appeal is made to Gödel that really ought be made to Tarski in the way your questions asks. (But, it is a big world.)

vanden
  • 1,644
  • 1
  • 13
  • 18
  • 3
    Thank you for updating your answer. I was grateful before and even more so now. Would that I had more than one vote to give! – Jon Ericson Jun 20 '11 at 17:24
  • 1
    Godel's theorems cannot, as far I know, be used to argue that Peano Arithmetic is inconsistent. – goblin GONE May 12 '13 at 04:18
  • 1
    I concur and would like to add that, for all we know, Peano Arithmetic is consistent even if we cannot proof it by finitary means. – Eric '3ToedSloth' May 22 '13 at 16:11
  • "Gödel's results do not seem to apply to English at all."

    Statement E: "There is no proof of statement E in the English language."

    Supposons qu'il existe une preuve de l'énoncé E dans la langue anglaise. Alors l'énoncé E est faux. Il n'y a donc aucune preuve de l'énoncé E dans la langue anglaise, QED.

     – Cyan Jan 19 '17 at 02:49
  • Something seems wrong with your second point: if there are, as you say at the end of said point, sentences that the system does not decide then either they are true or they are false, and then by definition become an instance of something true that cannot be proven, or something false whose negation is true and cannot be proven.

    The fact that Gödel does not make a reference to truth in a formal way does not hinder us from observing that his results can be interpreted to mean something about the truth of arithmetical propositions.

     – Santiago Estupiñán Feb 19 '23 at 19:36
  • @Eric'3ToedSloth': Indeed PA is likely consistent, considering the available evidence (Math SE). In particular, there are first- and second-order proofs that N, the set of natural numbers, is a model of PA; so if one believes that ZF (without Choice!), T, or Z₂ are consistent, then they ought to believe that PA is also consistent. From this, Gödel would claim that PA is incomplete, and indeed there are Gödel-sentences for PA. – Corbin Sep 22 '23 at 22:37
  • 1
    @SantiagoEstupiñán: Yes. Keep in mind that the traditional understanding of such sentences is that they are "unprovable but true:" we can either accept the sentence as true, or reject it as false; and while we get a new theory either way, the better choice is to accept it as true. For example, rejecting a Gödel-sentence for PA will yield a non-standard model of arithmetic, but acceptance always reuses the same model N. In this sense, those Gödel-sentences for PA are all true, since N is the natural numbers. – Corbin Sep 22 '23 at 22:40