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)






S false


So S =


End of Proof




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