Let $$C_s = \left\{ f\in \mathbb{N}/S \to \mathbb{N} : \forall M\in \mathbb{N} / S. f(M)\in M \right\}$$

Where $S$ is an equivalence class.

I need to prove $$\left|C_s\right| > \aleph_0 \implies \left|C_s\right| = \mathfrak{c}$$ And I am not allowed to assume there's no $\aleph_0 < a < \mathfrak{c}$ (Continuum hypothesis).

Start of proof:
$\left|\mathbb{N}/S\right|$ can't be finite because then, $\left|C_s\right|$ was also finite/countable.
Therefore, $\left|\mathbb{N}/S\right|$ must be infinite.

Since $\left|\mathbb{N}/S\right|$ is infinite but $\left|\mathbb{N}/S\right| \le \left|\mathbb{N}\right|$ it implies $\left|\mathbb{N}/S\right| = \aleph_0$

So far so good.

Now, the author claims:

"A finite number of equivalence classes with an infinite cardinality isn't possible since, if so then $\left|C_s\right|=\aleph_0$. And therefore, we have a set with $\aleph_0$ equivalence classes with the cardinality of $\aleph_0$. Hence, $\left|C_s\right|\ge\mathfrak{c}$"

I don't understand this claim completly and I'd be glad if someone could explain it me.

My guess:
Is the claim true because the cardinaliy of all finite subset of $\mathbb{N}$ is $\aleph_0$?

  • $\begingroup$ I've replace $\aleph$ with $\mathfrak{c}$. See here. $\endgroup$ – Frunobulax Sep 7 '14 at 13:45

I think the author's claim is wrong:

Let $M_n = \{2n,2n+1\}$ for $n\in\mathbb{N}$ and let $\cal P$ be the partition $\{M_n \mid n \in \mathbb{N} \}$ of $\mathbb{N}$. (And note that we assume $0\in\mathbb{N}$ as is usual in set theory.) So, ${\cal P}=\{\{0,1\},\{2,3\},\{4,5\},\dots\}$. This is the set of equivalence classes of some equivalence relation $S$ on $\mathbb N$ and all equivalence classes (all elements of $\cal P$) are finite.

Now, for $g\in \{0,1\}^\mathbb{N}$ define $f_g:{\cal P}\rightarrow\mathbb{N}$ as $f_g(M_{n}) = \min M_{n}$ if $g(n)=0$ and $f_g(M_{n}) = \max M_{n}$ if $g(n)=1$. Obviously, $f_g \in C_S$ for all $g\in \{0,1\}^\mathbb{N}$ and $f_g\neq f_h$ for $g\neq h$ which implies $|C_s|\geq 2^{\aleph_0} = \mathfrak{c}$.

  • $\begingroup$ Thank you so much for your efforts. I really appreciate it! $\endgroup$ – Aharon Sep 7 '14 at 14:36

Here's an idea how to prove the original claim:

If $C_S$ is uncountable, then it is not possible that only finitely many equivalence classes of $S$ have more than one element. Because otherwise let $M_0,M_1,M_2,\dots$ be an enumeration of $\mathbb{N}/S$. By assumption there'd be a $k\in\mathbb{N}$ with $|M_n|=1$ for all $n\geq k$. This would imply $|C_S|\leq |\prod_{n=0}^{k-1} M_n| \leq \aleph_0^k = \aleph_0$ (as two distinct elements of $C_s$ can only differ on at most the first $k$ sets $M_0,\dots,M_{k-1}$).

In other words, you know you can find infinitely many equivalence classes with at least two elements and you can now proceed as in my previous answer. (Use the second element instead of the maximum as the maximum won't always exist.) This shows $|C_s|\geq\mathfrak{c}$.

$|C_s|\leq\mathfrak{c}$ is obvious because of $|C_s|\leq\aleph_0^{\aleph_0}=2^{\aleph_0}=\mathfrak{c}$.


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.