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

Question

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.

Do you have any examples of infinite sets you already know to be well-ordered? Or: How is $\mathbb Z$ constructed if not starting from $\mathbb N$, which is wellordered per Peano axioms or as an ordinal ... Maybe you start with a complete ordered field $\mathbb R$ and let $\mathbb Z$ be the smallest additive subgroup containing $1$? — Hagen von Eitzen, Apr 29 '13 at 10:33
Do you know that finite subsets of $\mathbb R$ are wellordered? And that $(a,b)\cap \mathbb Z$ is always at most finite? — Hagen von Eitzen, Apr 29 '13 at 10:43
That's not something that I've used, though if I can formulate a Lemma then I can use it. — S3ANZ13, Apr 29 '13 at 10:46
It's hard to tell what you can use and what not. I repeat: What is your definition of $\mathbb Z$? — Hagen von Eitzen, Apr 29 '13 at 10:47
Our text gives what I expect is not what you were looking for: $\mathbb{Z} = {..., -3, -2, -1, 0, 1, 2, 3,... }$. — S3ANZ13, Apr 29 '13 at 10:51

score 4 · Accepted Answer · answered Apr 29 '13 at 10:50

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.

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

1 Answers1

Linked