"There does not exist an uncountable subset of the real numbers which can not be expressed as the union of two uncountable sets which are disjoint from one another" is obviously true assuming choice. However, I'm looking for a proof of this statement that does not involve choice. I believe I have come up with one myself, but it's a little complicated. Is there any easy way to go about this?

  • 2
    $\begingroup$ What about something like this : you have an uncountable subset of reals $S\subset\mathbb{R}$. Define for all $x\in\mathbb{R}$ the following subsets : $S_{\leq x}=S~\cap~ ]-\infty,x]$ and $S_{>x}=S~\cap~ ]x,+\infty[$. Then for some $x$ both should be uncountable... $\endgroup$ – Olivier Bégassat Oct 6 '11 at 2:58
  • $\begingroup$ I up-voted the question, but I feel it will be nice if you share with us what you already know. For instance, (1.) Assuming choice, what is the obvious partition into disjoint uncountable sets? (2.) And what is your construction that doesn't involve choice? (Atleast a gist of the constructions if not the full details.) $\endgroup$ – Srivatsan Oct 6 '11 at 3:00
  • $\begingroup$ Suppose U is our uncountable set, then assuming choice, we have a bijection between U and and the union of two disjoint sets (not necessarily subsets of U) with the same cardinality as U, right? Also Olivier, are you not assuming choice using that argument? Aren't you associating a set with every element x in R? $\endgroup$ – six Oct 6 '11 at 3:36
  • 2
    $\begingroup$ @Olivier: You don’t need AC to define the sets $S_{\le x}$ and $S_{>x}$, but I’m not yet convinced that you can show that there is an $x$ for which both are uncountable without using at least countable choice. $\endgroup$ – Brian M. Scott Oct 6 '11 at 3:53
  • 1
    $\begingroup$ See Asaf's answer here for a discussion of amorphous sets and other pathologies with cardinalities that may occur without choice. It doesn't address the question whether those can be realized as subsets of the reals but it should be of interest anyway. $\endgroup$ – t.b. Oct 6 '11 at 4:38

Let $x\in\mathbb{R}$. Define $$S_{\leq x}=S~\cap~(-\infty,x]~~~\mathrm{and}~~~S_{>x}=S~\cap~ (x,+\infty)$$ and define $S_{\leq}=\{$ the set of all $x$ such that $S_{\leq x}$ is uncountable $\}$, and $S_>=\{$ the set of all $x$ such that $S_{>x}$ is uncountable $\}$.

$S_{\leq}$ is a non empty$^{(*)}$ interval that extends to infinity on the right, and is therefore of the form $[a,+\infty)$ or $(a,+\infty)$ for some $a\in\mathbb{R}$ or is equal to the whole of $\mathbb{R}$.

Similarly, $S_>$ is a non empty$^{(*)}$ interval that extends to infinity on the left, and is thus of the form $(-\infty,b]$ or $(-\infty,b)$ for some $b\in\mathbb{R}$ or is equal to the whole of $\mathbb{R}$.

$^{(*)}$ : I have used some form of choice I believe when I say that $S_>$ and $S_{\leq}$ are non empty, because I use the fact that with some form of choice, the countable union of countable sets is still countable. Is it countable choice? Since $$S=\cup_{n\in\mathbb{N}}S_{\leq n}$$ is uncountable, at least one of the $S_{<n}$ must be uncountable, and so for some natural number $n$ you have $n\in S_{<}\neq\emptyset$.

Let's show that $S_>\cap S_{\leq}$ is non empty. If either one of $S_>$ or $S_{\leq}$ is the whole real line, there is no problem. So let's suppose none of them is the whole of $\mathbb{R}$.

Suppose $x\in S_{\leq}$ that is $S_{\leq x}=S~\cap~(-\infty,x]$ is uncountable. Since $$\bigcup_{n\in\mathbb{N}^*}S_{\leq x-\frac{1}{n}}\subset S_{\leq x}=S~\cap~(-\infty,x]\subset \{x\}\cup \bigcup_{n\in\mathbb{N}^*}S_{\leq x-\frac{1}{n}}$$ the already used fact that countable unions of countable sets are countable with some form of choice implies that at least one of the $S_{\leq x -\frac{1}{n}}$ is uncountable, which means that for some $n\in\mathbb{N}^*,~x -\frac{1}{n}\in L$ and thus $S_{\leq}$ is open, that is, $$\mathbf{S_{\leq}=(b,+\infty)}$$ for some real number $b$. Similarly, $$\mathbf{S_{>}=(-\infty,a)}$$ for some real number $a$.

Then $S_>\cap S_{\leq}$ is empty iff $a\leq b$. But this would entail that $$S=S_{\leq a}\cup S_{> a}$$ is countable as the union of two countable sets, since $a \notin (-\infty,a)=S_{\leq}$ means $S_{\leq a}$ is countable, and $a \notin (b,+\infty)=S_{>}$ means $S_{> a}$ countable.

  • 1
    $\begingroup$ You’ve definitely used some form of choice, because there are models in which $\mathbb{R}$ is a countable union of countable sets. $\endgroup$ – Brian M. Scott Oct 6 '11 at 5:00
  • 2
    $\begingroup$ After further investigation: you’ve used CUT($\mathbb{R}$) (countable unions of countable subsets of $\mathbb{R}$ are countable), which is strictly weaker than CC($\mathbb{R}$) (axiom of countable choice for subsets of $\mathbb{R}$), which is strictly weaker than CC (every countable family of non-empty sets has a choice function). $\endgroup$ – Brian M. Scott Oct 6 '11 at 5:09
  • $\begingroup$ @Brian M. Scott yes. What does 'CUT' stand for? 'C'ountable 'U'nion ... ? $\endgroup$ – Olivier Bégassat Oct 6 '11 at 5:33
  • $\begingroup$ Countable Union Theorem. I don’t know how widely used the name and abbreviation are; I took them from Herrlich’s Axiom of Choice (Springer Lecture Notes in Mathematics). $\endgroup$ – Brian M. Scott Oct 6 '11 at 5:52

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.