Tarski's Undefinability Theorem

From ProofWiki
Jump to navigation Jump to search


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$.


Informally, the theorem says that the set of true statements about arithmetic can't be defined arithmetically.


$\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).


Source of Name

This entry was named for Alfred Tarski.