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.


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.

  • $\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 '14 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 '14 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 '14 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 '14 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 '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.

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

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.