How would one prove using the Axiom of Choice that any uncountable set $A$ of $\mathbb{R}$ can be divided into two uncountably infinite disjoint subsets? I haven't seen this kind of proof exactly, because I'm not looking for a partition.

Formally, let $D$ be the set with the following property: $x$ is a member of $D$ just in case the set of all elements of $A$ strictly greater than $x$ is uncountable and the set of all elements of $A$ strictly less than $x$ is uncountable. How would one show that $D$ is nonempty, preferably without directly resorting to cardinal arithmetic?

Update: I appreciate all the feedback, including a solution. Although a nice proof has been given, I'm interested in seeing how it can be done by using the rationals in particular to split the set.

  • 1
    $\begingroup$ On a related note: math.stackexchange.com/questions/853113/… $\endgroup$ – lulu Oct 26 '16 at 13:26
  • 1
    $\begingroup$ I've added a second argument to show that we can indeed use a rational in the splitting. $\endgroup$ – Andrés E. Caicedo Oct 26 '16 at 16:07
  • $\begingroup$ @AndrésE.Caicedo I saw, thank you very much. But it seems as though Asaf's suggestion was a bit different and perhaps a bit more straightforward. I'm curious as to what he meant exactly. $\endgroup$ – CuriousKid7 Oct 26 '16 at 16:43

For every rational $q$ let $A_q^+=\{x\in A\mid x\geq q\}$ and $A_q^-=\{x\in A\mid x<q\}$. If for some $q$ both are uncountable, super. If not, what can you say about $A$ itself?

Now, you might wonder as to the use of the axiom of choice here, and it hides beneath the surface: in order to prove that every countable union of countable sets is countable, we have to use the axiom of choice.

Edit: Let $r=\sup\{q\mid A^-_q\text{ is countable}\}$ and $s=\inf\{q\mid A^+_q\text{ is countable}\}$.

  1. If either $r$ or $s$ is not a real number (i.e., $\pm\infty$) then we get that $A$ is countable.

  2. If $r>s$, take a rational $q$ witnessing that, then $A^-_q$ and $A^+_q$ are both countable, what do we get?

  3. If $r<s$, take a rational $q$ witnessing that, then $A^-_q$ and $A^+_q$ are both uncountable.

  4. Finally, if $r=s=q$, take an increasing sequence of rationals $r_n$ and a decreasing sequence of rationals $s_n$, both converging to $q$. Then $A\cap\bigcup_{p<q}A_p^+=A\cap\bigcup_{n\in\Bbb N}A^+_{r_n}$ is countable; and $A\cap\bigcup_{p>r} A^-_p$ is countable. Again, we get that $A$ is countable.

So if $A$ is uncountable, there is a rational $q$ such that $r<q<s$ and $A_q^-$ and $A^+_q$ are both uncountable.

  • 1
    $\begingroup$ Good answer, and also good for anticipating the question of where AC is invoked. $\endgroup$ – Matthew Leingang Oct 26 '16 at 13:05
  • 3
    $\begingroup$ It ain't my first rodeo, when it comes to the axiom of choice. ;-) $\endgroup$ – Asaf Karagila Oct 26 '16 at 13:05
  • 1
    $\begingroup$ @CuriousKid7: I've added stuff to the answer. $\endgroup$ – Asaf Karagila Oct 26 '16 at 16:57
  • 1
    $\begingroup$ Ah, this is the right way. Cool! $\endgroup$ – Andrés E. Caicedo Oct 26 '16 at 17:08
  • 1
    $\begingroup$ @Andres: Well, in general? As far as I know, from the work of Eilon Bilinsky, a student of Moti Gitik, the answer is indeed positive. It was an odd problem, posed in the early 1920s that wasn't given its due attention over the years. (I helped Eilon with the history of the problem, I can try and retrace my steps if you want, but only on Monday.) $\endgroup$ – Asaf Karagila Oct 26 '16 at 19:25

The question immediately reminded me of this. Here is an argument following the same basic idea at the beginning of that argument:

First, consider $B=\{x\in A\mid A\cap(-\infty,x]$ is countable$\}$, and note that $B$ itself is countable: The point is that if $x\in B$ then $A\cap(-\infty,x]\subseteq B$. Now, if $B\ne\emptyset$, let $t=\sup B$, fix an increasing sequence of elements of $B$ converging to $t$, $t_0\le t_1\le t_2\le\dots\to t$, and note that $$B\subseteq A\cap(-\infty,t]\subseteq \{t\}\cup\bigcup_n A\cap(-\infty,t_n],$$ and the expression on the right is a countable union of countable sets, and therefore countable (by the axiom of choice).

Now let $C=A\setminus B$. Note that $C$ is uncountable and that if $x\in C$ then $C\cap(-\infty,x]$ is itself uncountable. Otherwise, $x\in B$ (a contradiction), since $A\cap(-\infty,x]\subseteq B\cup(C\cap(-\infty,x])$. Forget about $A$ itself now and work with $C$. The same argument as above shows that $D=\{x\in C\mid C\cap[x,\infty)$ is countable$\}$ is countable as well.

Finally, let $E=C\setminus D$, and note that for any $x\in E$, both $E\cap(-\infty,x)$ and $E\cap(x,\infty)$ are uncountable.

Let me present another argument, showing that we can actually find a rational $q$ such that both $A\cap(-\infty,q)$ and $A\cap(q,\infty)$ are uncountable:

Since $$A\subseteq\mathbb Z\cup\bigcup_{l\in\mathbb Z}A\cap(l,l+1),$$ at least one of the intervals $A\cap(l,l+1)$ is uncountable (by the axiom of choice). We may as well assume that, for such an $l$, $A\setminus(l,l+1)$ is countable, or we are done.

Let $I_0=(l,l+1)$. Suppose we have found $I_n=(a,b)$ of length at most $1/2^n$ with rational endpoints such that $A\cap I_n$ is uncountable but $A\setminus I_n$ is countable. Find rational points $q_m$ for $m\in\mathbb Z$ such that $a<q_k<q_m<b$ whenever $k<m$, $\lim_{k\to-\infty} q_k=a$, $\lim_{m\to\infty}q_m=b$, and $q_{m+1}-q_m\le 1/2^{n+1}$ for all $m\in\mathbb Z$. As before, $$A\cap I_n\subseteq\{q_m\}_{m\in\mathbb Z}\cup\bigcup_{m\in\mathbb Z}A\cap(q_m,q_{m+1}),$$ so for some $m$, $A\cap(q_m,q_{m+1})$ is uncountable. As before, we may assume that $A\setminus (q_m,q_{m+1})$ is countable, or else we are done. Now set $I_{n+1}=(q_m,q_{m+1})$.

The claim is that at some stage $n$ we must actually be done, that is, $A\setminus(q_m,q_{m+1})$ must also be uncountable and therefore at least one of $q_m,q_{m+1}$ works as the rational $q$ we were after.

The proof is by contradiction: Otherwise, the recursion produces an infinite, shrinking sequence of intervals $I_n=(a_n,b_n)$ with $A\cap I_n$ uncountable and $A\setminus I_n$ countable for all $n\in\mathbb N$. Notice that $\bigcap_n I_n$ is either empty or a singleton $\{t\}$, and set $t=0$ if $\bigcap_n I_n=\emptyset$. We have $$A\subseteq \{t\}\cup\bigcup_{n\in\mathbb N}\{a_n,b_n\}\cup\bigcup_{n\in\mathbb N}A\setminus I_n,$$ so $A$ is countable.


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.