True arithmetic

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematical logic, true arithmetic is the set of all true statements about the arithmetic of natural numbers (Boolos, Burgess, and Jeffrey 2002:295). 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[edit]

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 φ 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} (see theories associated with a structure).

Arithmetic indefinability[edit]

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 formula  \varphi(x) in the language of first-order arithmetic such that, for every sentence θ in this language,

\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[edit]

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[edit]

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[edit]

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[edit]

  • Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002), Computability and logic (4th ed.), Cambridge University Press, ISBN 0-521-00758-5 .
  • 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 (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.), Logic, Semantics and Metamathematics, 1983.