True arithmetic

Template:Short description 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 $𝒩$ 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 $𝒩$ if it is true in the structure just defined. The notation $𝒩\models \phi$ is used to indicate that the sentence $\phi$ is true in $𝒩.$

True arithmetic is defined to be the set of all sentences in the language of first-order arithmetic that are true in $𝒩$, written Template:Nowrap. This set is, equivalently, the (complete) theory of the structure $𝒩$.

Arithmetic undefinability

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

$𝒩\models \theta \text{if and only if}𝒩\models \phi (\underset{\_}{\mathrm{\#}(\theta )}).$

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

$\text{Th}(𝒩)=\bigcup _{n\in \mathbb{N}}{\text{Th}}_n(𝒩)$

but no single formula can define Template:Nowrap for arbitrarily large n.

Computability properties

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

Template:Nowrap is closely related to the theory Template:Nowrap 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 Template:Nowrap if and only if S(φ) is in Template:Nowrap.
• For each sentence ψ in the signature of partial orders, ψ is in Template:Nowrap if and only if T(ψ) is in Template:Nowrap.

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^{{\mathrm{\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 $𝒩$ and whose second-order part consists of every subset of $\mathbb{N}$.

The true theory of first-order arithmetic, Template:Nowrap, is a subset of the true theory of second-order arithmetic, and Template:Nowrap 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.

Template:Harvtxt 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.

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". An English translation "The Concept of Truth in Formalized Languages" appears in Template:Citation

External links

• Template:MathWorld
• Template:MathWorld
• Template:MathWorld