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

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?

• Yes, you are missing something. For your example, Property 3 fails. It says that any non-empty subset has a least element. – André Nicolas Mar 23 '16 at 0:33
• @AndréNicolas: property 3 is expressed ambiguously. It's Knuth who is at fault here, not the OP. – Rob Arthan Mar 23 '16 at 1:05

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

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

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.

• Thank you for your answer. At the end I got an hexadecimal dollar from him, but not for this in particular. Knuth said that he doesn't consider it to be ambiguous since there is no comma after $x \preceq y$. – Filippo Costa Aug 8 '17 at 19:27
• Well done! I'm not sure Knuth's appeal to punctuation would stand up in court! Enjoy your hexadecimal dollar! – Rob Arthan Aug 8 '17 at 20:33

From the definition as quoted:

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

1. 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:

1. 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 make it sound like it's the reader's fault. – Rob Arthan Mar 23 '16 at 0:48
• @RobArthan Hmm, that wasn't my intention. So noted! – Chris Culter Mar 23 '16 at 0:54
• Amazing that the OP prefers an answer that is neutral about Knuth's lapse into an ambiguous style. – Rob Arthan Apr 20 '17 at 19:29

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$.

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.