# Well-Ordering Principle

## Contents

## Theorem

Every non-empty subset of $\N$ has a smallest (or **first**) element.

This is called the **well-ordering principle**.

The **well-ordering principle** also holds for $\N_{\ne 0}$.

## Proof

Consider the natural numbers $\N$ defined as the naturally ordered semigroup $\struct {S, \circ, \preceq}$.

From its definition, $\struct {S, \circ, \preceq}$ is well-ordered by $\preceq$.

The result follows.

As $\N_{\ne 0} = \N \setminus \set 0$, by Set Difference is Subset $\N_{\ne 0} \subseteq \N$.

As $\N$ is well-ordered, by definition, every subset of $\N$ has a smallest element.

$\blacksquare$

## Also known as

This is otherwise known as the **well-ordering property (of $\N$)**.

Some sources give it as the **least-integer principle**.

Note that some authors cite this as the **well-ordering theorem**.

However, this allows it to be confused even more easily with the Well-Ordering Theorem, which states that any set can have an ordering under which that set is a well-ordered set.

## Also see

Some authors extend the scope of this theorem to include:

- Set of Integers Bounded Below has Smallest Element
- Set of Integers Bounded Above has Greatest Element

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: I. Basic Concepts*... (previous) ... (next): Introduction $\S 4$: The natural numbers - 1960: Paul R. Halmos:
*Naive Set Theory*... (previous) ... (next): $\S 13$: Arithmetic - 1964: W.E. Deskins:
*Abstract Algebra*... (previous) ... (next): $\S 2.3$: Theorem $2.16$ - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {2-1}$ Euclid's Division Lemma: Exercise $2$ - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 20$ - 1971: Robert H. Kasriel:
*Undergraduate Topology*... (previous) ... (next): $\S 1.17$: Finite Induction and Well-Ordering for Positive Integers: $17.2$ - 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 4$: Number systems $\text{I}$: Peano's Axioms - 1977: K.G. Binmore:
*Mathematical Analysis: A Straightforward Approach*... (previous) ... (next): $\S 3.5$ - 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.6$: Mathematical Induction - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): $\S 2.1$: The integers: $\mathbf{I}''$ - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction: Exercise $15$ - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 4$: The Integers and the Real Numbers