1
$\begingroup$

How to prove that if a set with cardinality of continuum is divided into aleph zero many subsets, then at least one of them has cardinality of continuum? (Of course without assuming the Continuum hypothesis)

Edit: Not precise formulation.

$\endgroup$
4
  • $\begingroup$ A countable union of countable sets is... $\endgroup$
    – JMoravitz
    Feb 1, 2017 at 23:01
  • $\begingroup$ If all of them are countable so their sum is countable. But that indicates that the cardinality is not aleph zero. But I cannot infer from here that one of them is continuum. I infer that all of them are not countable. $\endgroup$
    – guser
    Feb 1, 2017 at 23:07
  • $\begingroup$ So I guess it doesn't imply that one of them is uncountable. $\endgroup$
    – guser
    Feb 1, 2017 at 23:08
  • 1
    $\begingroup$ At this point the question is precise, and quite interesting - surprisingly, the answer is yes, but not easily so! See my answer. $\endgroup$ Feb 1, 2017 at 23:16

2 Answers 2

3
$\begingroup$

EDIT: Now that you have clarified your question, I can answer it. The answer to this, perhaps surprisingly, is yes, regardless of whether CH holds! This follows from Koenig's Theorem, which implies that $cf(2^{\aleph_0})>\omega$: if $\mathbb{R}=\bigcup_{i\in\mathbb{N}}A_i$, let $\alpha_i=\vert A_1\cup A_2\cup . . . \cup A_i\vert$; then $\sup\alpha_i=2^{\aleph_0}$, but if each $A_i$ has size $<2^{\aleph_0}$, each $\alpha_i$ is $<2^{\aleph_0}$ (exercise), so the sequence of $\alpha_i$s is a length-$\omega$ sequence cofinal in $2^{\aleph_0}$ - a contradiction.

Note that choice is necessary here: in fact, without choice it is consistent that $\mathbb{R}$ is the union of two sets of strictly smaller cardinality!


EDIT 2: Here's a direct proof, without invoking Koeneig's theorem (although the argument below basically is the proof of Koenig's theorem):

Remember that the set $\mathbb{R}^\mathbb{N}$ of functions from $\mathbb{N}$ to $\mathbb{R}$ also has size continuum; we'll show that if we partition this set into countably many pieces, one must have size continuum.

Suppose otherwise. Let $A_i\subset \mathbb{R}^\mathbb{N}$ have size $<2^{\aleph_0}$, for $i\in\mathbb{N}$. Then for each $i$, there is some real $r_i$ such that whenever $s\in A_i$, we have $s(i)\not=r_i$. (Why not?) But now consider the function $$f(i)=r_i.$$ This $f$ is an element of $\mathbb{R}^\mathbb{N}$, but not in any $A_i$.

$\endgroup$
4
  • $\begingroup$ Thanks for the your answer. But Is there any simpler solution? This was an exam question on one of the previous years, but we haven't covered the Koenig's Theorem. $\endgroup$
    – guser
    Feb 1, 2017 at 23:26
  • 1
    $\begingroup$ @guser I've put up a solution not involving KT, but it really is just the proof of KT. $\endgroup$ Feb 2, 2017 at 0:16
  • $\begingroup$ The result about splitting the reals into two parts is actually due to Monro, ams.org/mathscinet-getitem?mr=325394, and also if we talk about a failure of Koenig's theorem, then the Feferman-Levy model is probably the OG result from 1964 (no citation, as it was announced in Notices of the AMS). $\endgroup$
    – Asaf Karagila
    Feb 2, 2017 at 5:04
  • $\begingroup$ (By the way, VanLierre's thesis does not cite Monro's work. I think that he just wasn't aware of it.) $\endgroup$
    – Asaf Karagila
    Feb 2, 2017 at 6:23
2
$\begingroup$

Here is a fairly direct argument (this is really the same as Noah's answer; I'm just implementing the proof of König's theorem in this particular case). Suppose $X=\bigcup_{n\in\mathbb{N}} X_n$ has cardinality $\mathfrak{c}$ but each $X_n$ has cardinality less than $\mathfrak{c}$. Since $\mathfrak{c}^{\aleph_0}=\mathfrak{c}$, there exists a bijection $f:X\to X^\mathbb{N}$. For each $n$, let $s_n\in X$ be some element which is not the $n$th coordinate of $f(x)$ for any $x\in X_n$ (such an $s_n$ exists since $|X_n|<|X|$). Now consider the sequence $s=(s_n)\in X^{\mathbb{N}}$. Since $f$ is surjective, $s=f(x)$ for some $x\in X$, and $x\in X_n$ for some $n$. But by construction, the $n$th coordinate of $s$ is then different from the $n$th coordinate of $f(x)$. This is a contradiction.

$\endgroup$

You must log in to answer this question.

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