4
$\begingroup$

Question 1: Let $P$ is a well-ordered set of real numbers with the usual order. Is $P$ always countable? I think it is true, but I can't prove it.

Question 2: Let $P$ is a well-ordered set. Is $P$ always countable?

Thanks in advance.

$\endgroup$
6
  • 1
    $\begingroup$ Assuming axiom of choice, the well ordering principle tells us that $\Bbb R$ is well-ordered. So the assertion is obviously false assuming the axiom of choice. Your second question also has a negative answer. Take a large ordinal, say $\omega_1$, the first uncountable ordinal. This is an uncountable, well-ordered set. $\endgroup$
    – SamM
    Jul 16, 2017 at 10:05
  • 1
    $\begingroup$ @SamM Looking at the question as it is, the implicit assumption that $\Bbb R$ has the usual order seems quite apparent. And that one is not a well-ordering. $\endgroup$
    – user228113
    Jul 16, 2017 at 10:11
  • $\begingroup$ It is not that obvious. As with any problem of orderings, one should be explicit as to what ordering should be taken, specifically to avoid problems involving the well-ordering principle. My comment stands, it is not true that an arbitrary well-ordered subset of the real numbers (where we are allowed to define an ordering) is countable. $\endgroup$
    – SamM
    Jul 16, 2017 at 10:13
  • $\begingroup$ Yeah, I mean the usual order. @G.Sassatelli $\endgroup$
    – Johnny Ji
    Jul 16, 2017 at 10:13
  • $\begingroup$ @SamM If we're allowed to choose the ordering freely, why would the question specify that we're using the real numbers? $\endgroup$
    – Arthur
    Jul 16, 2017 at 10:15

2 Answers 2

4
$\begingroup$

Suppose $A \subseteq \mathbb{R}$ is well-ordered in the order $<$ from $\mathbb{R}$. Then it is at most countable.

Suppose $A$ is well-ordered in $<$.

Then for each $a \in A$, there is some $r_a>0$ such that $A \cap [a, a+r_a) = \{a\}$ (it's a right-sided limit point). For, if this were not the case:

$$\forall r>0: \exists a'(r) \in A: a'(r) \neq a \land a'(r) \in [a, a+r)$$

And then take $a_1 = a'(1)$, and having defined $a_n$ set $a_{n+1} = a'(a_n -a)$. This defines a decreasing sequence $a_n$ in $A$, and so $\{a_n : n \in \mathbb{N}\}$ does not have a minimum, contradicting well-orderedness. So the claim holds, and we have the required $r_a$. Note that all intervals $[a, a+r_a)$ are pairwise disjoint by construction, and the set of open intervals

$(a, a+r_a)_{a \in A}$ is a family of pairwise disjoint non-empty open intervals of $\mathbb{R}$ of size $|A|$ and each interval contains a (necessarily different) rational, and $\mathbb{Q}$ is countable.

So $A$ is at most countable.

As to 2): In ZF we can develop countable ordinals and take the union of all of them. This is $\omega_1$ : the first uncountable ordinal, which is well-ordered (as all ordinals). So there are uncountable well-ordered sets. Using AC (the axiom of choice) we can prove that all sets regardless of size, can have a well-order defined on them.

$\endgroup$
7
  • 1
    $\begingroup$ AC is not needed for Q2 $\endgroup$ Jul 16, 2017 at 11:00
  • $\begingroup$ @HagenvonEitzen it does require an extra axiom. OK, I know, not full choice (I have the book "Consequences of the axiom of choice" at home), but I only said assuming AC we have the result, which is true. This is the most standard assumption to get this result. $\endgroup$ Jul 16, 2017 at 11:46
  • $\begingroup$ @bof, OK. I'll add it. thx. $\endgroup$ Jul 16, 2017 at 12:32
  • $\begingroup$ @HagenvonEitzen I corrected my statements. thx. $\endgroup$ Jul 16, 2017 at 12:32
  • $\begingroup$ @HennoBrandsma, I think the interval $(a, a+r_a)_{a \in A}$ has more than one rational. $\endgroup$
    – Johnny Ji
    Jul 18, 2017 at 0:10
2
$\begingroup$

Q1: For every $x\in P$, the set $\{\,y\in P\mid y>x\,\}\cup \{x+1\}$ has a minimal element $y_x$. Pick a rational number $q_x\in [x,y_x)$. This gives us an injective map $P\to\Bbb Q$.

Q2: No. In set-theory, well-order manifests best in ordinals. Since I do not know if aou are acquainted with them, these are, in short, sets $\alpha$ with the properties that a) $x\in \alpha$ implies $x\subseteq \alpha$ and b) the $\in$ relation is a well-order on $\alpha$. Some elementary facts:

  • It is vacuously true that $\emptyset$ is an ordinal.
  • If $\alpha$ is an ordinal, then $\alpha\cup\{\alpha\}$ is an ordinal.
  • If $S$ is a set of ordinals, then $\bigcup S$ is an ordinal
  • Every well-ordered set is order-isomorphic to a unique ordinal

Let $B$ the set of well-order relations on $\Bbb N$ (that need not be related to the usual order on $\Bbb N$), and for each $b\in B$, let $\alpha_b$ be the unique ordinal order-isomorphic to $b$. Let $S=\{\,\alpha_b\mid b\in B\,\}$ and $\beta=\bigcup S$. Then $\beta\notin S$, i.e., $\beta$ is not order-isomorphic to any well-ordering of $A$. Hence there cannot exist a bijection $\Bbb N\to\beta$. On the other hand, the standard order $<$ of $\Bbb N$ is a well-order, hence then there does exist a bijection $\Bbb N\to \alpha_<\subseteq \beta$. It follows that $\beta$ is uncountable.

(Remark: If we replace $\Bbb N$ with any other set, the same proof shows that if a set is well-orderable, then there exists a well-orderable set of larger cardinality)

$\endgroup$
3
  • 1
    $\begingroup$ For Q2, Von Neumann ordinals are a needless complication, if the OP is not already acquainted with them. You can just consider countable ordinals as equivalence classes of well-orders on $\omega.$ $\endgroup$
    – bof
    Jul 16, 2017 at 12:14
  • $\begingroup$ @Hagen von Eitzen, Thanks for your reply! But why need $\{ x+1 \}$, I think $\{\,y\in P\mid y>x\,\}$ always has minimal element $y_x$ is enough. $\endgroup$
    – Johnny Ji
    Jul 17, 2017 at 23:49
  • $\begingroup$ @HagenvonEitzen, For Q2, totally don't understand...Is it related with topology? $\endgroup$
    – Johnny Ji
    Jul 17, 2017 at 23:57

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