True arithmetic

<h2 id="definition">Definition</h2>
The <a href="/facts/Signature_(logic)/C0YQCuce">signature</a> of <a href="/facts/Peano_arithmetic/DhhDnNug">Peano arithmetic</a> 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 <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a>.
The <a href="/facts/Structure_(mathematical_logic)/GsMx1fEb">structure</a> 
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
 is defined to be a model of Peano arithmetic as follows.

<ul><li>The <a href="/facts/Domain_of_discourse/T1WRQxx6">domain of discourse</a> is the set 
 
 
 
 
 N
 
 
 
 {\displaystyle \mathbb {N} }
 
 of natural numbers,</li>
<li>The symbol 0 is interpreted as the number 0,</li>
<li>The function symbols are interpreted as the usual arithmetical operations on 
 
 
 
 
 N
 
 
 
 {\displaystyle \mathbb {N} }
 
,</li>
<li>The equality and less-than relation symbols are interpreted as the usual equality and order relation on 
 
 
 
 
 N
 
 
 
 {\displaystyle \mathbb {N} }
 
.</li></ul>
This structure is known as the <a href="/facts/Nonstandard_arithmetic/e3EktWqv">standard model</a> or <a href="/facts/Intended_interpretation/goPmjjQG">intended interpretation</a> of first-order arithmetic.
A <a href="/facts/Sentence_(mathematical_logic)/lnsLzvTx">sentence</a> in the language of first-order arithmetic is said to be true in 
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
 if it is true in the structure just defined. The notation 
 
 
 
 
 
 N
 
 
 ⊨
 φ
 
 
 {\displaystyle {\mathcal {N}}\models \varphi }
 
 is used to indicate that the sentence 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 is true in 
 
 
 
 
 
 N
 
 
 .
 
 
 {\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 
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
, written Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
). This set is, equivalently, the (complete) theory of the structure 
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="arithmetic-undefinability">Arithmetic undefinability</h2>
The central result on true arithmetic is the <a href="/facts/Tarski%27s_undefinability_theorem/T9LgFkVx">undefinability theorem</a> of <a href="/facts/Alfred_Tarski/7h6NySAj">Alfred Tarski</a> (1936). It states that 
the set Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is not arithmetically definable. This means that there is no formula 
 
 
 
 φ
 (
 x
 )
 
 
 {\displaystyle \varphi (x)}
 
 in the language of first-order arithmetic such that, for every sentence θ in this language,

N
          
        
        ⊨
        θ
        
        
          if and only if
        
        
        
          
            N
          
        
        ⊨
        φ
        (
        
          
            
              #
              (
              θ
              )
            
            _
          
        
        )
        .
      
    
    {\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 <a href="/facts/G%C3%B6del_number/36BpTK1g">Gödel number</a> of the sentence θ.
<a href="/facts/Post%27s_theorem/wPId3E7D">Post's theorem</a> is a sharper version of the undefinability theorem that shows a relationship between the definability of Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) and the <a href="/facts/Turing_degree/yDkWYeT1">Turing degrees</a>, using the <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical hierarchy</a>. For each natural number n, let Thn(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) be the subset of Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) consisting of only sentences that are 
 
 
 
 
 Σ
 
 n
 
 
 0
 
 
 
 
 {\displaystyle \Sigma _{n}^{0}}
 
 or lower in the arithmetical hierarchy. Post's theorem shows that, for each n, Thn(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is arithmetically definable, but only by a formula of complexity higher than 
 
 
 
 
 Σ
 
 n
 
 
 0
 
 
 
 
 {\displaystyle \Sigma _{n}^{0}}
 
. Thus no single formula can define Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
), because

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

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

<h2 id="computability-properties">Computability properties</h2>
As discussed above, Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is not arithmetically definable, by Tarski's theorem. A corollary of Post's theorem establishes that the <a href="/facts/Turing_degree/yDkWYeT1">Turing degree</a> of Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is 0(ω), and so Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is not <a href="/facts/Decidable_set/rsnT9cLn">decidable</a> nor <a href="/facts/Recursively_enumerable_set/lpzr8jHn">recursively enumerable</a>.
Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is closely related to the theory Th(
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {R}}}
 
) of the <a href="/facts/Recursively_enumerable_Turing_degree/yDkWYeT1">recursively enumerable Turing degrees</a>, in the signature of <a href="/facts/Partial_order/qb4a3FAX">partial orders</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> In particular, there are computable functions S and T such that:

<ul><li>For each sentence φ in the signature of first-order arithmetic, φ is in Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) if and only if S(φ) is in Th(
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {R}}}
 
).</li>
<li>For each sentence ψ in the signature of partial orders, ψ is in Th(
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {R}}}
 
) if and only if T(ψ) is in Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
).</li></ul>
<h2 id="model-theoretic-properties">Model-theoretic properties</h2>
True arithmetic is an <a href="/facts/Stable_theory/0bVGhbeK">unstable theory</a>, and so has 
 
 
 
 
 2
 
 κ
 
 
 
 
 {\displaystyle 2^{\kappa }}
 
 models for each uncountable cardinal 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
. As there are <a href="/facts/Cardinality_of_the_continuum/ob578Q9l">continuum</a> many <a href="/facts/Type_(model_theory)/nuUHGFcg">types</a> over the empty set, true arithmetic also has 
 
 
 
 
 2
 
 
 ℵ
 
 0
 
 
 
 
 
 
 {\displaystyle 2^{\aleph _{0}}}
 
 countable models. Since the theory is <a href="/facts/Complete_theory/TfBN8Fnb">complete</a>, all of its models are <a href="/facts/Elementarily_equivalent/3C94AfFq">elementarily equivalent</a>.

<h2 id="true-theory-of-second-order-arithmetic">True theory of second-order arithmetic</h2>
The true theory of second-order arithmetic consists of all the sentences in the language of <a href="/facts/Second-order_arithmetic/abBxQsaH">second-order arithmetic</a> that are satisfied by the standard model of second-order arithmetic, whose first-order part is the structure 
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
 and whose second-order part consists of every subset of 
 
 
 
 
 N
 
 
 
 {\displaystyle \mathbb {N} }
 
.
The true theory of first-order arithmetic, Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
), is a subset of the true theory of second-order arithmetic, and Th(
 
 
 
 
 
 N
 
 
 
 
 {\displaystyle {\mathcal {N}}}
 
) is definable in second-order arithmetic. However, the generalization of Post's theorem to the <a href="/facts/Analytical_hierarchy/C9r61LzA">analytical hierarchy</a> 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 <a href="/facts/Turing_degree/yDkWYeT1">Turing degrees</a>, in the signature of partial orders, and vice versa.

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/George_Boolos/K969uIhT">Boolos, George</a>; <a href="/facts/John_P._Burgess/vVxaBgbr">Burgess, John P.</a>; <a href="/facts/Richard_Jeffrey/fL2rpek3">Jeffrey, Richard C.</a> (2002), Computability and logic (4th ed.), Cambridge University Press, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-00758-0.</li>
<li>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, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-8218-2984-4.</li>
<li><a href="/facts/Richard_Shore/UfqjaeAR">Shore, Richard</a> (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, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-444-54701-9.</li>
<li><a href="/facts/Steve_Simpson_(mathematician)/33WuyqGs">Simpson, Stephen G.</a> (1977), "First-order theory of the degrees of recursive unsolvability", <a href="/facts/Annals_of_Mathematics/CUYktUqD">Annals of Mathematics</a>, Second Series, 105 (1), Annals of Mathematics: 121–139, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1971028">10.2307/1971028</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0003-486X">0003-486X</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1971028">1971028</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0432435">0432435</a></li>
<li><a href="/facts/Alfred_Tarski/7h6NySAj">Tarski, Alfred</a> (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., <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-915144-75-4</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/Arithmetic.html">"Arithmetic"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/PeanoArithmetic.html">"Peano Arithmetic"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/TarskisTheorem.html">"Tarski's Theorem"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Boolos, Burgess & Jeffrey 2002, p. 295 - Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002), Computability and logic (4th ed.), Cambridge University Press, ISBN 978-0-521-00758-0 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">see theories associated with a structure <a href="/wiki/Theory_(mathematical_logic)#Theories_associated_with_a_structure" target="_blank">/wiki/Theory_(mathematical_logic)#Theories_associated_with_a_structure</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Shore 2011, p. 184 - 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 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

True arithmetic open-in-new

True arithmetic