From what I understand, the well-ordering theorem assumes ANY set can be made well-ordered depending on how you define the ordering.

For example, $\mathbb{Z}$ is not well-ordered according to the conventional ordering of (<). But, if we define a new ordering, say ($\prec$), s.t. for any $a,b \in \mathbb{Z}$, we have $a \prec b$ whenever $|a| \le |b|$, then we can order the set of integers as $\{0, 1 ,-1, 2,-2,3, -3,...\}$ and thus make the set well-ordered. Under this new ordering the least element is $0$, and every nonempty subset will also have a least element.

If the well-ordering axiom is true, then there exists an ordering s.t. the $\mathbb{R}$ are also well-ordered, but how is this possible given the $\mathbb{R}$ is uncountable?

In other words, if there was such an ordering, say ordering $(@)$, then that ordering would effectively be a function makes the reals listable, would it not? Under $@$, there would be some number, say $n_1$, that would be the least element of $\mathbb{R}$... and another number, $n_2$, that would be the least element of $\mathbb{R}-\{n_1\}$... and another number, $n_3$, that would be the least element of $\mathbb{R}-\{n_1,n_2\}$, and so on and so forth... but we know the reals cannot be placed into a one-to-one correspondence with $\mathbb{N}$ as $n_1,n_2,n_3$,... This seems like a contradiction to me.

Can anyone resolve this for me without getting too steeped in jargon and notation? Thanks.

  • $\begingroup$ An order isn't literally a list, it's just a relation that is total (law of trichotomy). So, uncountable sets can be well ordered. $\endgroup$ – Don Thousand Oct 5 at 5:45
  • $\begingroup$ The ordering may not be a list, but couldn't you use the ordering to create a list? For example, by recursively removing the least element of the $\mathbb{R}$ starting with the $\mathbb{R}$? $\endgroup$ – RyRy the Fly Guy Oct 5 at 5:49
  • $\begingroup$ Who said doing that will cover all of $\mathbb R$? See this $\endgroup$ – Don Thousand Oct 5 at 5:50
  • 2
    $\begingroup$ The axiom of choice is a red herring. There are uncountable well-ordered sets, even if the real numbers cannot be well-ordered (and the axiom of choice fails significantly). $\endgroup$ – Asaf Karagila Oct 5 at 9:07
  • 1
    $\begingroup$ I want to amplify Asaf's comment, because it took a weirdly long time for someone to clearly point out that there are uncountable well-orderings. Being well-ordered is entirely unrelated to countability. $\endgroup$ – Malice Vidrine Oct 5 at 17:27

First, your list of elements of $\mathbb Z$ can be regarded as well-ordered, but not using the relation you have stated, since that makes both $n\prec -n$ and $-n\prec n$.

Secondly a well-ordered set corresponds to an ordinal number. A countable set is one which has a bijection to the ordinal $\omega$ (which can be regarded as the ordered set $\{0,1,2,3,4, \dots\}$).

To illustrate the difference, consider the integers with the ordering $0, 1, 2, 3 \dots -1, -2, -3, \dots$. This has order type $2\omega$ and is a well-ordering (you should check this). Using your strategy for the reals you would list the positive integers, but would never get to the negative integers.

Countably infinite sets can have many different well-orderings of different order types (uncountably many in fact). But they all have a well-ordering of type $\omega$.

Your strategy for the reals fails to show hey are countable because it doesn't list every real number. Cantor's diagonal argument shows that no strategy can work.

Perhaps others will inject a little more technical precision here. The fact that all sets can be well-ordered does not follow from the "other" axioms of set theory. It is sometimes posed as an axiom itself, and is sometimes regarded as a consequence of the Axiom of Choice.

  • $\begingroup$ i appreciate you pointing out the shortcomings of the ordering i defined on the integers. However, I am NOT trying to make a point that it's possible to list the real numbers. I'm aware of Cantor's argument and that is the very reason i feel the well-ordering theorem or "axiom" poses a contradiction $\endgroup$ – RyRy the Fly Guy Oct 5 at 6:09
  • 1
    $\begingroup$ @RyRytheFlyGuy It doesn't pose a contradiction precisely because your procedure to enumerate $\mathbb{Z}$, given the well-ordering in the answer, does not in fact enumerate $\mathbb{Z}$. If your "contradiction" were indeed a contradiction, that procedure would have to enumerate $\mathbb{Z}$. $\endgroup$ – Patrick Stevens Oct 5 at 6:39
  • $\begingroup$ i'm not trying to order the integers. that was just an example. the point is i'm talking about the real numbers $\endgroup$ – RyRy the Fly Guy Oct 5 at 6:41
  • 1
    $\begingroup$ @RyRytheFlyGuy I used the example of an alternative well-ordering of the integers to show that even if you begin with a set you well know to be countable, the procedure you want to adopt for the real numbers need not produce a complete enumeration. Indeed every infinite ordinal has an initial segment order isomorphic to $\omega$ and your enumeration technique only counts that initial segment. $\endgroup$ – Mark Bennet Oct 5 at 16:51

It is indeed possible to generate an infinite list-more precisely, a list of order type $\omega$-by recursively choosing the least element of any well ordered set. This list will usually not contain the whole set, and indeed cannot when the set is uncountable. You haven't given any justification for why you intuit that this process should exhaust the set, so it's difficult to say more.

  • $\begingroup$ can you explain why this method would not exhaust the whole set if every subset of the reals had a least element? $\endgroup$ – RyRy the Fly Guy Oct 5 at 6:39
  • 2
    $\begingroup$ @RyRytheFlyGuy Well, it simply doesn't. Can you explain why it would? If you understand Cantor's argument, you understand there are different scales of infinity. "Going on forever" doesn't give any reason to exhaust a set. $\endgroup$ – Kevin Carlson Oct 5 at 6:47
  • $\begingroup$ maybe the issue is I'm lacking what it means for something to be of order type $\omega$. $\endgroup$ – RyRy the Fly Guy Oct 5 at 6:52
  • 2
    $\begingroup$ @RyRytheFlyGuy Order-isomorphic to the naturals in their standard ordering. In other words, ordered like this: $x,x,x,x,x\ldots,$ as opposed to like this: $x,x,x,x\ldots, x,x,x,x,\ldots$ as in the counterexamples given above. (Or as opposed to any of the many other patterns the order of a set can take.) $\endgroup$ – spaceisdarkgreen Oct 5 at 7:30

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.