I have recently been studying cardinality of finite and infinite sets and the 'theory part' was not hard to understand, but it is pretty problematic for me to apply any of the definitions to solve problems.
The first problem is following and I am not sure whether I solved it correctly:
Does $A_1\sim A_2$, $B_1\sim B_2$ and $|A_1|\leq|B_1|$ implies that $|A_2|\leq|B_2|$?
My answer is yes, as $A_1$ is equinumerous to $A_2$ and $B_1$ is equinumerous to $B_2$, we may assume that $|A_1|=|A_2|=n$ and $|B_1|=|B_2|=m$.
Then, $|A_1|\leq|B_1| \equiv n\leq m$.
As $n=|A_2|$ and $m=|B_2|$, we get that $|A_1|\leq|B_1| \Rightarrow |A_2|\leq|B_2|$.
The second problem is connected with Cantor-Bernstein theorem, which says that if $|A|\leq|B|$ and $|B|\leq|A|$, then $|A|=|B|$. Using the theorem we can determine the cardinality of sets $A$ and $B$ by constructing two injective functions $f:A\rightarrow B$ and $g: B\rightarrow A$.
My job is to construct injective functions to show that $\{0,1\}^\mathbb{N}$ and $\mathbb{N}^\mathbb{N}$ have the same cardinality, but I do not know how do I construct such functions:
$f: \{0,1\}^\mathbb{N} \rightarrow \mathbb{N}^\mathbb{N}$,
$g: \mathbb{N}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$. Creating e.g. function $f$ requires to map
$\big(\mathbb{N}\rightarrow\{0,1\}\big)\rightarrow \big(\mathbb{N}\rightarrow\mathbb{N}\big)$, which confuses me a lot and I have no idea how should it work.
Best Answer
The way you've done the first part implicitly assumes that the sets are finite (and quite a bit more besides). It would be much better to do this in greater generality. Remember that $A_1\sim A_2$ is shorthand for "There is a bijective function $f: A_1 \rightarrow A_2$," while $|A_1|\leq|B_1|$ is shorthand for "There is an injective function $g: A_1 \rightarrow B_1$."
Given bijections $f_A: A_1 \rightarrow A_2$ and $f_B: B_1 \rightarrow B_2$, and an injection $g: A_1 \rightarrow B_1$, can you construct an injection $A_2 \rightarrow B_2$?
For the second part, bringing in bulky notation like $\big(\mathbb{N}\rightarrow\{0,1\}\big)\rightarrow \big(\mathbb{N}\rightarrow\mathbb{N}\big)$ is only going to serve to muddle matters. Instead focus on the actual substance of the sets of functions involved. For the easier half, can you see that $\{0,1\}^\mathbb{N}$ is an actual subset of $\mathbb{N}^\mathbb{N}$? That is, members of $\{0,1\}^\mathbb{N}$ are members of $\mathbb{N}^\mathbb{N}$ obeying a particular restriction?
The other way round is harder, and where it is crucial to become familiar with the way these set constructions work. The key ones for you are:
Chain together the injections you get from each of these steps and you will get the injection $\mathbb{N}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$