1

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

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

1 Answers1

1

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

emma
  • 1,937
  • 1
  • 10
  • 21
  • 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? – Pwned1760 Nov 08 '17 at 03: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 08 '17 at 03:36
  • Yes it is. I'm just not really sure why our map $\varphi$ shows that our set of functions is countable. – Pwned1760 Nov 08 '17 at 03:44
  • Do you understand why $\varphi$ shows that we have a bijective correspondence between $\mathcal{F}$ and $\Bbb N \times \Bbb N$? – emma Nov 08 '17 at 03:45
  • Honestly no not really. – Pwned1760 Nov 08 '17 at 03:51
  • Okay, so there's various parts where you could get lost: do you understand how we're defining $\varphi$? Do you understand why $\varphi$ is 1-1? Do you understand why it is onto? – emma Nov 08 '17 at 03:53
  • Remember, $\mathcal{F}$ is just a set. Yes, its elements are functions, but we're just treating them like the elements of any set. And we're defining a map, $\varphi$, between two sets: $\mathcal{F}$ and $\Bbb N \times \Bbb N$. – emma Nov 08 '17 at 03:54
  • The only thing I'm not really understanding is how we can say that our map shows that there exists a bijective correspondence between F and N X N. I feel like I just might need to reread your answer with the question a couple of times to really digest what is going on. – Pwned1760 Nov 08 '17 at 04:01
  • Okay, just to check: the definition of having a bijective correspondence between two sets is that we can find a bijection between the two sets. So if you agree that $\varphi$ is a bijection, then we're done. Otherwise, let it sit for a bit and feel free to ask more if it doesn't click. – emma Nov 08 '17 at 04:07
  • Maybe one more quick question to then. So what you’re saying is that bijection phi gives a 1-1 correspondence between all the elements in F and all the elements of N X N right? – Pwned1760 Nov 08 '17 at 04:14
  • Yes, that's exactly right – emma Nov 08 '17 at 04:20
  • 1
    Interesting. That’s actually blowing my mind. Thanks for the help :) – Pwned1760 Nov 08 '17 at 04:23