True arithmetic#True theory of second-order 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 $\backslash mathcal\{N\}$ is defined to be a model of Peano arithmetic as follows.

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

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

The central result on true arithmetic is the undefinability theorem of Alfred Tarski (1936). It states that

the set {{nowrap|1=Th($\backslash mathcal\{N\}$)}} is not arithmetically definable. This means that there is no formula $\backslash varphi(x)$ in the language of first-order arithmetic such that, for every sentence θ in this language,

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

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

:$\backslash mbox\{Th\}(\backslash mathcal\{N\})\; =\; \backslash bigcup\_\{n\; \backslash in\; \backslash mathbb\{N\}\}\; \backslash mbox\{Th\}\_n(\backslash mathcal\{N\})$

but no single formula can define {{nowrap|1=Th_n($\backslash mathcal\{N\}$)}} for arbitrarily large n.

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

{{nowrap|1=Th($\backslash mathcal\{N\}$)}} is closely related to the theory {{nowrap|1=Th($\backslash mathcal\{R\}$)}} of the recursively enumerable Turing degrees, in the signature of partial orders.{{Harvnb|Shore|2011|p=184}} In particular, there are computable functions S and T such that:

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

True arithmetic is an unstable theory, and so has $2^\backslash kappa$ models for each uncountable cardinal $\backslash kappa$. As there are continuum many types over the empty set, true arithmetic also has $2^\{\backslash 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 $\backslash mathcal\{N\}$ and whose second-order part consists of every subset of $\backslash mathbb\{N\}$.

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

{{Harvtxt|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.

{{Reflist|2}}

• {{citation

| last1=Boolos

| first1=George

|author1link = George Boolos

| last2=Burgess

|author2link = John P. Burgess

| first2=John P.

| last3=Jeffrey

| first3=Richard C.

|author3link = Richard Jeffrey

| title=Computability and logic

| edition=4th

| publisher=Cambridge University Press

| year=2002

| isbn=978-0-521-00758-0

}}.

• {{Citation

| last1=Bovykin

| first1=Andrey

| last2=Kaye

| first2=Richard

| chapter=On order-types of models of arithmetic

| year=2001

| editor-last=Zhang

| editor-first=Yi

| title=Logic and algebra

| series=Contemporary Mathematics

| volume=302

| publisher=American Mathematical Society

| publication-date=2001

| pages=275–285

| isbn=978-0-8218-2984-4

}}.

• {{Citation

| last1=Shore

| first1=Richard

|authorlink = Richard Shore

| chapter=The recursively enumerable degrees

| year=2011

| editor-last=Griffor

| editor-first=E.R.

| title=Handbook of Computability Theory

| series=Studies in Logic and the Foundations of Mathematics

| volume=140

| publisher=North-Holland

| publication-date=1999

| pages=169–197

| isbn=978-0-444-54701-9

}}.

• {{Citation

| last1=Simpson

| first1=Stephen G.

|authorlink = Steve Simpson (mathematician)

| title=First-order theory of the degrees of recursive unsolvability

| mr=0432435

| year=1977

| journal=Annals of Mathematics |series=Second Series

| issn=0003-486X

| volume=105

| pages=121–139

| doi=10.2307/1971028

| jstor=1971028

| issue=1

| publisher=Annals of Mathematics

}}

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

| editor-last=Corcoran

| editor-first=J.

| title=Logic, Semantics and Metamathematics: Papers from 1923 to 1938

| year=1983

| edition=2nd

| publisher=Hackett Publishing Company, Inc.

| isbn=978-0-915144-75-4

}}

• {{MathWorld|title=Arithmetic|urlname=Arithmetic}}
• {{MathWorld|title=Peano Arithmetic|urlname=PeanoArithmetic}}
• {{MathWorld|title=Tarski's Theorem|urlname=TarskisTheorem}}

Category:Model theory

Category:Formal theories of arithmetic