What is the cardinal number of these sets :
-
$X:= \left\{ A \in P(\mathbb Z) \mid \sum_{a \in A} |a| \text{ is finite} \right\}$
-
$Y:= \left\{ B \in P(\mathbb R) \mid(\mathbb {R}\setminus B) \space \text {is countable} \right\}$
-
$Z:= \left\{ C \in P(\mathbb R) \mid|C| = \mathfrak{c} \right\}$
My solutions:
$1.$ Define $ f : \left\{x\in P(\mathbb Z) | \text {x is finite subset}\right\} \to \mathbb N$
$\space \text{defined by :} \begin{cases}
P_{lastdigit7} \space , & \text{if $y\in x>0$} \\
P_{lastdigit3}, & \text{if $y\in x<0$} \\\end{cases} $
so $f(X) = P_{y1}*P_{y2}* \cdots * P_{yn}$
$Py:=$ the prime number in the y place , $P_1 = 2 , P_2=3$ and so on..
$P_{lastdigit7}:=$ the prime number in the y place when last digit is 7 $P_1 = 7 , P_2=17$…
$P_{lastdigit3}:=$ the prime number in the y place when last digit is 3 $P_1 = 3
, P_2=13$…
I think its a bijection and its prove that is countable , $\aleph_0$.
2.We want $(\mathbb {R}\setminus B)$ to be countable so $B$ must be
uncountable .
so lets find cardinality of countable sets.
High limit : $|\mathbb R ^{\mathbb N}| = \mathfrak{c}.$
Low limit: $| \left\{0,1 \right\} ^{\mathbb N}| = \mathfrak{c}$.
So $|Y|=\mathfrak{c}$.
$P(\mathbb R)=\left\{ Countable \space subsets \right\} \bigcup \left\{
Uncountable \space subsets \right\} \implies $
$2^\mathfrak{c}=|P(\mathbb R)|=|\left\{ Countable \space subsets
\right\}| + |\left\{ Uncountable \space subsets \right\}| = $
$\mathfrak{c} + |\left\{ Uncountable \space subsets \right\}| \implies
|\left\{ Uncountable \space subsets \right\}|=2^\mathfrak{c}. $
$|Y|=2^\mathfrak{c}.$
$3.$ In excercise 2 we show that $|C|=2^\mathfrak{c}.$
Is my proofs correct ?
Best Answer
Your answer for (1) works, modulo some more careful wording, but your $f$ isn’t a bijection.
But $f$ is one-to-one. It is easy to prove that if $W$ is infinite, and there is a one-to-one function $f:W\to\mathbb N,$ then $W$ is countably infinite.
So you don’t need your $f$ to be a bijection to get the cardinality of $X$ is countably infinite.
An explicit bijection for (1).
If $x=\{a_1<a_2<\cdots <a_k\},$ then define $$f(x)=\begin{cases}0&x=\emptyset\\\sum_{i=1}^k2^{a_i+1}&a_1\geq 0\\ -1+\sum_{i=1}^k 2^{a_i-2a_1}&a_1<0 \end{cases}$$
This is slightly easier to understand by seeing that $g(x)=f(x)+1$ is a bijection with $\mathbb N^+,$ the set of non-zero natural numbers.
Given $n\in\mathbb N,$ write $n+1$ in binary:
$$n+1=2^{b_1}+2^{b_2}+\cdots+2^{b_k}.$$
With $0\leq b_1<b_2<\cdots<b_k.$
Then if $b_1=0,$ we get:
$$f^{-1}(n)=\{b_2-1,b_3-1,\dots,b_k-1\}$$
When $b_1>0,$ you get: $$f^{-1}(n)=\{b_1-2b_1,b_2-2b_1,b_3-2b_1,\dots b_k-2b_1\}.$$
I’ll leave it to you to prove this is a bijection.
This is a tricky way of doing something that is easy for the set $$X’=\{x\in P(\mathbb N)\mid x\text{ finite}\}$$ There is an easy binary encoding of $X’$:
$$f’(x)=\sum_{i\in x} 2^{i}$$
We could just use a simple bijection $g:X\to X’,$ of course, and define $f(x)=f’(g(x)),$ but I wanted a more direct numeric encoding.