True arithmetic
# True arithmetic

In mathematical logic, true arithmetic is the set of all true first-order statements about the arithmetic of natural numbers. This is the theory associated with the standard model of the Peano axioms in the language of the first-order Peano axioms. True arithmetic is occasionally called Skolem arithmetic, though this term usually refers to the different theory of natural numbers with multiplication.

## 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 ${\mathcal {N}}$ is defined to be a model of Peano arithmetic as follows.

* The domain of discourse is the set $\mathbb {N}$ of natural numbers,
* The symbol 0 is interpreted as the number 0,
* The function symbols are interpreted as the usual arithmetical operations on $\mathbb {N}$,
* The equality and less-than relation symbols are interpreted as the usual equality and order relation on $\mathbb {N}$.

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 ${\mathcal {N}}$ if it is true in the structure just defined. The notation ${\mathcal {N}}\models \varphi$ is used to indicate that the sentence $\varphi$ is true in ${\mathcal {N}}.$

True arithmetic is defined to be the set of all sentences in the language of first-order arithmetic that are true in ${\mathcal {N}}$, written Th(${\mathcal {N}}$). This set is, equivalently, the (complete) theory of the structure ${\mathcal {N}}$.

## Arithmetic undefinability

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

    ${\mathcal {N}}\models \theta \quad {\text{if and only if}}\quad {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).$

Here ${\underline {\#(\theta )}}$ 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(${\mathcal {N}}$) and the Turing degrees, using the arithmetical hierarchy. For each natural number n, let $Th_n($${\mathcal {N}}$) be the subset of Th(${\mathcal {N}}$) consisting of only sentences that are $\Sigma _{n}^{0}$ or lower in the arithmetical hierarchy. Post's theorem shows that, for each n, $Th_n($${\mathcal {N}}$) is arithmetically definable, but only by a formula of complexity higher than $\Sigma _{n}^{0}$. Thus no single formula can define Th(${\mathcal {N}}$), because

    ${\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})$

but no single formula can define $Th_n($${\mathcal {N}}$) for arbitrarily large n.

## Computability properties

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

Th(${\mathcal {N}}$) is closely related to the theory Th(${\mathcal {R}}$) 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 Th(${\mathcal {N}}$) if and only if S(φ) is in Th(${\mathcal {R}}$).
* For each sentence ψ in the signature of partial orders, ψ is in Th(${\mathcal {R}}$) if and only if T(ψ) is in Th(${\mathcal {N}}$).

## Model-theoretic properties

True arithmetic is an unstable theory, and so has $2^{\kappa }$ models for each uncountable cardinal $\kappa$. As there are continuum many types over the empty set, true arithmetic also has $2^{\aleph _{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 ${\mathcal {N}}$ and whose second-order part consists of every subset of $\mathbb {N}$.

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

