# Proving that an uncountable set has an uncountable subset whose complement is uncountable.

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.

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.

• 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? – user10444 Feb 21 '14 at 22:34
• 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 – Asaf Karagila Feb 21 '14 at 22:38
• Also, it appears in Jech Set Theory (3rd Millennium edition, 2006) on page 31; and also Asaf, with just one s. :-) – Asaf Karagila Feb 21 '14 at 22:40
• 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! – user10444 Feb 21 '14 at 22:48
• 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. – Asaf Karagila Feb 21 '14 at 22:52

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.

• How is this "elementary"? Zorn's lemma is equivalent to the axiom of choice. – Noah Schweber Jan 22 '16 at 19:26
• 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!) – parsiad Jan 22 '16 at 20:24
• Ah, I see. +1. ${}$ – Noah Schweber Jan 22 '16 at 20:24