# Tarski's undefinability theorem

This article includes a list of general references, but it lacks sufficient corresponding inline citations. (August 2023) |

**Tarski's undefinability theorem**, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that "arithmetical truth cannot be defined in arithmetic".^{[1]}

The theorem applies more generally to any sufficiently strong formal system, showing that truth in the standard model of the system cannot be defined within the system.

## History

In 1931,

*coding*and, more generally, as arithmetization. In particular, various

*sets*of expressions are coded as sets of numbers. For various syntactic properties (such as

*being a formula*,

*being a sentence*, etc.), these sets are computable

The undefinability theorem shows that this encoding cannot be done for

^{[2]}

The undefinability theorem is conventionally attributed to Alfred Tarski. Gödel also discovered the undefinability theorem in 1930, while proving his incompleteness theorems published in 1931, and well before the 1933 publication of Tarski's work (Murawski 1998). While Gödel never published anything bearing on his independent discovery of undefinability, he did describe it in a 1931 letter to John von Neumann. Tarski had obtained almost all results of his 1933 monograph "*The Concept of Truth in the Languages of the Deductive Sciences*" between 1929 and 1931, and spoke about them to Polish audiences. However, as he emphasized in the paper, the undefinability theorem was the only result he did not obtain earlier. According to the footnote to the undefinability theorem (Twierdzenie I) of the 1933 monograph, the theorem and the sketch of the proof were added to the monograph only after the manuscript had been sent to the printer in 1931. Tarski reports there that, when he presented the content of his monograph to the Warsaw Academy of Science on March 21, 1931, he expressed at this place only some conjectures, based partly on his own investigations and partly on Gödel's short report on the incompleteness theorems "Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit" [Some metamathematical results on the definiteness of decision and consistency], Austrian Academy of Sciences, Vienna, 1930.

## Statement

We will first state a simplified version of Tarski's theorem, then state and prove in the next section the theorem Tarski proved in 1933.

Let be the language of

Let be the standard structure for i.e. consists of the ordinary set of natural numbers and their addition and multiplication. Each sentence in can be interpreted in and then becomes either true or false. Thus is the "interpreted first-order language of arithmetic".

Each formula in has a

*Tarski's undefinability theorem*: There is no -formula that defines
That is, there is no -formula such that for every -sentence holds in .

Informally, the theorem says that the concept of truth of first-order arithmetic statements cannot be defined by a formula in first-order arithmetic. This implies a major limitation on the scope of "self-representation". It *is* possible to define a formula whose extension is but only by drawing on a metalanguage whose expressive power goes beyond that of . For example, a truth predicate for first-order arithmetic can be defined in second-order arithmetic. However, this formula would only be able to define a truth predicate for formulas in the original language . To define a truth predicate for the metalanguage would require a still higher metametalanguage, and so on.

To prove the theorem, we proceed by contradiction and assume that an -formula exists which is true for the natural number in if and only if is the Gödel number of a sentence in that is true in . We could then use to define a new -formula which is true for the natural number if and only if is the Gödel number of a formula (with a free variable ) such that is false when interpreted in (i.e. the formula when applied to its own Gödel number, yields a false statement). If we now consider the Gödel number of the formula , and ask whether the sentence is true in , we obtain a contradiction. (This is known as a diagonal argument.)

The theorem is a corollary of Post's theorem about the arithmetical hierarchy, proved some years after Tarski (1933). A semantic proof of Tarski's theorem from Post's theorem is obtained by reductio ad absurdum as follows. Assuming is arithmetically definable, there is a natural number such that is definable by a formula at level of the arithmetical hierarchy. However, is -hard for all Thus the arithmetical hierarchy collapses at level , contradicting Post's theorem.

## General form

Tarski proved a stronger theorem than the one stated above, using an entirely syntactical method. The resulting theorem applies to any formal language with

*Tarski's undefinability theorem (general form)*: Let be any interpreted formal language which includes negation and has a Gödel numbering satisfying the diagonal lemma, i.e. for every -formula (with one free variable ) there is a sentence such that holds in . Then there is no -formula with the following property: for every -sentence is true in .

The proof of Tarski's undefinability theorem in this form is again by reductio ad absurdum. Suppose that an -formula as above existed, i.e., if is a sentence of arithmetic, then holds in if and only if holds in . Hence for all , the formula holds in . But the diagonal lemma yields a counterexample to this equivalence, by giving a "liar" formula such that holds in . This is a contradiction. QED.

## Discussion

The formal machinery of the proof given above is wholly elementary except for the diagonalization which the diagonal lemma requires. The proof of the diagonal lemma is likewise surprisingly simple; for example, it does not invoke recursive functions in any way. The proof does assume that every -formula has a

An interpreted language is *strongly-semantically-self-representational* exactly when the language contains

*No sufficiently powerful language is strongly-semantically-self-representational*.

The undefinability theorem does not prevent truth in one theory from being defined in a stronger theory. For example, the set of (codes for) formulas of first-order

## See also

- Chaitin's incompleteness theorem– Measure of algorithmic complexity
- Gödel's completeness theorem – Fundamental theorem in mathematical logic
- Gödel's incompleteness theorems – Limitative results in mathematical logic

## References

**
**

### Primary sources

- Tarski, A. (1933).
*Pojęcie Prawdy w Językach Nauk Dedukcyjnych*(in Polish). Nakładem Towarzystwa Naukowego Warszawskiego. - Tarski, A. (1936). "Der Wahrheitsbegriff in den formalisierten Sprachen" (PDF).
*Studia Philosophica*(in German).**1**: 261–405. Archived from the original (PDF) on 9 January 2014. Retrieved 26 June 2013.- Tarski, A. (1983). "The Concept of Truth in Formalized Languages" (PDF). In Corcoran, J. (ed.).
*Logic, Semantics, Metamathematics*. Translated by J. H. Woodger. Hackett. English translation of Tarski's 1936 article.

- Tarski, A. (1983). "The Concept of Truth in Formalized Languages" (PDF). In Corcoran, J. (ed.).

## Further reading

- Bell, J. L.; Machover, M. (1977).
*A Course in Mathematical Logic*. North-Holland. - Boolos, G.; Burgess, J.; Jeffrey, R. (2002).
*Computability and Logic*(4th ed.). Cambridge University Press. - S2CID 55408480. Archived from the originalon 2007-08-19.
- Murawski, R. (1998). "Undefinability of truth. The problem of the priority: Tarski vs. Gödel".
*History and Philosophy of Logic*.**19**(3): 153–160.doi:10.1080/01445349808837306. Archived from the originalon 2011-06-08. - Smullyan, Raymond M. (1992).
*Gödel's Incompleteness Theorems*. Oxford: Oxford University Press, USA. . - Smullyan, R. (2001). "Gödel's Incompleteness Theorems". In Goble, L. (ed.).
*The Blackwell Guide to Philosophical Logic*. Blackwell. pp. 72–89. .