Tarski's indefinability theorem

The set of Tarski about the elusiveness of truth is a limiting result in mathematical logic, which on Alfred Tarski back (1936). Informally the sentence says that the concept of truth in a language cannot be defined with the means of expression of the language itself. The proof is carried out using the so-called Tarski theorems, self-referential sentences of the form: I am an element of M for a set M. If one chooses the set of all false sentences of a system for M, the construction of a Tarski sentence leads to a contradiction: A true proposition that is unprovable in the system. From this it can be concluded that the set of all true propositions of a system cannot be defined within this system. This is no contradiction to the examples of formal systems given by Tarski himself, in which the concept of truth coincides with the concept of provability. In these cases the concept of provability cannot be defined within the system.

history

In 1931 Kurt Gödel published the Incompleteness Theorems , as proof of which he showed how the syntax of formal logic can be represented within first-order arithmetic . Each expression in the formal language of arithmetic is assigned a unique number. This procedure is known variously as Godel numbering , coding or more generally as arithmetization. In particular, different sets or expressions are coded as sets of numbers. It turns out that for various syntactic properties (e.g. is a formula , is a sentence ) these quantities can be calculated .

In addition, all calculable quantities or numbers can be defined by an arithmetic formula. For example, there are formulas in the language of arithmetic that define the set of Godel numbers for sentences of arithmetic and for provable sentences of arithmetic.

The indefinability theorem shows that this arithmetization cannot be carried out for semantic concepts such as truth . The sentence shows that no sufficiently powerful, interpreted language can represent its own semantics. One implication is that a metalanguage that is able to express the semantics of an object language must have a higher expressiveness than that language.

The sentence about the indefinability of truth is generally attributed to Alfred Tarski. However, Gödel discovered this theorem while he was working on the proof of his incompleteness theorems published in 1931 , long before the publication of Tarski's work in 1936 (Murawski 1998). Gödel never published anything on his independent discovery of indefinability, but described it as early as 1931 in a letter to Johann von Neumann . Between 1929 and 1931 Tarski had received almost all of the results of his 1936 essay "The Concept of Truth in Formalized Languages" and had spoken about them in front of a Polish audience. However, as he pointed out in the essay, the sentence about the indefinability of truth was the only result he had not received earlier. In the footnote to the sentence, Tarski notes that he added the sentence and his proof sketch only after the print version had been completed.

Statement of the sentence

We will first give and explain a simplified version of Tarski's theorem, and in the next section we will prove a version that Tarski actually proved in 1936. Let be the language of first order arithmetic and the standard structure for . The pair is then an interpretation of the arithmetic in the language of first order predicate logic . Every sentence in has a Gödel number . Further denote the set of - sentences that are true in and the set of Godel numbers of the sentences in . ${\ displaystyle L}$ ${\ displaystyle N}$ ${\ displaystyle L}$ ${\ displaystyle (L, N)}$ ${\ displaystyle x}$ ${\ displaystyle L}$ ${\ displaystyle g (x)}$ ${\ displaystyle T}$ ${\ displaystyle L}$ ${\ displaystyle N}$ ${\ displaystyle T ^ {*}}$ ${\ displaystyle T}$

Tarski's theorem of indefinability: There is no - formula that defines. ${\ displaystyle L}$ ${\ displaystyle W (n)}$ ${\ displaystyle T ^ {*}}$ That is, there is no formula that decides for a given Godel number whether the associated arithmetic sentence is true. ${\ displaystyle L}$ ${\ displaystyle W (n)}$ ${\ displaystyle n}$

Simply put, for a given arithmetic, the concept of truth in an interpretation cannot be expressed by the means of that arithmetic language. However, such a formula can be defined in a suitable metalanguage . For example, a truth predicate for first order arithmetic can be defined in second order arithmetic . However, this formula can only define the truth for statements of first-order arithmetic, and not the truth of more general statements of second-order arithmetic. To define a truth predicate , the metalanguage would require a higher level metametanguage, and so on. ${\ displaystyle L}$ ${\ displaystyle W (n)}$

The theorem just formulated is a consequence of Post's theorem on arithmetic hierarchy , which was proven a few years after Tarski's proof of the above theorem. A semantic derivation of Tarski's theorem from Post's theorem is obtained as follows by contradiction. If such a truth formula were arithmetically definable, there would be a natural number , so that it belongs to the level of the arithmetic hierarchy . But is -hard for everyone , so that the arithmetic hierarchy would have to collapse to -hierarchy, which would contradict Post's theorem. Hence there can be no such formula . ${\ displaystyle W ^ {*}}$ ${\ displaystyle n}$ ${\ displaystyle W ^ {*}}$ ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle W ^ {*}}$ ${\ displaystyle \ Sigma _ {k} ^ {0}}$ ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle W ^ {*}}$

generalization

Tarski proved a stronger proposition than the one given above. The theorem proved by Tarski is valid for languages which have negation and sufficient self-referentiality , which is especially fulfilled by first-order arithmetic.

Tarski's theorem of indefinability (in generalized form): Be an interpreted formal language that contains a negation and has a Godel number , so that for every formula there is a formula so that in applies. Let be the set of god numbers of sentences that are true. Then there is no formula that defines. That is, there is no formula so that in itself is true. ${\ displaystyle (L, N)}$ ${\ displaystyle g (x)}$ ${\ displaystyle L}$ ${\ displaystyle A (x)}$ ${\ displaystyle B}$ ${\ displaystyle B \ Leftrightarrow A (g (B))}$ ${\ displaystyle N}$ ${\ displaystyle T}$ ${\ displaystyle L}$ ${\ displaystyle N}$ ${\ displaystyle L}$ ${\ displaystyle W (n)}$ ${\ displaystyle T ^ {*}}$ ${\ displaystyle L}$ ${\ displaystyle A}$ ${\ displaystyle W (g (A)) \ Leftrightarrow A}$ ${\ displaystyle N}$

The proof for Tarski's theorem of indefinability in this form is again by contradiction. Suppose a formula is defined . For an arithmetic proposition , then in particular is true if and only if in is true. So even the Tarski then -Satz in true. With the help of the fixed point theorem , a counterexample to this equivalence can now be constructed, because it implies the existence of a formula so that in holds. So there can be no such formula . ${\ displaystyle L}$ ${\ displaystyle W (n)}$ ${\ displaystyle T ^ {*}}$ ${\ displaystyle A}$ ${\ displaystyle W (g (A))}$ ${\ displaystyle A}$ ${\ displaystyle N}$ ${\ displaystyle T}$ ${\ displaystyle W (g (A)) \ Leftrightarrow A}$ ${\ displaystyle N}$ ${\ displaystyle L}$ ${\ displaystyle S}$ ${\ displaystyle S \ Leftrightarrow \ neg W (g (S))}$ ${\ displaystyle N}$ ${\ displaystyle L}$ ${\ displaystyle W (n)}$

Conversely, it follows from the existence of such a formula that the function cannot express. The language would not have enough self-reference. In this form, the theorem is applicable to decidable axiom systems like that of Euclidean geometry or the real closed solids. ${\ displaystyle L}$ ${\ displaystyle W (n)}$ ${\ displaystyle L}$ ${\ displaystyle g (x)}$

Tarski's theorem of indefinability provides some well-known properties of first-order arithmetic resulting from Gödel's theorems of incompleteness. But Tarski's theorem does not imply Gödel's theorems, and the reverse is also not possible.

discussion

Tarski's theorem implies an inherent limitation in every formal language. The only requirement is that the formal language allows sufficient self-reference that the fixed point theorem is applicable. Hence, Smullyan (1991, 2001) argues that a large part of the importance attached to incompleteness theorems actually belongs to Tarski's indefinability theorem .

literature

A. Tarski : The concept of truth in formalized languages . In: Studia Philosophica . tape 1 , 1936, pp. 261–405 ( archive.org [PDF; accessed February 18, 2019]).
Alfred Tarski: Truth and proof . In: L'age de la Science . tape 1 , 1969, p. 279-301 .
Wolfgang Stegmüller , Matthias Varga von Kibéd: Part C, self-reference, Tarski sentences and the indefinability of arithmetic truth (= structural types of logic . Volume III ).
R. Smullyan , 1991. Gödel's Incompleteness Theorems . Oxford Univ. Press.
R. Smullyan, 2001. "Gödel's Incompleteness Theorems". In L. Goble, ed., The Blackwell Guide to Philosophical Logic , Blackwell, 72-89.

Individual evidence

^ Alfred Tarski: Truth and proof (1969) . In: Ralph McKenzie, Steven Givant (Eds.): Tarski: Collected Papers . tape 4 . Birkhäuser, Basel, Boston, Stuttgart 1986, pp. 401-423 .
↑ Dirk W. Hoffmann: The limits of mathematics . 3. Edition. Springer Spectrum, Berlin, Heidelberg 2018, p. 204, 239 .

[1] Alfred Tarski: Truth and proof (1969) . In: Ralph McKenzie, Steven Givant (Eds.): Tarski: Collected Papers . tape 4 . Birkhäuser, Basel, Boston, Stuttgart 1986, pp. 401-423 .

[2] Dirk W. Hoffmann: The limits of mathematics . 3. Edition. Springer Spectrum, Berlin, Heidelberg 2018, p. 204, 239 .