As my username might possibly suggest, set theory and logic is not really an area of mathematics I know much about. But, there is this statement and apparent proof I was able to come up with, both of which I find extremely suspicious. The statement is as follows:

There exists an uncountable totally ordered set such that any bounded subset of it is countable.

$\textit{Proof:}$ Let $\Sigma$ be the set of all countable subsets of $\mathbb{R}$. Now, there exists a chain $(W_j)_{j\in J}$ in $\Sigma$ indexed by some set $J$ such that that it is not bounded above in $\Sigma$ (if every chain in $\Sigma$ was bounded above, then Zorn's lemma would tell us that $\mathbb{R}$ is countable and that is not possible). Now, $\bigcup_{j\in J}W_j$ is an uncountable set (otherwise it would bound the chain). Therefore, $J$ must be uncountable too. Now I define a set $I$ to be the set $J$ quotiented by the equivalence relation $\sim$, where, for any $i,j\in J$ we say $i\sim j$ if and only if $W_i=W_j$. Now, $I$ continues to be a totally ordered set and, since $\bigcup_{i\in I}W_i=\bigcup_{j\in J}W_j$, we have that $I$ is also uncountable. Now, let $i,j\in I$ such that $i<j$. Then, for any $i<k,k'<j$, we have that $W_k=W_{k'}$ if and only if $k=k'$. Therefore, since $W_j\setminus W_i$ is still a countable set, there can only be countably many elements between $i$ and $j$. Thus, $I$ is an uncountable totally ordered set such that any bounded subset has only countably many elements.

I was discussin this result wil a friend and we concluded the following even weirder result.

There does not exist an increasing sequence in $I$ (as defined in the above proof) such that it is unbounded.

$\textit{Proof:}$ First define $W_0=\emptyset$ and hence we add an element $0$ to $J$. Then, using this new $J$ we can define $I$ as previously. Now, any sequence $0=a_0<a_1<a_2<\cdot\cdot\cdot$ in I would have to be bounded becasue otherwise $\bigcup_{k=0}^\infty[a_i,a_{i+1}]=I$ and the set of the left is countable while the set of the right is uncoutable.

If there is an error in the proof, I believe is should have something to do with choice and Zorn's lemma. Could someone please tell me if this above statement and the proof that follows are correct. Like I said previously, set theory and logic is not an area I know much about and please excuse me if I have made some very obvious and ridiculous error.

Thanks in advance


There is actually a subtle flaw in your proof, but the statements you mention are still true!

The flaw is in the bit where you claim that $\{ k \in I : i < k < j\}$ is countable, this does not need to be the case. I think it is best illustrated with a counterexample. By the same logic there would not be a chain $(A_i)_{i \in I}$ such that $\bigcup_{i \in I} A_i = \mathbb{Q}$, where $I$ is uncountable and for $i < j \in I$ we have that $A_i \subsetneq A_j$. However, we can construct such a chain. Just take $I$ to be $\mathbb{R}$ and for $r \in \mathbb{R}$ let $A_r = (-\infty, r) \cap \mathbb{Q}$.

The first statement you are trying to prove does actually not need the axiom of choice! The ordinal $\omega_1$, the first uncountable ordinal, is in fact a totally ordered set and every bounded subset is countable. To construct this ordinal you do not need the axiom of choice.

In your second statement, you have discovered the concept of cofinality. For this proof we do need the axiom of choice, because otherwise a countable union of countable sets does not need to be countable. However, assuming the axiom of choice your proof goes through and would also work to show that $\omega_1$ has uncountable cofinality (i.e. you cannot find an unbounded countable sequence).

  • $\begingroup$ Could you direct me to a proof of the first statement? A link maybe. $\endgroup$ – Coherent Sheaf Jun 11 at 16:10
  • $\begingroup$ @CoherentSheaf Once you understand the construction of $\omega_1$ the statement follows directly: for any $\alpha \in \omega_1$ we have that $X = \{\beta \in \omega_1 : \beta < \alpha\}$ is an ordinal. So $X$ must be countable, because otherwise $\omega_1$ would not be the least uncountable ordinal. $\endgroup$ – Mark Kamsma Jun 11 at 16:47
  • $\begingroup$ @CoherentSheaf To prove that $\omega_1$ actually exist you first need to understand some basics about ordinal numbers. Importantly: the class of all ordinal numbers is well-ordered. Using Hartogs number construction we can prove that there are actually uncountable ordinals. So the class of uncountable ordinals is non-empty and thus has a least element, which we call $\omega_1$. $\endgroup$ – Mark Kamsma Jun 11 at 16:54
  • $\begingroup$ Thank you very much. $\endgroup$ – Coherent Sheaf Jun 12 at 11:10

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.