[Math] Prove that the set of integers bounded below is well-ordered.

elementary-set-theory

Given that we have some $r \in \mathbb{R}$, demonstrate that the set $ S=\{n\in \mathbb{Z} : r\leq n\}$ is well-ordered.

I first tried to demonstrate that there exists exactly one integer on the half-open interval $(r,r+1]$ (because I had used that as a Lemma for a previous assignment) and then proceed inductively to show that any subset would admit a least element. However, that proof required that I assume that $\mathbb{N}$ is well-ordered. The point of this assignment is to use this result as a Lemma to prove that $\mathbb{N}$ is well-ordered, so I cannot use that assumption.

It seems obvious to me that the only thing keeping $\mathbb{Z}$ from being well-ordered is that it is unbounded on the negative side. However, seeing that this lower bound eliminates that problem and demonstrating that an arbitrary subset of $\mathbb{Z}$ must admit a least element has proven more difficult for me than I expected. The level for the question is an undergraduate intro to Set Theory.

It turns out the intention of the professor was to have us prove that every non-empty subset of $\mathbb{R}$ is well ordered if and only if every descending sequence of that subset stabilizes. Off to work on that one now.

Best Answer

The following proof assumes the following is known:

  • For $a,b\in\mathbb R$, the set $[a,b]\cap \mathbb Z$ is finite.
  • A total order on a finite set is a well-order.

We have to show that every nonempty subset $A$ of $S$ has a minimal element. As $A\ne \emptyset$, let $a\in A$ be some element of $A$. Then $B:=\{x\in A\mid x\le a\}$ is nonempty and finite because it is in fact $\mathbb Z\cap [r,a]$. Hence $B$ is well-ordered. Let $b=\min B$. Then $b=\min A$ because for $x\in A$ we have either $x\le a$ and then $b\le x$ because $x\in B$; or we have $x>a$ and then $x\le a<x$ directly.