Math Notes - Well-Ordering Principle

 

The set of positive integers P is well-ordered with respect to the relation £.  According to the well-ordering principle, every non-empty subset of P has a least element.  Suppose that the set S is a subset of P, then there exists a member of S such that for all members c of S, the relation b £ c is true:

 

      S ¹Æº ($ b | b Î S : (" c | c Î S : b £ c ))

 

      S ¹Æº ($ b | b Î S : (" c | : c Î S Þ b £ c ))

 

Theorem 1: The least element of a set is unique.

 

Let S be a non-empty subset of a well-ordered set, and let b be the least element.  Let b’ be another least element.  The proof will show that b = b’.

 

Since b is a least element and b’ is a least element, let b and b’ be distinct elements such that:

      (" c | : c Î S Þ b £ c ) Ù (" c | : c Î S Þ b’ £ c )

 

Instantiating the universal quantifications implies:

      (b’ Î S Þ b £ b’) Ù (b Î S Þ b’ £ b )

 

Since b and b’ are both elements of S:

      b £ b’ Ù b’ £ b

 

Relation £ is antisymmetric, so

     

      b = b’

 

End of Proof

 

Corollary to Theorem 1: If b is a least element of set S, and b’ £ b then b = b’.

 

Theorem 2: The number 1 is the least positive integer. That is,

a Î P º 1 £ a.

 

The universal set of discourse is the set of integers, and the set of positive integers is defined as

 

P = {i |0 < i : i}.

 

The set

 

S = {j | 0 < j < 1 : j}

 

is the set of all positive integers less than 1.  This proof will show that S is empty.

 

Assume that S ¹Æ.  Let b be a distinct integer, then by the well-ordering principle:

 

      ($ b | b Î S : (" c | : c Î S Þ b £ c))

 

Since b Î S, then 0 < b < 1.  Multiply by b:

 

      0 < b² < b < 1.

 

Thus, b² Î S.  Instantiation of the well-ordering principle implies that

 

      ($ b | b Î S : b² Î S Þ b £ b²)

 

Since p and true is equivalent to p:

 

      ($ b | b Î S : b² Î S Þ b £ b² Ù b² < b)

     

An integer cannot be less than and greater than another integer.

 

     

      ($ b | b Î S : b² Î S Þ false)

 

 
If p implies false is equivalent to not-p

 

      ($ b | b Î S : b² Ï S )

 

Trading and instantiating the member-of operations results in

 

      ($ b | : b < 1 Ù 1 < b² )

      º($ b | : b < b² )

 

      º($ b | : false )

 

º (A counter-example is false)

 

false

 

Thus

 

      S ¹ÆÞ false

 

So S = Æ

 

End of Proof

 

References:

 

Long, Calvin T., 1965, Elementary Introduction to Number Theory, Boston, MA: D. C. Heath and Company

 

Gries, David and Schneider, Fred B., 1993, A Logical Approach to Discrete Math, New York, NY: Springer-Verlag