Is there any infinite set which has no disjoint infinite subsets?
I claim that the answer is NO!

Let $S$ be any infinite set. Take a countable subset $A$ of $S.$ Then we can find a bijection $f:A\to\mathbb{N}.$ Define $B=\{b\in A:f(b)\, \text{is even}\}$ and $C=\{c\in A:f(c)\,\text{is odd}\}.$
Then clearly $B$ and $C$ are disjoint infinite subsets of $S.$
Hence we are done.

Am I correct?
If this is correct, this proof is depend on the fact that "Every infinite set has a countable subset."
Can we prove the same result without using above fact?

  • 2
    $\begingroup$ Yes, what you've done is correct. I personally can't think of anything which doesn't end up just proving the statement "every infinite set has a countable subset" in the process. Are you trying to avoid using Axiom of Choice? $\endgroup$ – Hayden Sep 15 '16 at 22:36
  • 1
    $\begingroup$ @Hayden: Yes. I tried to avoid AC. But Asaf Karagila tald that it is impossible. $\endgroup$ – Bumblebee Sep 15 '16 at 22:49
  • $\begingroup$ Not quite. Countable set A is not stated to be infinite, therefore B and C are not proven to be infinite. In other words, find me a bijection from the empty set to N :-) $\endgroup$ – pedant Sep 16 '16 at 2:43
  • 1
    $\begingroup$ "Countable" in this context has the meaning "countably infinite." $\endgroup$ – Christian Mann Sep 16 '16 at 3:36
  • 1
    $\begingroup$ @Meni: While I am not disagreeing with you, I do find it very rare when any set theorist uses "denumerable" rather than "countable" when talking only about countably infinite (but we're used to it enough to understand it from the context). In the basic set theory course for the last couple of years the convention was that "countable" always means "countably infinite" (you could blame Hebrew for lack of diversity on this aspect, but nevertheless, this is something that can be found elsewhere). $\endgroup$ – Asaf Karagila Sep 16 '16 at 8:04

Assuming the axiom of choice, yes. Every infinite set has a countably infinite subset. Since we can split a countable set to two disjoint infinite sets, we can split the original set into two disjoint infinite sets.

However, without the axiom of choice it is consistent that there is an infinite set which cannot be split into two disjoint infinite sets. Such a set is called amorphous.

  • $\begingroup$ I vaguely remember hearing about infinite sets such that if one element is remove their cardinality is reduced (of course without the axiom of choice), am I hallucinating or is this a thing? $\endgroup$ – JKEG Sep 22 '16 at 3:00
  • $\begingroup$ They are called Dedekind finite sets, or rather infinite Dedekind finite sets. It is consistent that such sets exist. In fact, it is consistent to have a set of reals with this property. $\endgroup$ – Asaf Karagila Sep 22 '16 at 4: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.