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 < b2 < b < 1.

 

Thus, b2 S. Instantiation of the well-ordering principle implies that

 

($ b | b S : b2 S b b2)

 

Since p and true is equivalent to p:

 

($ b | b S : b2 S b b2 b2 < b)

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

 

($ b | b S : b2 S false)

 


If p implies false is equivalent to not-p

 

($ b | b S : b2 S )

 

Trading and instantiating the member-of operations results in

 

($ b | : b < 1 1 < b2 )


($ b | : b < b2 )

 

($ 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