Tarski's Undefinability Theorem

Tarski's theorem on the undefinability of truth shows that no sufficiently expressive formal language can define its own truth predicate. This result is closely related to Gödel's incompleteness theorems and reveals deep limitations of formal systems.

Statement

Theorem6.2Tarski's Undefinability Theorem

Let $\mathcal{L}$ be the language of arithmetic and $\mathbb{N}$ the standard model. There is no $\mathcal{L}$ -formula $\mathrm{True}(x)$ such that for every $\mathcal{L}$ -sentence $\sigma$ : $\mathbb{N} \models \mathrm{True}(\ulcorner \sigma \urcorner) \iff \mathbb{N} \models \sigma.$ In other words, the set of Gödel numbers of true arithmetic sentences $\mathrm{Th}(\mathbb{N})$ is not definable in $\mathbb{N}$ .

Proof

Suppose for contradiction that $\mathrm{True}(x)$ is an $\mathcal{L}$ -formula satisfying $\mathbb{N} \models \mathrm{True}(\ulcorner \sigma \urcorner) \iff \mathbb{N} \models \sigma$ for all sentences $\sigma$ .

By the diagonal lemma (which holds in $\mathbb{N}$ since it models PA), there exists a sentence $\lambda$ such that: $\mathbb{N} \models \lambda \iff \mathbb{N} \models \neg \mathrm{True}(\ulcorner \lambda \urcorner).$

But by the assumed property of $\mathrm{True}$ : $\mathbb{N} \models \mathrm{True}(\ulcorner \lambda \urcorner) \iff \mathbb{N} \models \lambda$ .

Combining: $\mathbb{N} \models \lambda \iff \mathbb{N} \models \neg \lambda$ . This is a contradiction. $\square$

■

Consequences

ExamplePartial Truth Predicates

While the full truth predicate for $\mathcal{L}_{\text{PA}}$ is not definable in $\mathbb{N}$ , partial truth predicates exist. For each $n$ , there is a $\Sigma_n$ formula $\mathrm{True}_{\Sigma_n}(x)$ that correctly evaluates all $\Sigma_n$ sentences. The truth predicate for $\Sigma_n$ formulas is $\Pi_n$ -definable, which is one level higher in the arithmetic hierarchy.

RemarkRelationship to Gödel

Tarski's theorem can be seen as the semantic counterpart of Gödel's first incompleteness theorem. Gödel showed that provability fails to capture truth; Tarski showed that truth itself cannot be internally defined. Both results use the diagonal lemma, but Gödel works with provability ( $\mathrm{Prov}_T$ ) while Tarski works with truth ( $\mathrm{True}$ ).

RemarkLiar Paradox

Tarski's theorem is the formal resolution of the liar paradox ("this sentence is false"). The paradox arises because natural language can define its own truth predicate. Tarski's theorem shows that no formal language with sufficient expressive power can do so consistently, implying that the truth of a language must be defined in a richer metalanguage.