Does every nonempty well-ordered set have a least element?

Question

I was making my way through The Art of Computer Programming, when some words got me puzzled. Here is how the book describes the principle of well-ordering:

Let "$\prec$" be a relation on set $S$, satisfying the following properties:

1. Given $x$, $y$ and $z$ in $S$, if $ x \prec y$ and $y \prec z$, then $x \prec z$.

2. Given $x$ and $y$ in $S$, exactly one of the following three possibilities is true: $x \prec y$, $x = y$, or $y \prec x$.

3. If $A$ is any nonempty subset of $S$, there is an element $x$ in $A$ with $x \preceq y$ for all $y$ in $A$.

This relation is said to be a well-ordering of $S$.

Set theory is definitely not my strength suit, but this seems plain wrong to me. Let $S \leftarrow \mathbb{Z}$ and $A \leftarrow S$.

Consider the "less than" ($\lt$) relation. It is transitive $(1)$, and trichotomous $(2)$; it also supports $(3)$ since there will always be some element $x \mid x \le y$.

The set hold for all three assertions, thus it should be well-ordered. (Which is not, since there is no least element.) Am I missing something, or the textbook is misleading?

Answer 1

Knuth has committed the sin of writing something of the form:

• there exists an $x$ such that $P(x, y)$ for all $y$

which can be read as:

1) there exists an $x$ such that for all $y$ $P(x, y)$

or

2) for all $y$ there exists an $x$ such that $P(x, y)$.

Reading 1) is the intended reading here. But how is the reader to know that? You should look into Knuth's rules about errata and see if he owes you a a bounty.

Answer 2

Our example fails (3).There exists $x$ such that $x \leq y$ for all $y \in S$. You cannot find an integer that satisfies this condition.

The natural numbers on the other hand, do have such an element, namely, $1$.

Answer 3

From the definition as quoted:

3. If $A$ is any nonempty subset of $S$, there is an element $x$ in $A$ with $x \preceq y$ for all $y$ in $A$.

You seem to have read:

3. If $A$ is any nonempty subset of $S$, (there is an element $x$ in $A$ with $x \preceq y$) for all $y$ in $A$.

But the author meant:

3. If $A$ is any nonempty subset of $S$, there is an element $x$ in $A$ (with $x \preceq y$ for all $y$ in $A$).

Answer 4

Let $(A, \prec)$ be a well-ordered set. By definition, every nonempty subset of $A$ has a least element with respect $(\prec)$. But $A$ is a nonempty subset of $A$, so it must have a least element with respect to $(\prec)$.

Consider the set of all negative integers. This is a nonempty subset of $\mathbb{Z}$, but it doesn't have a least element with respect to the natural ordering $(<)$ on the integers. Therefore, $(<)$ is not a well-ordering on $\mathbb{Z}$. You can define a well-ordering on $\mathbb{Z}$, but that's probably not what you're after.