Tarski's undefinability theorem

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 ${\displaystyle L}$ be the language of first-order arithmetic. This is the theory of the natural numbers, including their addition and multiplication, axiomatized by the first-order Peano axioms. This is a "first-order" theory: the quantifiers extend over natural numbers, but not over sets or functions of natural numbers. The theory is strong enough to describe recursively defined integer functions such as exponentiation, factorials or the Fibonacci sequence.

Let ${\displaystyle \mathcal{N}}$ be the standard structure for ${\displaystyle L,}$ i.e. ${\displaystyle \mathcal{N}}$ consists of the ordinary set of natural numbers and their addition and multiplication. Each sentence in ${\displaystyle L}$ can be interpreted in ${\displaystyle \mathcal{N}}$ and then becomes either true or false. Thus ${\displaystyle (L,\mathcal{N})}$ is the "interpreted first-order language of arithmetic".

Each formula ${\displaystyle \phi }$ in ${\displaystyle L}$ has a Gödel number ${\displaystyle g(\phi ).}$ This is a natural number that "encodes" ${\displaystyle \phi .}$ In that way, the language ${\displaystyle L}$ can talk about formulas in ${\displaystyle L,}$ not just about numbers. Let ${\displaystyle T}$ denote the set of ${\displaystyle L}$-sentences true in ${\displaystyle \mathcal{N}}$, and ${\displaystyle T^{\ast }}$ the set of Gödel numbers of the sentences in ${\displaystyle T.}$ The following theorem answers the question: Can ${\displaystyle T^{\ast }}$ be defined by a formula of first-order arithmetic?

Tarski's undefinability theorem: There is no ${\displaystyle L}$-formula ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ that defines ${\displaystyle T^{\ast }.}$ That is, there is no ${\displaystyle L}$-formula ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ such that for every ${\displaystyle L}$-sentence ${\displaystyle A,}$ ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(g(A))⟺A}$ holds in ${\displaystyle \mathcal{N}}$.

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 ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ whose extension is ${\displaystyle T^{\ast },}$ but only by drawing on a metalanguage whose expressive power goes beyond that of ${\displaystyle L}$. 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 ${\displaystyle L}$. 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 ${\displaystyle L}$-formula ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ exists which is true for the natural number ${\displaystyle n}$ in ${\displaystyle \mathcal{N}}$ if and only if ${\displaystyle n}$ is the Gödel number of a sentence in ${\displaystyle L}$ that is true in ${\displaystyle \mathcal{N}}$. We could then use ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ to define a new ${\displaystyle L}$-formula ${\displaystyle S(m)}$ which is true for the natural number ${\displaystyle m}$ if and only if ${\displaystyle m}$ is the Gödel number of a formula ${\displaystyle \phi (x)}$ (with a free variable ${\displaystyle x}$) such that ${\displaystyle \phi (m)}$ is false when interpreted in ${\displaystyle \mathcal{N}}$ (i.e. the formula ${\displaystyle \phi (x),}$ when applied to its own Gödel number, yields a false statement). If we now consider the Gödel number ${\displaystyle g}$ of the formula ${\displaystyle S(m)}$, and ask whether the sentence ${\displaystyle S(g)}$ is true in ${\displaystyle \mathcal{N}}$, 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 ${\displaystyle T^{\ast }}$ is arithmetically definable, there is a natural number ${\displaystyle n}$ such that ${\displaystyle T^{\ast }}$ is definable by a formula at level ${\displaystyle {\mathrm{\Sigma }}_n^0}$ of the arithmetical hierarchy. However, ${\displaystyle T^{\ast }}$ is ${\displaystyle {\mathrm{\Sigma }}_k^0}$-hard for all ${\displaystyle k.}$ Thus the arithmetical hierarchy collapses at level ${\displaystyle n}$, 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 negation, and with sufficient capability for self-reference that the diagonal lemma holds. First-order arithmetic satisfies these preconditions, but the theorem applies to much more general formal systems, such as ZFC.

Tarski's undefinability theorem (general form): Let ${\displaystyle (L,\mathcal{N})}$ be any interpreted formal language which includes negation and has a Gödel numbering ${\displaystyle g(\phi )}$ satisfying the diagonal lemma, i.e. for every ${\displaystyle L}$-formula ${\displaystyle B(x)}$ (with one free variable ${\displaystyle x}$) there is a sentence ${\displaystyle A}$ such that ${\displaystyle A⟺B(g(A))}$ holds in ${\displaystyle \mathcal{N}}$. Then there is no ${\displaystyle L}$-formula ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ with the following property: for every ${\displaystyle L}$-sentence ${\displaystyle A,}$ ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(g(A))⟺A}$ is true in ${\displaystyle \mathcal{N}}$.

The proof of Tarski's undefinability theorem in this form is again by reductio ad absurdum. Suppose that an ${\displaystyle L}$-formula ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(n)}$ as above existed, i.e., if ${\displaystyle A}$ is a sentence of arithmetic, then ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(g(A))}$ holds in ${\displaystyle \mathcal{N}}$ if and only if ${\displaystyle A}$ holds in ${\displaystyle \mathcal{N}}$. Hence for all ${\displaystyle A}$, the formula ${\displaystyle \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(g(A))⟺A}$ holds in ${\displaystyle \mathcal{N}}$. But the diagonal lemma yields a counterexample to this equivalence, by giving a "liar" formula ${\displaystyle S}$ such that ${\displaystyle S⟺\mathrm{\neg }\mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}(g(S))}$ holds in ${\displaystyle \mathcal{N}}$. 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 ${\displaystyle L}$-formula has a Gödel number, but the specifics of a coding method are not required. Hence Tarski's theorem is much easier to motivate and prove than the more celebrated theorems of Gödel about the metamathematical properties of first-order arithmetic.

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.

An interpreted language is strongly-semantically-self-representational exactly when the language contains predicates and function symbols defining all the semantic concepts specific to the language. Hence the required functions include the "semantic valuation function" mapping a formula ${\displaystyle A}$ to its truth value ${\displaystyle ||A||,}$ and the "semantic denotation function" mapping a term ${\displaystyle t}$ to the object it denotes. Tarski's theorem then generalizes as follows: 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 Peano arithmetic that are true in ${\displaystyle \mathcal{N}}$ is definable by a formula in second order arithmetic. Similarly, the set of true formulas of the standard model of second order arithmetic (or ${\displaystyle n}$-th order arithmetic for any ${\displaystyle n}$) can be defined by a formula in first-order ZFC.