# Construct bijections of given sets to show that they have the same cardinality and prove they are correct

I need to construct bijections of few sets to show that they have the same cardinality and prove their correctness. I have already done $$f: \mathbb{N}\rightarrow\mathbb{Z}$$, which was not very hard, but I am struggling with a bit more complex examples.

In the following examples $$a \bot b$$ means, that $$a$$ and $$b$$ are coprime numbers.

Ex. 1: $$\mathbb{N}$$ and $$\{\langle n,m\rangle \in \mathbb{N}^+\times\mathbb{N}^+ \:|\: m\bot n\}$$
It should be a function of the form $$g: \mathbb{N}\rightarrow \mathbb{N}^+\times \mathbb{N}^+$$, but I do not know how should a function of one number create a pair of coprime numbers.

Ex. 2: $$\{\langle n,m\rangle \in \mathbb{N}^+\times\mathbb{N}^+ \:|\: m\bot n\}$$ and $$\mathbb{Q}^+$$
There the function should have the form $$h:\mathbb{N}^+\times\mathbb{N}^+\rightarrow \mathbb{Q}^+$$ and I was thinking about a function which would divide $$n$$ by $$m$$, which in my opinion would be pretty understandable, but I am not sure whether it is a correct idea.

I would like to get some tips how should I get a grasp in solving such problems, as well as some hints how to solve and prove these two examples.

• No, sadly my lectures did not involve them. – whiskeyo Jan 6 at 13:10
• For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air. – Git Gud Jan 6 at 13:25
• Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $\mathbb{Q}$ is countable, or that $\mathbb{N}^{2}$ has the same cardinality as $\mathbb{N}$. If so can you adapt that proof? – Adam Higgins Jan 6 at 13:51

For $$2$$ we have the obvious map sending $$(m,n)\in C$$ to $$\frac{m}{n} \in \mathbb{Q}^+$$, where $$C$$ are the co-prime pairs of positive integers. It's onto and 1-1 because every positive rational has a unique representation as a quotient of co-prime positive integers (after cancelling common factors in numerator and denominator).
As to $$1$$, did you do a bijection from $$\mathbb{N}$$ to $$\mathbb{N}^2$$? You could use that for the subset $$C$$ as well: If $$f$$ is that earlier bijection, define $$g: \mathbb{N} \to \mathbb{N}$$ recursively by $$g(0) = \min \{n: f(n) \in C\}$$ and $$g(n+1) = \min\{n : n > g(n) \text{ and } f(n) \in C\}$$ and then $$h(n) := f(g(n))$$ is a bijection from $$\mathbb{N}$$ to $$C$$.
• When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $\mathbb{N}^2$ to $\mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done. – whiskeyo Jan 6 at 15:34
• @whiskeyo if $f$ is a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $\mathbb{N}$ which you then enumerate to get a bijection with $\mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”. – Henno Brandsma Jan 6 at 16:11