Proof of well-ordering property

237 Views Asked by At

I'm reading the proof of the well-ordering property from my text and I don't understand the last step. I have reproduced the proof here with my explanations for each step in [].

The well-ordering property states that: Every nonempty subset of $\mathbb{Z}_+$ has a smallest element.

To prove this, my text has first proved the following lemma: For each $n\in\mathbb{Z}_+$, the following statement holds: Every nonempty subset of $\{1,\ldots, n\}$ has a smallest element.

The proof of the well-ordering property then goes:


Suppose that $D$ is a nonempty subset of $\mathbb{Z}_+$.

Choose an element $n$ of $D$.

Then the set $A=D\cap\{1,\ldots, n\}$ is nonempty [because it contains $n$], so that $A$ has a smallest element $k$. [This is because $A$ is a nonempty subset of $\{1, \ldots, n\}$ and so we can use the lemma.]

The element $k$ is automatically the smallest element of $D$ as well. [I don't understand this step; please explain.]

2

There are 2 best solutions below

1
On

Certainly $k$ is the smallest element of $D \cap \{1,\ldots, n\}$. $D \cap \{1,\ldots,n\}$ can be thought of as "the set of all members of $D$ that are not larger than $n$.

Suppose that $k$ isn't the smallest element of $D$. Then, by definition, there must be some $a \in D$ with $a < k$. Since $k \leq n$, we have $a \leq n$ and therefore $a$ is "a member of $D$ that is not larger than $n$". So $a \in D \cap \{1,\ldots, n\}$. But $k$ was the smallest member of this set, so it must be that $k \leq a$, contradicting our choice of $a < k$.

0
On

You know by definition that $k \le n$. If $m \in D$ is arbitrary, either $ m > n$ and then $k \le n < m$, or $m \le n$ and then $m \in D \cap \{1,\ldots, n\}$ and by minimality of $k$ in that set, $k \le m$ as well. So $k$ is the minimum of $D$.