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.

  • $\begingroup$ Think of $\{0, 1\}^\mathbb{N}$ and $\mathbb{N}^\mathbb{N}$ as collections of sequences, which is another way to think of these spaces. $\endgroup$ – twnly Jan 13 at 2:36

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:

  • $\{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}$

  • $\begingroup$ To the first problem, we can construct injection $A_2\rightarrow B_2$, as there exists injection $g: A_1\rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that $\{0,1\}^\mathbb{N}$ is a subset of $\mathbb{N}^\mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round. $\endgroup$ – whiskeyo Jan 13 at 3:01
  • $\begingroup$ For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away. $\endgroup$ – Chessanator Jan 13 at 3:29
  • $\begingroup$ For the second part, play around with the two details I gave you. $\{0,1\}^\mathbb{N}$ is (in bijection with) some power-set. $\mathbb{N}^\mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them. $\endgroup$ – Chessanator Jan 13 at 3:31
  • $\begingroup$ When it comes to the injection $\mathbb{N}^\mathbb{N}\rightarrow \{0,1\}^\mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,\dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,\dots)$ would be $1,1,0,1,0,1,1,1,0,\dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct? $\endgroup$ – whiskeyo Jan 13 at 15:00

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.