1
$\begingroup$

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 :)

$\endgroup$
3
  • $\begingroup$ What is the codomain of the functions in $\mathcal{F}$? $\mathbb{N}$? $\endgroup$
    – emma
    Nov 8, 2017 at 3:14
  • $\begingroup$ 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? $\endgroup$
    – Bram28
    Nov 8, 2017 at 3:14
  • 1
    $\begingroup$ Sorry Guys, yes N is the codomain. I'll add it to the question. $\endgroup$
    – Pwned1760
    Nov 8, 2017 at 3:19

1 Answer 1

1
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – Pwned1760
    Nov 8, 2017 at 3:34
  • $\begingroup$ 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! $\endgroup$
    – emma
    Nov 8, 2017 at 3:36
  • $\begingroup$ Yes it is. I'm just not really sure why our map $\varphi$ shows that our set of functions is countable. $\endgroup$
    – Pwned1760
    Nov 8, 2017 at 3:44
  • $\begingroup$ Do you understand why $\varphi$ shows that we have a bijective correspondence between $\mathcal{F}$ and $\Bbb N \times \Bbb N$? $\endgroup$
    – emma
    Nov 8, 2017 at 3:45
  • 1
    $\begingroup$ Interesting. That’s actually blowing my mind. Thanks for the help :) $\endgroup$
    – Pwned1760
    Nov 8, 2017 at 4:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .