Induction, bounding and least number principles

<h2 id="definitions">Definitions</h2>
Informally, for a <a href="/facts/First-order_logic/lcISqWIg">first-order</a> <a href="/facts/Well-formed_formula/YpTVlzuj">formula</a> of arithmetic 
 
 
 
 φ
 (
 x
 )
 
 
 {\displaystyle \varphi (x)}
 
 with one free variable, the induction principle for 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 expresses the validity of <a href="/facts/Mathematical_induction/KxAPqNrH">mathematical induction</a> over 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
, while the least number principle for 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 asserts that if 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 has a <a href="/facts/Witness_(mathematics)/H4JXNTHw">witness</a>, it has a least one. For a formula 
 
 
 
 ψ
 (
 x
 ,
 y
 )
 
 
 {\displaystyle \psi (x,y)}
 
 in two free variables, the bounding principle for 
 
 
 
 ψ
 
 
 {\displaystyle \psi }
 
 states that, for a fixed bound 
 
 
 
 k
 
 
 {\displaystyle k}
 
, if for every 
 
 
 
 n
 <
 k
 
 
 {\displaystyle n<k}
 
 there is 
 
 
 
 
 m
 
 n
 
 
 
 
 {\displaystyle m_{n}}
 
 such that 
 
 
 
 ψ
 (
 n
 ,
 
 m
 
 n
 
 
 )
 
 
 {\displaystyle \psi (n,m_{n})}
 
, then we can find a bound on the 
 
 
 
 
 m
 
 n
 
 
 
 
 {\displaystyle m_{n}}
 
's.
Formally, the induction principle for 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 is the sentence:<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

I
          
        
        φ
        :
        
        
          
            [
          
        
        φ
        (
        0
        )
        ∧
        ∀
        x
        
          
            (
          
        
        φ
        (
        x
        )
        →
        φ
        (
        x
        +
        1
        )
        
          
            )
          
        
        
          
            ]
          
        
        →
        ∀
        x
         
        φ
        (
        x
        )
      
    
    {\displaystyle {\mathsf {I}}\varphi :\quad {\big [}\varphi (0)\land \forall x{\big (}\varphi (x)\to \varphi (x+1){\big )}{\big ]}\to \forall x\ \varphi (x)}

There is a similar <a href="/facts/Mathematical_induction/KxAPqNrH">strong induction</a> principle for 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
:<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

I
 
 
 ′
 
 φ
 :
 
 ∀
 x
 
 
 [
 
 
 
 
 (
 
 
 ∀
 y
 <
 x
  
  
 φ
 (
 y
 )
 
 
 )
 
 
 →
 φ
 (
 x
 )
 
 
 ]
 
 
 →
 ∀
 x
  
 φ
 (
 x
 )
 
 
 {\displaystyle {\mathsf {I}}'\varphi :\quad \forall x{\big [}{\big (}\forall y<x\ \ \varphi (y){\big )}\to \varphi (x){\big ]}\to \forall x\ \varphi (x)}

The least number principle for 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 is the sentence:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

L
 
 
 φ
 :
 
 ∃
 x
  
 φ
 (
 x
 )
 →
 ∃
 
 x
 ′
 
 
 
 (
 
 
 φ
 (
 
 x
 ′
 
 )
 ∧
 ∀
 y
 <
 
 x
 ′
 
  
 
 ¬
 φ
 (
 y
 )
 
 
 )
 
 
 
 
 {\displaystyle {\mathsf {L}}\varphi :\quad \exists x\ \varphi (x)\to \exists x'{\big (}\varphi (x')\land \forall y<x'\ \,\lnot \varphi (y){\big )}}

Finally, the bounding principle for 
 
 
 
 ψ
 
 
 {\displaystyle \psi }
 
 is the sentence:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

B
 
 
 ψ
 :
 
 ∀
 u
 
 
 [
 
 
 
 
 (
 
 
 ∀
 x
 <
 u
  
 
 ∃
 y
  
 
 ψ
 (
 x
 ,
 y
 )
 
 
 )
 
 
 →
 ∃
 v
  
 
 ∀
 x
 <
 u
  
 
 ∃
 y
 <
 v
  
 
 ψ
 (
 x
 ,
 y
 )
 
 
 ]
 
 
 
 
 {\displaystyle {\mathsf {B}}\psi :\quad \forall u{\big [}{\big (}\forall x<u\ \,\exists y\ \,\psi (x,y){\big )}\to \exists v\ \,\forall x<u\ \,\exists y<v\ \,\psi (x,y){\big ]}}

More commonly, we consider these principles not just for a single formula, but for a class of formulae in the <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical hierarchy</a>. For example, 
 
 
 
 
 
 I
 
 
 
 Σ
 
 2
 
 
 
 
 {\displaystyle {\mathsf {I}}\Sigma _{2}}
 
 is the <a href="/facts/Axiom_schema/vKNTz5IT">axiom schema</a> consisting of 
 
 
 
 
 
 I
 
 
 φ
 
 
 {\displaystyle {\mathsf {I}}\varphi }
 
 for every 
 
 
 
 
 Σ
 
 2
 
 
 
 
 {\displaystyle \Sigma _{2}}
 
 formula 
 
 
 
 φ
 (
 x
 )
 
 
 {\displaystyle \varphi (x)}
 
 in one free variable.

<h2 id="nonstandard-models">Nonstandard models</h2>
It may seem that the principles 
 
 
 
 
 
 I
 
 
 φ
 
 
 {\displaystyle {\mathsf {I}}\varphi }
 
, 
 
 
 
 
 
 
 I
 
 
 ′
 
 φ
 
 
 {\displaystyle {\mathsf {I}}'\varphi }
 
, 
 
 
 
 
 
 L
 
 
 φ
 
 
 {\displaystyle {\mathsf {L}}\varphi }
 
, 
 
 
 
 
 
 B
 
 
 ψ
 
 
 {\displaystyle {\mathsf {B}}\psi }
 
 are trivial, and indeed, they hold for all formulae 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
, 
 
 
 
 ψ
 
 
 {\displaystyle \psi }
 
 in the <a href="/facts/Natural_number/u65og8JE">standard model of arithmetic</a> 
 
 
 
 
 N
 
 
 
 {\displaystyle \mathbb {N} }
 
. However, they become more relevant in nonstandard models. Recall that a nonstandard model of arithmetic has the form 
 
 
 
 
 N
 
 +
 
 Z
 
 ⋅
 K
 
 
 {\displaystyle \mathbb {N} +\mathbb {Z} \cdot K}
 
 for some linear order 
 
 
 
 K
 
 
 {\displaystyle K}
 
. In other words, it consists of an initial copy of 
 
 
 
 
 N
 
 
 
 {\displaystyle \mathbb {N} }
 
, whose elements are called finite or standard, followed by many copies of 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
 arranged in the shape of 
 
 
 
 K
 
 
 {\displaystyle K}
 
, whose elements are called infinite or nonstandard.
Now, considering the principles 
 
 
 
 
 
 I
 
 
 φ
 
 
 {\displaystyle {\mathsf {I}}\varphi }
 
, 
 
 
 
 
 
 
 I
 
 
 ′
 
 φ
 
 
 {\displaystyle {\mathsf {I}}'\varphi }
 
, 
 
 
 
 
 
 L
 
 
 φ
 
 
 {\displaystyle {\mathsf {L}}\varphi }
 
, 
 
 
 
 
 
 B
 
 
 ψ
 
 
 {\displaystyle {\mathsf {B}}\psi }
 
 in a nonstandard model 
 
 
 
 
 
 M
 
 
 
 
 {\displaystyle {\mathcal {M}}}
 
, we can see how they might fail. For example, the hypothesis of the induction principle 
 
 
 
 
 
 I
 
 
 φ
 
 
 {\displaystyle {\mathsf {I}}\varphi }
 
 only ensures that 
 
 
 
 φ
 (
 x
 )
 
 
 {\displaystyle \varphi (x)}
 
 holds for all elements in the standard part of 
 
 
 
 
 
 M
 
 
 
 
 {\displaystyle {\mathcal {M}}}
 
 - it may not hold for the nonstandard elements, who can't be reached by iterating the successor operation from zero. Similarly, the bounding principle 
 
 
 
 
 
 B
 
 
 ψ
 
 
 {\displaystyle {\mathsf {B}}\psi }
 
 might fail if the bound 
 
 
 
 u
 
 
 {\displaystyle u}
 
 is nonstandard, as then the (infinite) collection of 
 
 
 
 y
 
 
 {\displaystyle y}
 
 could be <a href="/facts/Cofinal_(mathematics)/l5Hoqx3o">cofinal</a> in 
 
 
 
 
 
 M
 
 
 
 
 {\displaystyle {\mathcal {M}}}
 
.

<h2 id="relations-between-the-principles">Relations between the principles</h2>

The following relations hold between the principles (over the weak base theory 
 
 
 
 
 
 
 P
 A
 
 
 
 −
 
 
 +
 
 
 I
 
 
 
 Σ
 
 0
 
 
 
 
 {\displaystyle {\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}}
 
):<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<ul><li>
 
 
 
 
 
 
 I
 
 
 ′
 
 φ
 ≡
 
 
 L
 
 
 ¬
 φ
 
 
 {\displaystyle {\mathsf {I}}'\varphi \equiv {\mathsf {L}}\lnot \varphi }
 
 for every formula 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
;</li>
<li>
 
 
 
 
 
 I
 
 
 
 Σ
 
 n
 
 
 ≡
 
 
 I
 
 
 
 Π
 
 n
 
 
 ≡
 
 
 
 I
 
 
 ′
 
 
 Σ
 
 n
 
 
 ≡
 
 
 
 I
 
 
 ′
 
 
 Π
 
 n
 
 
 ≡
 
 
 L
 
 
 
 Σ
 
 n
 
 
 ≡
 
 
 L
 
 
 
 Π
 
 n
 
 
 
 
 {\displaystyle {\mathsf {I}}\Sigma _{n}\equiv {\mathsf {I}}\Pi _{n}\equiv {\mathsf {I}}'\Sigma _{n}\equiv {\mathsf {I}}'\Pi _{n}\equiv {\mathsf {L}}\Sigma _{n}\equiv {\mathsf {L}}\Pi _{n}}
 
;</li>
<li>
 
 
 
 
 
 I
 
 
 
 Σ
 
 n
 +
 1
 
 
 
 ⟹
 
 
 
 B
 
 
 
 Σ
 
 n
 +
 1
 
 
 
 ⟹
 
 
 
 I
 
 
 
 Σ
 
 n
 
 
 
 
 {\displaystyle {\mathsf {I}}\Sigma _{n+1}\implies {\mathsf {B}}\Sigma _{n+1}\implies {\mathsf {I}}\Sigma _{n}}
 
, and both implications are strict;</li>
<li>
 
 
 
 
 
 B
 
 
 
 Σ
 
 n
 +
 1
 
 
 ≡
 
 
 B
 
 
 
 Π
 
 n
 
 
 ≡
 
 
 L
 
 
 
 Δ
 
 n
 +
 1
 
 
 
 
 {\displaystyle {\mathsf {B}}\Sigma _{n+1}\equiv {\mathsf {B}}\Pi _{n}\equiv {\mathsf {L}}\Delta _{n+1}}
 
;</li>
<li>
 
 
 
 
 
 L
 
 
 
 Δ
 
 n
 
 
 
 ⟹
 
 
 
 I
 
 
 
 Δ
 
 n
 
 
 
 
 {\displaystyle {\mathsf {L}}\Delta _{n}\implies {\mathsf {I}}\Delta _{n}}
 
, but it is not known if this reverses.</li></ul>
Over 
 
 
 
 
 
 
 P
 A
 
 
 
 −
 
 
 +
 
 
 I
 
 
 
 Σ
 
 0
 
 
 +
 
 
 e
 x
 p
 
 
 
 
 {\displaystyle {\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}+{\mathsf {exp}}}
 
, <a href="/facts/Theodore_Slaman/qFh41Gy9">Slaman</a> proved that 
 
 
 
 
 
 B
 
 
 
 Σ
 
 n
 
 
 ≡
 
 
 L
 
 
 
 Δ
 
 n
 
 
 ≡
 
 
 I
 
 
 
 Δ
 
 n
 
 
 
 
 {\displaystyle {\mathsf {B}}\Sigma _{n}\equiv {\mathsf {L}}\Delta _{n}\equiv {\mathsf {I}}\Delta _{n}}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="reverse-mathematics">Reverse mathematics</h2>
The induction, bounding and least number principles are commonly used in <a href="/facts/Reverse_mathematics/nHLm6JUQ">reverse mathematics</a> and <a href="/facts/Second-order_arithmetic/abBxQsaH">second-order arithmetic</a>. For example, 
 
 
 
 
 
 I
 
 
 
 Σ
 
 1
 
 
 
 
 {\displaystyle {\mathsf {I}}\Sigma _{1}}
 
 is part of the definition of the subsystem 
 
 
 
 
 
 
 R
 C
 A
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathsf {RCA}}_{0}}
 
 of second-order arithmetic. Hence, 
 
 
 
 
 
 
 I
 
 
 ′
 
 
 Σ
 
 1
 
 
 
 
 {\displaystyle {\mathsf {I}}'\Sigma _{1}}
 
, 
 
 
 
 
 
 L
 
 
 
 Σ
 
 1
 
 
 
 
 {\displaystyle {\mathsf {L}}\Sigma _{1}}
 
 and 
 
 
 
 
 
 B
 
 
 
 Σ
 
 1
 
 
 
 
 {\displaystyle {\mathsf {B}}\Sigma _{1}}
 
 are all theorems of 
 
 
 
 
 
 
 R
 C
 A
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathsf {RCA}}_{0}}
 
. The subsystem 
 
 
 
 
 
 
 A
 C
 A
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathsf {ACA}}_{0}}
 
 proves all the principles 
 
 
 
 
 
 I
 
 
 φ
 
 
 {\displaystyle {\mathsf {I}}\varphi }
 
, 
 
 
 
 
 
 
 I
 
 
 ′
 
 φ
 
 
 {\displaystyle {\mathsf {I}}'\varphi }
 
, 
 
 
 
 
 
 L
 
 
 φ
 
 
 {\displaystyle {\mathsf {L}}\varphi }
 
, 
 
 
 
 
 
 B
 
 
 ψ
 
 
 {\displaystyle {\mathsf {B}}\psi }
 
 for <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical</a> 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
, 
 
 
 
 ψ
 
 
 {\displaystyle \psi }
 
. The infinite pigeonhole principle is known to be equivalent to 
 
 
 
 
 
 B
 
 
 
 Π
 
 1
 
 
 
 
 {\displaystyle {\mathsf {B}}\Pi _{1}}
 
 and 
 
 
 
 
 
 B
 
 
 
 Σ
 
 2
 
 
 
 
 {\displaystyle {\mathsf {B}}\Sigma _{2}}
 
 over 
 
 
 
 
 
 
 R
 C
 A
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathsf {RCA}}_{0}}
 
.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

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

<ol>
<li id="fn:1">Hájek, Petr; Pudlák, Pavel (2016). Metamathematics of First-Order Arithmetic. Association for Symbolic Logic c/- Cambridge University Press. ISBN 978-1-107-16841-1. OCLC 1062334376. <a href="978-1-107-16841-1" target="_blank">978-1-107-16841-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hájek, Petr; Pudlák, Pavel (2016). Metamathematics of First-Order Arithmetic. Association for Symbolic Logic c/- Cambridge University Press. ISBN 978-1-107-16841-1. OCLC 1062334376. <a href="978-1-107-16841-1" target="_blank">978-1-107-16841-1</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hájek, Petr; Pudlák, Pavel (2016). Metamathematics of First-Order Arithmetic. Association for Symbolic Logic c/- Cambridge University Press. ISBN 978-1-107-16841-1. OCLC 1062334376. <a href="978-1-107-16841-1" target="_blank">978-1-107-16841-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Hájek, Petr; Pudlák, Pavel (2016). Metamathematics of First-Order Arithmetic. Association for Symbolic Logic c/- Cambridge University Press. ISBN 978-1-107-16841-1. OCLC 1062334376. <a href="978-1-107-16841-1" target="_blank">978-1-107-16841-1</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Hájek, Petr; Pudlák, Pavel (2016). Metamathematics of First-Order Arithmetic. Association for Symbolic Logic c/- Cambridge University Press. ISBN 978-1-107-16841-1. OCLC 1062334376. <a href="978-1-107-16841-1" target="_blank">978-1-107-16841-1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Paris, J.B.; Kirby, L.A.S. (1978), "Σn-Collection Schemas in Arithmetic", Logic Colloquium '77, Elsevier, pp. 199–209, doi:10.1016/s0049-237x(08)72003-2, ISBN 978-0-444-85178-9, retrieved 2021-04-14 <a href="978-0-444-85178-9" target="_blank">978-0-444-85178-9</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Slaman, Theodore A. (2004-08-01). "
 
 
 
 
 Σ
 
 n
 
 
 
 
 {\displaystyle \Sigma _{n}}
 
-bounding and 
 
 
 
 
 Δ
 
 n
 
 
 
 
 {\displaystyle \Delta _{n}}
 
-induction". Proceedings of the American Mathematical Society. 132 (8): 2449. doi:10.1090/s0002-9939-04-07294-6. ISSN 0002-9939. <a href="https://doi.org/10.1090%2Fs0002-9939-04-07294-6" target="_blank">https://doi.org/10.1090%2Fs0002-9939-04-07294-6</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Hirst, Jeffry (August 1987). Combinatorics in Subsystems of Second Order Arithmetic (PhD). Pennsylvania State University. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Induction, bounding and least number principles open-in-new

Induction, bounding and least number principles