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’

**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^{2} < b < 1.

Thus, b^{2} Î S.
Instantiation of the well-ordering principle implies that

($ b | b Î
S : b^{2} Î S Þ b £
b^{2})

Since p and true is equivalent to p:

($ b | b Î
S : b^{2} Î S Þ b £
b^{2} Ù b^{2} < b)

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

($ b | b Î
S : b^{2} Î S Þ false)

If p implies false is equivalent to not-p

($ b | b Î
S : b^{2} Ï S )

Trading and instantiating the member-of operations results in

($ b | : b < 1 Ù 1 < b^{2} )

º($ b | : b < b^{2} )

º($ b | : false )

º (A counter-example is false)

false

Thus

S ¹ÆÞ false

So S = Æ

** **

**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