Tarski's Undefinability Theorem
Theorem
Let $\ZZ$ be the standard structure $\struct {\Z, +, \cdot, s, <, 0}$ for the language of arithmetic.
Let $\operatorname {Th}_\ZZ$ be the sentences which are true in $\ZZ$.
Let $\Theta$ be the set of Gödel numbers of those sentences in $\operatorname {Th}_\ZZ$.
$\Theta$ is not definable in $\operatorname {Th}_\ZZ$.
Note
Informally, the theorem says that the set of true statements about arithmetic can't be defined arithmetically.
Proof
$\operatorname {Th}_\ZZ$ is easily seen to be a consistent extension of minimal arithmetic. (In fact, the axioms in minimal arithmetic were selected based on the behavior of standard arithmetic.)
Thus, the theorem is a special case of Set of Gödel Numbers of Arithmetic Theorems Not Definable in Arithmetic (and can be seen to follow immediately).
$\blacksquare$
Source of Name
This entry was named for Alfred Tarski.
Sources
- 2007: George S. Boolos, John P. Burgess and Richard C. Jeffrey: Computability and Logic (5th ed.): $\S 15$: Theorem $4$