define for arbitrarily large n. Computability properties As discussed above, is not arithmetically definable, by Tarski's theorem. A corollary of Post's theorem establishes that the Turing degree of is 0(ω), and so is not decidable nor recursively enumerable. is closely related to the theory of the recursively enumerable Turing degrees, in the signature of partial orders. In particular, there are computable functions S and T such that: For each sentence φ in the signature of first-order arithmetic, φ is in if and only if S(φ) is in . For each sentence ψ in the signature of partial orders, ψ is in if and only if T(ψ) is in . Model-theoretic properties True arithmetic is an unstable theory, and so has models for each uncountable cardinal . As there are continuum many types over the empty set, true arithmetic also has countable models. Since the theory is complete, all of its models are elementarily equivalent. True theory of second-order arithmetic The true theory of second-order arithmetic consists of all the sentences in the language of second-order arithmetic that are satisfied by the standard model of second-order arithmetic, whose first-order part is the structure and whose second-order part consists of every subset of . The true theory of first-order arithmetic, , is a subset of the true theory of second-order arithmetic, and is definable in second-order arithmetic. However, the generalization of Post's theorem to the analytical hierarchy shows that the true theory of second-order arithmetic is not definable by any single formula in second-order arithmetic. has shown that the true theory of second-order arithmetic is computably interpretable with the theory of the partial order of all Turing degrees, in the signature of partial orders, and vice versa. Notes References . . . Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". An English translation "The Concept of Truth in Formalized Languages" appears in External links Model theory Formal theories of arithmetic