Inmathematical logic,true arithmetic is the set of all truefirst-order statements about thearithmetic ofnatural numbers.^[1] This is the theoryassociated with thestandard model of thePeano axioms in thelanguage of the first-order Peano axioms.True arithmetic is occasionally called Skolem arithmetic, though this term usually refers to thedifferent theory of natural numbers with multiplication.

Thesignature ofPeano 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 thelanguage of first-order arithmetic are built up from these symbols together with the logical symbols in the usual manner offirst-order logic.

Thestructure${\displaystyle \mathcal{N}}$ is defined to be a model of Peano arithmetic as follows.

• Thedomain 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 thestandard model orintended interpretation of first-order arithmetic.

Asentence 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 \phi }$ is used to indicate that the sentence${\displaystyle \phi }$ 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}}$, writtenTh(${\displaystyle \mathcal{N}}$). This set is, equivalently, the (complete) theory of the structure${\displaystyle \mathcal{N}}$.^[2]

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

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

Here${\displaystyle \underset{\_}{\mathrm{\#}(\theta )}}$ is the numeral of the canonicalGödel number of the sentenceθ.

Post's theorem is a sharper version of the undefinability theorem that shows a relationship between the definability ofTh(${\displaystyle \mathcal{N}}$) and theTuring degrees, using thearithmetical hierarchy. For each natural numbern, letTh_n(${\displaystyle \mathcal{N}}$) be the subset ofTh(${\displaystyle \mathcal{N}}$) consisting of only sentences that are${\displaystyle {\mathrm{\Sigma }}_n^0}$ or lower in the arithmetical hierarchy. Post's theorem shows that, for eachn,Th_n(${\displaystyle \mathcal{N}}$) is arithmetically definable, but only by a formula of complexity higher than${\displaystyle {\mathrm{\Sigma }}_n^0}$. Thus no single formula can defineTh(${\displaystyle \mathcal{N}}$), because

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

but no single formula can defineTh_n(${\displaystyle \mathcal{N}}$) for arbitrarily largen.

As discussed above,Th(${\displaystyle \mathcal{N}}$) is not arithmetically definable, by Tarski's theorem. A corollary of Post's theorem establishes that theTuring degree ofTh(${\displaystyle \mathcal{N}}$) is0^(ω), and soTh(${\displaystyle \mathcal{N}}$) is notdecidable norrecursively enumerable.

Th(${\displaystyle \mathcal{N}}$) is closely related to the theoryTh(${\displaystyle \mathcal{R}}$) of therecursively enumerable Turing degrees, in the signature ofpartial orders.^[3] In particular, there are computable functionsS andT such that:

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

True arithmetic is anunstable theory, and so has${\displaystyle 2^{\kappa }}$ models for each uncountable cardinal${\displaystyle \kappa }$. As there arecontinuum manytypes over the empty set, true arithmetic also has${\displaystyle 2^{{\mathrm{\aleph }}_0}}$ countable models. Since the theory iscomplete, all of its models areelementarily equivalent.

The true theory of second-order arithmetic consists of all the sentences in the language ofsecond-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, andTh(${\displaystyle \mathcal{N}}$) is definable in second-order arithmetic. However, the generalization of Post's theorem to theanalytical 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 allTuring degrees, in the signature of partial orders, andvice 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,105 (1), Annals of Mathematics: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 inCorcoran, 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.

• Model theory
• Formal theories of arithmetic

• Articles with short description
• Short description is different from Wikidata