Tarski's Undefinability Theorem

From ProofWiki
Jump to navigation Jump to search

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