Let $S_{\Omega}$ be the minimal uncountable well-ordered set. Let $X_O$ be the subset of $S_{\Omega}$ consisting of all elements $x$ such that $x$ has no immediate predecessor.

Then how to show that $X_O$ is uncountable?

My effort:

Suppose that $X_O$ is at most countable. Since $S_{\Omega}$ is uncountable, there exists an element $a \in S_{\Omega} - X_O$. Then $a$ has an immediate predecessor, call it, $a_1$.

Since the subset $S_{\Omega} - X_O$ of $S_{\Omega}$ is non-empty, it has a smallest element, say, $u$. Let $u_1$ be the immediate predecessor of $u$. Then $u_1 \not\in S_{\Omega} - X_O$. So $u_1$ has no immediate predecessor. Thus $u_1 \in X_O$. So $X_O$ is non-empty.

Let $x_0$ be the smallest element of $X_O$.

What next?

How to proceed from here?

After reading @Crostul's answer.

A non-empty subset $A$ of $S_{\Omega}$ is (at most) countable if and only if $A$ is bounded above in $S_{\Omega}$.

Since $S_{\Omega}$ is well-ordered, it has a smallest element, and this element has no immediate predecessor and is thus in $X_O$; so $X_O$ is non-empty.

Suppose that $X_O$ is countable. Then $X_O$ has an upper bound $a$; let $b$ denote the immediate successor of $a$, which exists since $S_{\Omega}$ is well-ordered and has no largest element. Since $b$ has an immediate predecessor, namely $a$, therefore $b \not\in X_O$. So $X_O \subset S_b$.

Moreover, every well-ordered set has the least-upper-bound property. Let $c$ be the supremum of $X_O$. Then $c \leq a$.

What next?


For $a \in S_{\Omega}$ i will denote by $a+1$ the successor of $a$, $a+2$ the successor of $a+1$, etc...

You should use the following useful fact:

Let $A\subset S_{\Omega}$ any subset. Then $A$ is bounded above if and only if $A$ is countable.

Now, suppose that $X_0$ is bounded above (and countable). Then, there exists $a \in S_{\Omega}$ such that $X_0 < a$. Consider the set $$A=\{ a, a+1, a+2, \dots, a+n, \dots, \} = \{ a+n :n \in \Bbb{Z}_{\ge0}\}$$ $A$ is clearly countable, so it is bounded above. Let $\psi = \sup A$. Obviously, $\psi \notin A$, since $A$ has no maximum.

I claim that $\psi$ has no predecessor. Otherwise, suppose $\psi = \alpha +1$ for some element $\alpha \in S_{\Omega}$. Then $\alpha $ is not an upper bound of $A$, hence there exists come $n \ge 0$ such that $\alpha \le a+n$. Then $\psi = \alpha +1 \le a+(n+1) < a+ (n+2)$: a contradiction.

We proved that $\psi$ has no predecessor, i.e. $\psi \in X_0$: a contradiction.

So $X_0$ cannot be a countable set.

  • $\begingroup$ Can you spell out why $A\subset S_\Omega$ countable implies bounded above? $\endgroup$ – Ben Blum-Smith Jun 7 '15 at 21:46
  • $\begingroup$ Let $A$ be countable, and suppose it has no maximum. Then $$A\subseteq \bigcup_{a \in A} \{ x \in S_{\Omega} : x < a \} = B$$ B is a countable ordinal since it is a countable union of countable sets. But now, this means that it is an ordinal smaller than $\Omega$, so $B$ is bounded in $S_{\Omega}$. $\endgroup$ – Crostul Jun 7 '15 at 21:57
  • $\begingroup$ See also math.stackexchange.com/questions/1234859/… $\endgroup$ – Crostul Jun 7 '15 at 22:02
  • $\begingroup$ @Crostul, what do you mean by $a+1$? You see, we haven't got any operator of addition here. $\endgroup$ – Saaqib Mahmood Jun 8 '15 at 4:22
  • $\begingroup$ @Crostul, by $a+1$, do you mean the successor of $a$, which exists because $S_{\Omega}$ is well-ordered and has no largest element? $\endgroup$ – Saaqib Mahmood Jun 8 '15 at 4:24

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.