# Bijective Correspondence Between function and cartesian product

What I'm asked to do is to find a bijective correspondence between $\mathcal F$ (set of functions with domain {0,1} and codomain $\Bbb N)$ and $\Bbb N$ X $\Bbb N$.

What I was thinking first of all was for each function, f(0) would be the first number of the element of the output $\Bbb N$ X $\Bbb N$, and f(1) would be the second number, but I'm not entirely sure how this would create any sort of bijection between $\mathcal F$ and $\Bbb N$ X $\Bbb N$. Also, I'm not sure I understand how we could possibly create a bijection considering that our codomain is a cross product of all natural numbers. Maybe I'm just not understanding something trivial. Any help would be really appreciated :)

• What is the codomain of the functions in $\mathcal{F}$? $\mathbb{N}$?
– emma
Nov 8, 2017 at 3:14
• I assume $\mathcal F$ is a set of functions ... and you're saying that these functions have a domain of $\{ 0,1 \}$ ... but then what is their co-domain? Nov 8, 2017 at 3:14
• Sorry Guys, yes N is the codomain. I'll add it to the question. Nov 8, 2017 at 3:19

Okay, so based on your suggestion let's create a map $\varphi:\mathcal{F} \to \Bbb N \times \Bbb N$, where $\varphi(f) = (f(0), f(1))$. We want to show that this map is 1-1 and onto.

Suppose that we have two functions $f, g \in \mathcal{F}$ such that $\varphi(f) = (f(0),f(1)) = (g(0), g(1)) = \varphi(g)$. Then $f(0) = g(0)$ and $f(1) = g(1)$. But since the domains of $f$ and $g$ are $\{0,1\}$, this happens preciesly when $f = g$. Thus our map is 1-1.

Next, let $(a,b) \in \Bbb N \times \Bbb N$. Then we can define $f: \{0,1\} \to \Bbb N$ such that $f(0) = a$ and $f(1) = b$. Then when have $\varphi(f) = (a,b)$, so our map is onto.

Thus $\varphi$ is a bijection, so we have a bijective correspondence between $\mathcal{F}$ and $\Bbb N \times \Bbb N$.

• Thanks for your answer. Maybe I'm not understanding something simple here, but if something is surjective, the image of the function needs to map onto the whole of the codomain right? How does this map onto all of the natural numbers? Or am I misunderstanding something here? Nov 8, 2017 at 3:34
• I think maybe you're confusing the functions in $\mathcal{F}$ and our function $\varphi$. Certainly the functions in $\mathcal{F}$ are not surjective - they're only mapping to two of infinitely many natural numbers! But, our map $\varphi$ into $\Bbb N \times \Bbb N$ IS surjective, since we can create a function in $\mathcal{F}$ that will be sent to any $(a,b)$ in $\Bbb N \times \Bbb N$. Is that difference making sense? It is difficult to get used to dealing with a set of functions!
– emma
Nov 8, 2017 at 3:36
• Yes it is. I'm just not really sure why our map $\varphi$ shows that our set of functions is countable. Nov 8, 2017 at 3:44
• Do you understand why $\varphi$ shows that we have a bijective correspondence between $\mathcal{F}$ and $\Bbb N \times \Bbb N$?
– emma
Nov 8, 2017 at 3:45
• Interesting. That’s actually blowing my mind. Thanks for the help :) Nov 8, 2017 at 4:23