Vtgyjfy

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_1sim A_2$, $B_1sim 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 nleq 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:Arightarrow B$ and $g: Brightarrow 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}rightarrowmathbb{N}big)$, which confuses me a lot and I have no idea how should it work.

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_1sim 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}rightarrowmathbb{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:

• 
  ${0,1}^X$ is in bijection with the power-set of $X$, using the idea of indicator functions.


• A function $f:X rightarrow Y$ can be thought of as a set of ordered pairs $(x,f(x))$. This will let you establish $mathbb{N}^mathbb{N}$ as a subset of a particular power-set.

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}$