Let $\Omega$ be an uncountable set. Without assuming the axiom of choice, does there exist a subset $S\subset \Omega$ such that neither $S$ nor $\Omega\setminus S$ is countable?


Impossible. It is consistent with ZF (i.e. Zermelo-Frankel set theory without axiom of choice) that there is an infinite set $X$ such that if $A$ and $B$ divides $X$ (i.e. $A\cap B = \varnothing$ and $A\cup B = X$) then either $A$ or $B$ must be finite. Such set is called amorphous set. Of course, such set does not exist when assuming choice.

If $X$ is amorphous and $S\subset X$, then one of $S$ or $X-S$ should be finite, so it is impossible that both $S$ and $X-S$ are uncountable. Moreover, countable set should not be amorphous, since we can divide countable sets into two countable sets (e.g. divide $\Bbb{N}$ into odds and evens) so any amourphos set is uncountable. (In fact, every amorphous set can not contain countably infinite subsets.)

  • 1
    $\begingroup$ If you allow me, I would suggest you to include in your answer that an amorphous set can NOT be countable. $\endgroup$ – Ramiro Oct 1 '15 at 4:28
  • $\begingroup$ @Ramiro Thanks for your comment. I add it. $\endgroup$ – Hanul Jeon Oct 1 '15 at 4:55
  • $\begingroup$ I see: even the existence of a countable subset of an uncountable set relies on the axiom of choice. $\endgroup$ – pre-kidney Oct 1 '15 at 6:22
  • $\begingroup$ @pre-kidney: You can actually construct $\aleph_1$-amorphous set, where every subset is countable or co-countable. These sets can carry quite a lot more structure than just amorphous sets. $\endgroup$ – Asaf Karagila Oct 1 '15 at 6:34

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.