True Arithmetic - Arithmetic Indefinability

Arithmetic Indefinability

The central result on true arithmetic is the indefinability theorem of Alfred Tarski (1936). It states that the set Th is not arithmetically definable. This means that there is no "universal formula" φ in the signature of first-order arithmetic such that, for every sentence θ in this signature,

if and only if

Here is the numeral of the canonical Gödel number of the sentence θ.

Post's theorem is a sharper version of the indefinability theorem that shows a relationship between the definability of Th and the Turing degrees, using the arithmetical hierarchy. For each natural number n, let Th_n be the subset of Th consisting of only sentences that are or lower in the arithmetical hierarchy. Post's theorem shows that, for each n, Th_n is arithmetically definable, but only by a formula of complexity higher than . Thus no single formula can define Th, because

but no single formula can define Th_n for arbitrarily large n.