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