9
$\begingroup$

How does one prove that an uncountable set has an uncountable subset whose complement is uncountable. I know it needs the axiom of choice but I've never worked with it, so I can't figure out how to use. Here is my attempt (which seems wrong from the start):

Let $X$ be an uncountable set, write $X$ as a disjoint uncountable union of the sets $\{x_{i_1},x_{i_2}\}$ i.e $X=\bigcup_{i\in I}\{x_{i_1},x_{i_2}\}$ where $I$ is an uncountable index (I'm pretty sure writing $X$ like this can't always be done), using the axiom of choice on the collection $\{x_{i_1},x_{i_2}\}$ we get an uncountable set which say is all the ${x_{i_1}}$ then the remaining ${x_{i_2}}$ are uncountable.

Anyway how is it done, properly?

I know the question has been asked in some form here but the answers are beyond my knowledge.

$\endgroup$

2 Answers 2

9
$\begingroup$

Your idea is generally correct.

Using the axiom of choice, $|X|=|X|+|X|$, so there is a bijection between $X$ and $X\times\{0,1\}$. Clearly the latter can be partitioned into two uncountable sets, $X\times\{0\}$ and $X\times\{1\}$.

Therefore $X$ can be partitioned to two uncountable disjoint sets.


Indeed you need the axiom of choice to even have that every infinite set can be written as a disjoint union of two infinite sets, let alone uncountable ones.

$\endgroup$
9
  • $\begingroup$ Thanks Assaf, does the proof $|X|=|X|+|X|$ require some advanced knowledge(If so could you direct me to a proof as Google and Jech's book gave me no results) or should I be able to do it without much knowledge? $\endgroup$
    – user10444
    Feb 21, 2014 at 22:34
  • $\begingroup$ It's quite easy if you know a bit about ordinals. It's pretty much the same proof that $\aleph_0+\aleph_0=\aleph_0$ (define a notion of parity on ordinals, and just repeat the same trick as before); if not you can still do it with Zorn's lemma by considering the partial order whose elements are $(S,f)$ where $S\subseteq X$ and $f$ is a bijection between $S$ and $S\times\{0,1\}$, ordered by pointwise inclusion. It's non-empty because $X$ is infinite, so it has countable subsets; and it's easy to verify Zorn's lemma. The maximal elements must be co-finite to $X$ and removing a finite set is fine $\endgroup$
    – Asaf Karagila
    Feb 21, 2014 at 22:38
  • $\begingroup$ Also, it appears in Jech Set Theory (3rd Millennium edition, 2006) on page 31; and also Asaf, with just one s. :-) $\endgroup$
    – Asaf Karagila
    Feb 21, 2014 at 22:40
  • $\begingroup$ Then I shall get started with studying ordinals.Oh and sorry about that, I even wrote complement incorrectly(I'm sleep deprived). Thanks for the help again! $\endgroup$
    – user10444
    Feb 21, 2014 at 22:48
  • $\begingroup$ Studying ordinals is probably a good idea in general. If you're unfamiliar with well-orders, then perhaps working through a Zorn's lemma based argument (as I suggested above) is a good idea for moving forward with this topic. $\endgroup$
    – Asaf Karagila
    Feb 21, 2014 at 22:52
2
$\begingroup$

Sorry for the necropost; I came across this and wanted to share a proof using only Zorn's lemma (i.e. an "elementary" proof).

Edit: "elementary" might not be the best word to use here. Perhaps "easy" is better. See comments.


Let $ P=\left\{ A \subset X\times X\colon\phi(A)\right\} $ where $\phi$ is the proposition given by: $$ \phi(A)=\forall(x,y)\in X\times X\colon(x,y)\in A\implies\psi(A,x,y) $$ and $$ \psi(A,x,y)=\forall(w,z)\in A\colon\left(x=w\iff y=z\right)\wedge x\neq z\wedge y\neq w. $$

Example: If $X=\mathbb{N}$, the set $A=\{(1,2),(3,4)\}$ would be in $P$, but the set $A^{\prime}=\{(1,2),(3,1)\}$ would not (the number $1$ appears twice).

Define a partial order on $P$ by inclusion $\subset$. Trivially, every chain in $P$ has an upper bound given by the union of the elements in that chain. By Zorn's lemma, $P$ has a maximal element, say $$ A^{\star}=\{(x_{\alpha},y_{\alpha})\}. $$ Let $X_{1}=\{x_{\alpha}\}$ and $X_{2}=\{y_{\alpha}\}$. Then $X_{1}$ and $X_{2}$ are disjoint by construction and necessarily uncountable (otherwise $X$ is not uncountable). Let $ Z= X_{1}\sqcup X_{2} $ and note that $X\setminus Z$ has at most one element, for otherwise we contradict the maximality of $A^{\star}$. Lastly, let $$ X_{1}^{\prime}= X_{1}\sqcup(X\setminus Z), $$ so that $X= X_{1}^{\prime}\sqcup X_{2}$, as desired.

$\endgroup$
3
  • 1
    $\begingroup$ How is this "elementary"? Zorn's lemma is equivalent to the axiom of choice. $\endgroup$ Jan 22, 2016 at 19:26
  • 1
    $\begingroup$ Of course. I meant in the sense that a reader with knowledge of Zorn's lemma and no previous knowledge of ordinals can digest the above (I have edited the post to reflect your point; thanks!) $\endgroup$
    – parsiad
    Jan 22, 2016 at 20:24
  • $\begingroup$ Ah, I see. +1. ${}$ $\endgroup$ Jan 22, 2016 at 20:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .