9
$\begingroup$

I read here that while 'The Axiom of Choice agrees with the intuition of most mathematicians; the Well Ordering Principle is contrary to the intuition of most mathematicians'. I don't understand why this is so. According to Wikipedia, 'the well-ordering principle states that every non-empty set of positive integers contains a least element'. This is quite a straightforward definition. Is it the way you derive the equivalence of the Axiom of Choice and well ordering principle that makes it counter-intuitive or the definition of the least element?

$\endgroup$
  • 1
    $\begingroup$ I think the passage refers to the more general well-ordering principle "every (nonempty) set [class]" admits a well-ordering. The WOP for $\mathbb{N}$ is not equivalent to the axiom of choice, as far as I remember. $\endgroup$ – Daniel Fischer Jul 3 '13 at 13:57
  • 1
    $\begingroup$ the well-ordering principle goes beyond the integers. For instance, the real numbers can be well-ordered, as well. This could be considered counter-intuitive. $\endgroup$ – Mikhail Katz Jul 3 '13 at 13:57
  • $\begingroup$ As the Wikipedia article you refer to says, "The phrase "well-ordering principle" is sometimes taken to be synonymous with the well-ordering theorem." It's the latter result that is claimed to be unintuitive. $\endgroup$ – Chris Eagle Jul 3 '13 at 13:58
  • 6
    $\begingroup$ It's not really counterintuitive from a contemporary perspective, any more than the imaginary unit $i$ is counterintuitive. But Descartes found $i$ very counterintutive, and invented the term "imaginary" for it. The idea that a metal vehicle could fly under its own power to the moon and back would have been very counterintuitive in the year 1800. Intuition changes over time as we see more examples of things. Usually, when people claim that the well ordering principle is counterintuitive, they are just trying to make a point in their argument. $\endgroup$ – Carl Mummert Jul 3 '13 at 14:12
14
$\begingroup$

The well-ordering principle just refers to $\mathbb{N}$. What is being referred to is the well-ordering theorem, which says that every set admits a well-order. That's the thing that seems a little bit crazy, if you consider how you might achieve this even for a "basic" set like $\mathbb{R}$.

As for choice, a very non-objectionable version is "the product of an arbitrary family of non-empty sets is non-empty". It's equally difficult to think of what a counter-example might look like.

If I would be so bold as to endorse a book on the topic, it would definitely be Horst Herrlich's Axiom of Choice. It will simultaneously convince you of the statement, of the statement's negation, and of neither. Cognitive dissonance eat your heart out.

$\endgroup$
  • 4
    $\begingroup$ It's not hard to find a potential counterexample: for example, consider the product of all nonempty sets of reals. You can't exhibit an element of that product. $\endgroup$ – Chris Eagle Jul 3 '13 at 14:01
  • 3
    $\begingroup$ that came off as far more religious than i intended... $\endgroup$ – citedcorpse Jul 3 '13 at 14:04
  • 2
    $\begingroup$ Yes, I know what the axiom of choice is. I'm just taking issue with your claim that it's difficult to think of what a counter-example to products-are-nonempty might look like. $\endgroup$ – Chris Eagle Jul 3 '13 at 14:09
  • 2
    $\begingroup$ well, in my head it's difficult to distinguish between a non-empty set and an inhabited set. i would hope all non-empty sets come with some certificate witnessing that they are indeed non-empty, yet i know this is not necessarily given $\endgroup$ – citedcorpse Jul 3 '13 at 14:11
  • 2
    $\begingroup$ @Chris: If one’s intuition makes no distinction between non-empty set and set with exhibited element, then it is indeed hard to imagine what a counterexample might look like. One can say that if there is a counterexample, it must be here, not over there, but one’s intuition may still find it find it very hard to imagine that this thing here really is a counterexample. $\endgroup$ – Brian M. Scott Jul 3 '13 at 21:21
11
$\begingroup$

People object to the idea that every set can be well-ordered because they often think of sets alongside a natural structure imposed on them, and they initially expect that a well-order of the set would somehow respect that natural structure.

For example, people don't think of $\Bbb R$ as just a set, they think about it as an ordered set, with binary operations. If you expect that a well-ordering of $\Bbb R$ would respect the natural order of $\Bbb R$ then you run into problems: what is the successor of $0$? What is the minimal element of the order?

However, it is true that a well-ordering need not be compatible with that order of $\Bbb R$. The reason this is an interesting objection is that people have no qualms with the claim that $\Bbb Q$ is a countable set, and that there is a bijection from $\Bbb N$ onto $\Bbb Q$. This bijection induces a well-ordering of $\Bbb Q$ and it too doesn't respect the natural order of the rational numbers. Not even one bit.

Another objection people may have, and you see this objection often with cranks who argue that all the mathematics based on infinities is inconsistent, is that if a set is well-ordered then we must have a name for every element in the set, because then you can ask "what is the minimal element that cannot be named?", and so you can name that element. Since the set of names is countable well-ordering of a set would have to imply it is a countable set.

However the problem with this argument is that "the set of unnameable objects" is not a first-order definition, and so we can't really define that set in the universe of set theory. So this sort of objection is wrong just as well.

Finally, there is a reasonable objection that people may have, and that that the assumption of the axiom of choice induces all sort of intangible objects that we can't construct by any reasonable means. These people feel that philosophically we need to avoid such mathematics, and they prefer to work in a different framework that requires things to be explicitly constructed, and that's fine. This is the only valid objection I heard so far. Although there are people who voice these sort of opinions along with other near-crank claims against the axiom of choice.

$\endgroup$
2
$\begingroup$

The well ordering theorem is equivalent too "for every set, this is a strict total order, such that every subset has a minimum element." Think about how you would order $\mathbb{R}$ such that that is true (the normal ordering wouldn't work for sure.)

$\endgroup$
  • 1
    $\begingroup$ It's easy to think about how you would order $\mathbb{R}$ that way: imagine the ordinal numbers laid out in a row, and just stick different a real number beside each ordinal until you are out of real numbers. It turns out that formalizing that argument in set theory requires the axiom of choice, but the actual argument is very straightforward and intuitive. $\endgroup$ – Carl Mummert Jul 3 '13 at 14:14
  • 1
    $\begingroup$ To clarify for people who are confused: Carl is using a Theorem of Hartog which says that, for any set $X$, there is no injection from the ordinals into $X$. The proof of this theorem is hard (IMNSHO) in that it involves some tricky manipulations, but it does not use AC or any other controversial principle. If you agree with Carl that you can imagine "stick[ing] a different real number beside each real ordinal until you run out of real numbers", then Hartog's theorem guarantees that you will run out of real numbers before you cover all the ordinals. $\endgroup$ – David E Speyer Jul 3 '13 at 15:22
  • $\begingroup$ The mathematician's name is Hartogs not Hartog en.wikipedia.org/wiki/Friedrich_Hartogs ; sorry. $\endgroup$ – David E Speyer Jul 3 '13 at 15:38
  • $\begingroup$ Exactly. I would phrase it the opposite way, though: because the reals are a set and the ordinals are a proper class, any (set) function from the reals to the ordinals has to be bounded. Otherwise, the range of that function would be an unbounded set of ordinals, but every set of ordinals is bounded (this is easier than it might seem). A key aspect of the original "intuitive" argument is that if we line up the reals beside the ordinals then we have both a function from (some) ordinals to reals, and also a function from reals to ordinals. $\endgroup$ – Carl Mummert Jul 3 '13 at 15:52
  • 1
    $\begingroup$ @David: I don't think that the proof is hard, although I wouldn't characterize it as particularly easy. I would also think that an easier way of doing so would be to first prove that there a well-ordering which does not embed into the set (as Hartogs original theorem that predates the von Neumann ordinals), and then prove that every well-ordered set is isomorphic to a unique ordinal. $\endgroup$ – Asaf Karagila Jan 28 '15 at 21:32

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.