1

THe well ordering principle has that every subset of $\mathbb{Z}^+_0$ has a least element.

or if $S$ is a non-empty subset of $\mathbb{Z}^+_0$ and $S = \{a_1, a_2, a_3 ... a_n\}$, then there is a least element (say $a_1$) which is lesser than $a_2, a_3 ...a_n$

I attempted to prove it by using three elements :

Suppose that there is no least element. Then,

$$a_1 < a_2, a_3 ~~\not\exists$$ $$\implies a_1 > a_2, a_3$$

Then we have two cases :

Case I:

$a_2 > a_3$
$\implies a_1 > a_2 > a_3$
So $a_3$ is least element

Case 2:

$a_3 > a_2$
$\implies a_1 > a_3 > a_2$
So $a_2$ is least element

There is a lest element in every case. Contradiction.

Questions

Is this proof correct? Can it also be shown for any arbitrary number of elements?

Thank you!

Max Payne
  • 3,447
  • The well-ordering principle includes infinite sets, too. Proving for finite cases, the fact that there is a least element only requires a linear orders - it is true for the real, rationales and integers, for example. The infinite case is not true for the reals, rationals, nor the integers. – Thomas Andrews May 26 '15 at 16:50
  • How do we show it for finite as well as infinite sets? is my proof ok? Thank you. – Max Payne May 26 '15 at 16:52

2 Answers2

3

Hint: Let $S\subseteq\Bbb N$ with no least element. So $0\notin S$ for otherwise it would have a least element. So, $0\in\Bbb N\setminus S$. Now use induction to show $\Bbb N=\Bbb N\setminus S$.

Tim Raczkowski
  • 20,046
2

Tim's suggestion is a great way to show this for both finite and infinite subsets of $\mathbb{N}$. Here's a simple/fun argument just for finite sets. Suppose that $n > 0$ and consider the problem of determining the smallest element in a set of $n$ distinct positive integers. Note that if $n = 1$, then the set contains a single element $a_1$, which is the smallest element by default.

Suppose that $n \geq 2$ and for all positive integers $m < n$ every set of positive integers of order $m$ has a least element. Let $S = \{a_1,\ldots,a_n\}$ be a set of $n$ distinct positive integers. Since $n \geq 2$, by trichotomy (pick any two arbitrary $a_\ell$ and $a_m$ and choose the larger one) there exists $k \in \{1,\ldots,n\}$ such that the set $S_k = \{a_\ell \mid a_\ell < a_k\}$ is nonempty, and hence so is $T_k = S \setminus S_k$, since $a_k \in T_k$. Therefore $$ \#S_k = \#S - \#T_k \leq n-1, $$ and so our hypothesis ensures that $S_k$ contains a least element. Said element is of the form $a_m$ for some $m \in \{1,\ldots,n\}$, and satisfies $a_m \leq x$ for all $x \in S_k$. Since $a_m \in S_k$ implies $a_m < a_k$ and since $a_k \leq y$ for all $y \in T_k$, we see by transitivity that $a_m < y$ for all $y \in T_k$. Thus $a_m \leq z$ for all $z \in S_k\cup T_k = S$, contradicting our hypothesis that $S$ had no least element.

Dan
  • 7,951