True arithmetic

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

• The domain of discourse is the set ${\displaystyle \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 ${\displaystyle \mathbb {N} }$,
• The equality and less-than relation symbols are interpreted as the usual equality and order relation on ${\displaystyle \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 ${\displaystyle {\mathcal {N}}}$ if it is true in the structure just defined. The notation ${\displaystyle {\mathcal {N}}\models \varphi }$ is used to indicate that the sentence ${\displaystyle \varphi }$ is true in ${\displaystyle {\mathcal {N}}.}$

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

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

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

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

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

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

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

Th(${\displaystyle {\mathcal {N}}}$) is closely related to the theory Th(${\displaystyle {\mathcal {R}}}$) of the recursively enumerable Turing degrees, in the signature of partial orders.[3] In particular, there are computable functions S and T such that:

• For each sentence φ in the signature of first-order arithmetic, φ is in Th(${\displaystyle {\mathcal {N}}}$) if and only if S(φ) is in Th(${\displaystyle {\mathcal {R}}}$).
• For each sentence ψ in the signature of partial orders, ψ is in Th(${\displaystyle {\mathcal {R}}}$) if and only if T(ψ) is in Th(${\displaystyle {\mathcal {N}}}$).

True arithmetic is an unstable theory, and so has ${\displaystyle 2^{\kappa }}$ models for each uncountable cardinal ${\displaystyle \kappa }$. As there are continuum many types over the empty set, true arithmetic also has ${\displaystyle 2^{\aleph _{0}}}$ countable models. Since the theory is complete, all of its models are elementarily equivalent.

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

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

• Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002), Computability and logic (4th ed.), Cambridge University Press, ISBN 978-0-521-00758-0.
• Bovykin, Andrey; Kaye, Richard (2001), "On order-types of models of arithmetic", in Zhang, Yi (ed.), Logic and algebra, Contemporary Mathematics, vol. 302, American Mathematical Society, pp. 275–285, ISBN 978-0-8218-2984-4.
• Shore, Richard (2011), "The recursively enumerable degrees", in Griffor, E.R. (ed.), Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland (published 1999), pp. 169–197, ISBN 978-0-444-54701-9.
• Simpson, Stephen G. (1977), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics, Second Series, Annals of Mathematics, 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435
• Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". An English translation "The Concept of Truth in Formalized Languages" appears in Corcoran, J., ed. (1983), Logic, Semantics and Metamathematics: Papers from 1923 to 1938 (2nd ed.), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

• Weisstein, Eric W. "Arithmetic". MathWorld.
• Weisstein, Eric W. "Peano Arithmetic". MathWorld.
• Weisstein, Eric W. "Tarski's Theorem". MathWorld.