True arithmetic

Definition

The signature of Peano arithmetic includes the addition, multiplication, and successor function symbols, the equality and less-than relation symbols, and a constant symbol for 0. The (well-formed) formulas of the language of first-order arithmetic are built up from these symbols together with the logical symbols in the usual manner of first-order logic.

The structure N is defined to be a model of Peano arithmetic as follows.

This structure is known as the standard model or intended interpretation of first-order arithmetic.

A sentence in the language of first-order arithmetic is said to be true in N if it is true in the structure just defined. The notation N ⊨ φ is used to indicate that the sentence φ is true in N .

True arithmetic is defined to be the set of all sentences in the language of first-order arithmetic that are true in N , written Th( N ). This set is, equivalently, the (complete) theory of the structure N (see theories associated with a structure).

Arithmetic undefinability

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

Here # ( θ ) _ is the numeral of the canonical Gödel number of the sentence θ.

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

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

Computability properties

As discussed above, Th( N ) is not arithmetically definable, by Tarski's theorem. A corollary of Post's theorem establishes that the Turing degree of Th( N ) is 0^(ω), and so Th( N ) is not decidable nor recursively enumerable.

Th( N ) is closely related to the theory Th( R ) of the recursively enumerable Turing degrees, in the signature of partial orders (Shore 1999:184). In particular, there are computable functions S and T such that:

Model-theoretic properties

True arithmetic is an unstable theory, and so has 2 κ models for each uncountable cardinal κ . As there are continuum many types over the empty set, true arithmetic also has 2 ℵ 0 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 N and whose second-order part consists of every subset of N .

The true theory of first-order arithmetic, Th( N ), is a subset of the true theory of second order arithmetic, and Th( N ) 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.

Simpson (1977) 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.