Well-ordering principle

<h2 id="properties">Properties</h2>
<p>Depending on the framework in which the natural numbers are introduced, this (second-order) property of the set of natural numbers is either an <a href="/facts/Axiom/mLjP14Mc">axiom</a> or a provable theorem. For example:
</p>
<ul><li>In <a href="/facts/Peano_arithmetic/DhhDnNug">Peano arithmetic</a>, <a href="/facts/Second-order_arithmetic/abBxQsaH">second-order arithmetic</a> and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well-ordering principle, the principle is derived from the principle of <a href="/facts/Mathematical_induction/KxAPqNrH">mathematical induction</a>, which is itself taken as basic.</li>
<li>Considering the natural numbers as a subset of the real numbers, and assuming that we know already that the real numbers are complete (again, either as an axiom or a theorem about the <a href="/facts/Real_number/R02gw5Pb">real number</a> system), i.e., every bounded (from below) set has an infimum, then also every set 
  
    
      
        A
      
    
    {\displaystyle A}
  
 of natural numbers has an infimum, say 
  
    
      
        
          a
          
            ∗
          
        
      
    
    {\displaystyle a^{*}}
  
. We can now find an integer 
  
    
      
        
          n
          
            ∗
          
        
      
    
    {\displaystyle n^{*}}
  
 such that 
  
    
      
        
          a
          
            ∗
          
        
      
    
    {\displaystyle a^{*}}
  
 lies in the half-open interval 
  
    
      
        (
        
          n
          
            ∗
          
        
        −
        1
        ,
        
          n
          
            ∗
          
        
        ]
      
    
    {\displaystyle (n^{*}-1,n^{*}]}
  
, and can then show that we must have 
  
    
      
        
          a
          
            ∗
          
        
        =
        
          n
          
            ∗
          
        
      
    
    {\displaystyle a^{*}=n^{*}}
  
, and 
  
    
      
        
          n
          
            ∗
          
        
      
    
    {\displaystyle n^{*}}
  
 in <i>
  
    
      
        A
      
    
    {\displaystyle A}
  
</i>.</li>
<li>In <a href="/facts/Axiomatic_set_theory/1ptfsvUP">axiomatic set theory</a>, the natural numbers are defined as the smallest <a href="/facts/Inductive_set_(axiom_of_infinity)/kDWQE32v">inductive set</a> (i.e., set containing 0 and closed under the successor operation). One can (even without invoking the <a href="/facts/Axiom_of_regularity/sa121RjC">regularity axiom</a>) show that the set of all natural numbers 
  
    
      
        n
      
    
    {\displaystyle n}
  
 such that "
  
    
      
        {
        0
        ,
        …
        ,
        n
        }
      
    
    {\displaystyle \{0,\ldots ,n\}}
  
 is well-ordered" is inductive, and must therefore contain all natural numbers; from this property one can conclude that the set of all natural numbers is also well-ordered.</li></ul>
<p>In the second sense, this phrase is used when that proposition is relied on for the purpose of justifying proofs that take the following form: to prove that every natural number belongs to a specified set 
  
    
      
        S
      
    
    {\displaystyle S}
  
, assume the contrary, which implies that the set of counterexamples is non-empty and thus contains a smallest <a href="/facts/Counterexample/dnThYpHW">counterexample</a>.  Then show that for any counterexample there is a still smaller counterexample, producing a contradiction.  This mode of argument is the <a href="/facts/Contrapositive/ENPumbyv">contrapositive</a> of proof by <a href="/facts/Complete_induction/KxAPqNrH">complete induction</a>. It is known light-heartedly as the "<a href="/facts/Minimal_criminal/AjxAT6Vj">minimal criminal</a>" method and is similar in its nature to <a href="/facts/Fermat/FLbUh75u">Fermat's</a> method of "<a href="/facts/Infinite_descent/4640ySPA">infinite descent</a>".
</p><p><a href="/facts/Garrett_Birkhoff/5jeI7Wmr">Garrett Birkhoff</a> and <a href="/facts/Saunders_Mac_Lane/rjgUqfkA">Saunders Mac Lane</a> wrote in <i>A Survey of Modern Algebra</i> that this property, like the <a href="/facts/Least_upper_bound_axiom/tE5NLTT9">least upper bound axiom</a> for real numbers, is non-algebraic; i.e., it cannot be deduced from the algebraic properties of the integers (which form an ordered <a href="/facts/Integral_domain/cylt6zxW">integral domain</a>).
</p>
<h2 id="example-applications">Example applications</h2>
<p>The well-ordering principle can be used in the following proofs.
</p>
<h3>Prime factorization</h3>
<p>Theorem: <i>Every integer greater than one can be factored as a product of primes.</i> This theorem constitutes part of the <a href="/facts/Fundamental_Theorem_of_Arithmetic/EzHUwlXX">Prime Factorization Theorem</a>.
</p><p><i>Proof</i> (by well-ordering principle). Let 
  
    
      
        C
      
    
    {\displaystyle C}
  
 be the set of all integers greater than one that <i>cannot</i> be factored as a product of primes. We show that 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is empty.
</p><p>Assume for the sake of contradiction that 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is not empty. Then, by the well-ordering principle, there is a least element 
  
    
      
        n
        ∈
        C
      
    
    {\displaystyle n\in C}
  
; 
  
    
      
        n
      
    
    {\displaystyle n}
  
 cannot be prime since a <a href="/facts/Prime_number/L20FLkgn">prime number</a> itself is considered a length-one product of primes. By the definition of non-prime numbers, 
  
    
      
        n
      
    
    {\displaystyle n}
  
 has factors 
  
    
      
        a
        ,
        b
      
    
    {\displaystyle a,b}
  
, where 
  
    
      
        a
        ,
        b
      
    
    {\displaystyle a,b}
  
 are integers greater than one and less than 
  
    
      
        n
      
    
    {\displaystyle n}
  
. Since 
  
    
      
        a
        ,
        b
        <
        n
      
    
    {\displaystyle a,b<n}
  
, they are not in 
  
    
      
        C
      
    
    {\displaystyle C}
  
 as 
  
    
      
        n
      
    
    {\displaystyle n}
  
 is the smallest element of 
  
    
      
        C
      
    
    {\displaystyle C}
  
. So, 
  
    
      
        a
        ,
        b
      
    
    {\displaystyle a,b}
  
 can be factored as products of primes, where 
  
    
      
        a
        =
        
          p
          
            1
          
        
        
          p
          
            2
          
        
        .
        .
        .
        
          p
          
            k
          
        
      
    
    {\displaystyle a=p_{1}p_{2}...p_{k}}
  
 and 
  
    
      
        b
        =
        
          q
          
            1
          
        
        
          q
          
            2
          
        
        .
        .
        .
        
          q
          
            l
          
        
      
    
    {\displaystyle b=q_{1}q_{2}...q_{l}}
  
, meaning that 
  
    
      
        n
        =
        
          p
          
            1
          
        
        
          p
          
            2
          
        
        .
        .
        .
        
          p
          
            k
          
        
        ⋅
        
          q
          
            1
          
        
        
          q
          
            2
          
        
        .
        .
        .
        
          q
          
            l
          
        
      
    
    {\displaystyle n=p_{1}p_{2}...p_{k}\cdot q_{1}q_{2}...q_{l}}
  
, a product of primes. This contradicts the assumption that 
  
    
      
        n
        ∈
        C
      
    
    {\displaystyle n\in C}
  
, so the assumption that 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is nonempty must be false.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h3>Integer summation</h3>
<p>Theorem: 
  
    
      
        1
        +
        2
        +
        3
        +
        .
        .
        .
        +
        n
        =
        
          
            
              n
              (
              n
              +
              1
              )
            
            2
          
        
      
    
    {\displaystyle 1+2+3+...+n={\frac {n(n+1)}{2}}}
  
 for all positive integers 
  
    
      
        n
      
    
    {\displaystyle n}
  
.
</p><p><i>Proof</i>. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non-empty set of positive integers 
  
    
      
        C
        =
        {
        n
        ∈
        
          N
        
        ∣
        1
        +
        2
        +
        3
        +
        .
        .
        .
        +
        n
        ≠
        
          
            
              n
              (
              n
              +
              1
              )
            
            2
          
        
        }
      
    
    {\displaystyle C=\{n\in \mathbb {N} \mid 1+2+3+...+n\neq {\frac {n(n+1)}{2}}\}}
  
. By the well-ordering principle, 
  
    
      
        C
      
    
    {\displaystyle C}
  
 has a minimum element 
  
    
      
        c
      
    
    {\displaystyle c}
  
 such that when 
  
    
      
        n
        =
        c
      
    
    {\displaystyle n=c}
  
, the equation is false, but true for all positive integers less than 
  
    
      
        c
      
    
    {\displaystyle c}
  
. The equation is true for 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
  
, so 
  
    
      
        c
        >
        1
      
    
    {\displaystyle c>1}
  
; 
  
    
      
        c
        −
        1
      
    
    {\displaystyle c-1}
  
 is a positive integer less than 
  
    
      
        c
      
    
    {\displaystyle c}
  
, so the equation holds for 
  
    
      
        c
        −
        1
      
    
    {\displaystyle c-1}
  
 as it is not in 
  
    
      
        C
      
    
    {\displaystyle C}
  
. Therefore, 
</p><p>
  
    
      
        
          
            1
            +
            2
            +
            3
            +
            .
            .
            .
            +
            (
            c
            −
            1
            )
          
          
            
            =
            
              
                
                  (
                  c
                  −
                  1
                  )
                  c
                
                2
              
            
          
        
        
          
            1
            +
            2
            +
            3
            +
            .
            .
            .
            +
            (
            c
            −
            1
            )
            +
            c
          
          
            
            =
            
              
                
                  (
                  c
                  −
                  1
                  )
                  c
                
                2
              
            
            +
            c
          
        
        
          
          
            
            =
            
              
                
                  
                    c
                    
                      2
                    
                  
                  −
                  c
                
                2
              
            
            +
            
              
                
                  2
                  c
                
                2
              
            
          
        
        
          
          
            
            =
            
              
                
                  
                    c
                    
                      2
                    
                  
                  +
                  c
                
                2
              
            
          
        
        
          
          
            
            =
            
              
                
                  c
                  (
                  c
                  +
                  1
                  )
                
                2
              
            
          
        
      
    
    {\begin{aligned}1+2+3+...+(c-1)&={\frac {(c-1)c}{2}}\\1+2+3+...+(c-1)+c&={\frac {(c-1)c}{2}}+c\\&={\frac {c^{2}-c}{2}}+{\frac {2c}{2}}\\&={\frac {c^{2}+c}{2}}\\&={\frac {c(c+1)}{2}}\end{aligned}}
  
,
</p><p>which shows that the equation holds for 
  
    
      
        c
      
    
    {\displaystyle c}
  
, a contradiction. So, the equation must hold for all positive integers.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>

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

<ol>
<li id="fn:1"><p>Apostol, Tom (1976). Introduction to Analytic Number Theory. New York: Springer-Verlag. pp. 13. ISBN 0-387-90163-9. <a href="0-387-90163-9" target="_blank">0-387-90163-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Lehman, Eric; Meyer, Albert R; Leighton, F Tom. Mathematics for Computer Science (PDF). Retrieved 2 May 2023. <a href="https://courses.csail.mit.edu/6.042/spring17/mcs.pdf" target="_blank">https://courses.csail.mit.edu/6.042/spring17/mcs.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Lehman, Eric; Meyer, Albert R; Leighton, F Tom. Mathematics for Computer Science (PDF). Retrieved 2 May 2023. <a href="https://courses.csail.mit.edu/6.042/spring17/mcs.pdf" target="_blank">https://courses.csail.mit.edu/6.042/spring17/mcs.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Well-ordering principle open-in-new

Well-ordering principle