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.

  • $\begingroup$ No, sadly my lectures did not involve them. $\endgroup$ – whiskeyo Jan 6 at 13:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Git Gud Jan 6 at 13:25
  • $\begingroup$ 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? $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – whiskeyo Jan 6 at 15:34
  • $\begingroup$ @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”. $\endgroup$ – Henno Brandsma Jan 6 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.