# True arithmetic: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

# Encyclopedia

In mathematical logic, true arithmetic is the theory Th($\mathcal{N}$) of the natural numbers in the language of first-order Peano arithmetic (Boolos, Burgess, and Jeffrey 2002:295). Tarski's indefinability theorem shows that this theory is not arithmetically definable.

## 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 in this signature are built up in the the usual manner of first-order logic. The language of first-order arithmetic consists of all the well-formed formulas in this signature.

The structure $\mathcal{N}$ is a model of Peano arithmetic defined 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 φ is true in $\mathcal{N}.$

True arithmetic is the set Th($\mathcal{N}$) of all sentences in the language of first-order arithmetic that are true in $\mathcal{N}$. This set is, equivalently, the (complete) theory of the structure $\mathcal{N}$ (see theories associated with a structure).

## Arithmetic indefinability

The central result on true arithmetic is the indefinability theorem of Alfred Tarski (1936). It states that the set Th($\mathcal{N}$) 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,

$\mathcal{N} \models \theta \qquad$ if and only if $\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 indefinability 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 Thn($\mathcal{N}$) be the subset of Th($\mathcal{N}$) consisting of only sentences that are $\Sigma^0_n$ or lower in the arithmetical hierarchy. Post's theorem shows that, for each n, Thn($\mathcal{N}$) is arithmetically definable, but only by a formula of complexity higher than $\Sigma^0_n$. 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 Thn($\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 (Shore 1999:184). 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κ models for each uncountable cardinal κ. 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.

## References

• Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002), Computability and logic (4th ed.), Cambridge University Press, ISBN 0521007585  .
• Bovykin, Andrey; Kaye, Richard (2001), "On order-types of models of arithmetic", in Zhang, Yi, Logic and algebra, Contemporary Mathematics, 302, American Mathematical Society, pp. 275–285  .
• Shore, Richard (1999), "The recursively enumerable degrees", in Griffor, E.R., Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics, 140, North-Holland, pp. 169–197  .
• Simpson, Stephen G. (1977), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics. Second Series 105: 121–139, doi:10.2307/1971028, MR0432435, ISSN 0003-486X
• Tarksi, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". An English translation "The Concept of Truth in Formalized Languages" appears in in Corcoran, J., (ed.), Logic, Semantics and Metamathematics, 1983.