3
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $. $\endgroup$ – Filippo Costa Aug 8 '17 at 19:27
  • 1
    $\begingroup$ Well done! I'm not sure Knuth's appeal to punctuation would stand up in court! Enjoy your hexadecimal dollar! $\endgroup$ – Rob Arthan Aug 8 '17 at 20:33
1
$\begingroup$

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

You seem to have read:

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.