2

I've proven that $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $f(m,n)=2^{m-1}(2n-1)$ is a bijection.

How do I show that the function $g:\mathbb{N}\times\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $g(k,m,n)=f(k,f(m,n))$ is a bijection by writing it as a composition of functions $\mathbb{N}\times\mathbb{N}\times\mathbb{N}\to\mathbb{N}\times\mathbb{N}\to\mathbb{N}$?

Then do I conclude with the fact the $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$ is denumerable a composition of such would be denumerable and thus $\mathbb{N}\times\mathbb{N}\times\mathbb{N}$ is?

Theo Bendit
  • 50,900
Ben French
  • 135
  • Imagine the cube-like lattice of coordinates in $\mathbb{N}^3$. Order them according to distance from the point $(0,0,0)$, breaking ties arbitrarily. Countable.Edit: if you want to spend the time to do it, you could write down an explicit bijection between $\mathbb{N}$ and $\mathbb{N}^3$, but that's not necessary to show it's countable – Zubin Mukerjee Nov 23 '17 at 03:04
  • Well, $\mathbb{N}^3$ = $\mathbb{N} \times \mathbb{N}^2$. Those are both countable as you've proved. Maybe you can take it from there. – qualcuno Nov 23 '17 at 03:05

1 Answers1

3

You have $f : \mathbb{N}^2 \to \mathbb{N}$, that is bijective. As you've correctly intuited, the map $g(a, b, c) = f(f(a, b), c)$ is a bijection between $\mathbb{N}^3$ to $\mathbb{N}$. We just have to prove it.

First, injectivity. Suppose that $g(a_1, b_1, c_1) = g(a_2, b_2, c_2)$. From this, we obtain $$f(f(a_1, b_1), c_1) = f(f(a_2, b_2), c_2).$$ Injectivity of $f$ implies that, $$(f(a_1, b_1), c_1) = (f(a_2, b_2), c_2),$$ which in turn implies that $c_1 = c_2$ and $f(a_1, b_1) = f(a_2, b_2)$. Using injectivity of $f$ a second time implies that $(a_1, b_1) = (a_2, b_2)$, and so $a_1 = a_2$, $b_1 = b_2$, and of course, $c_1 = c_2$. Therefore, in total, we have $(a_1, b_1, c_1) = (a_2, b_2, c_2)$, and injectivity is proven.

Have a go at surjectivity. Again, it's just a matter of using the surjectivity of $f$ twice. The actual definition of $f$ should not matter, just so long as it is a bijection!

Theo Bendit
  • 50,900