# one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals.

I know there are a lot of ways to do this but I am looking for one in particular that I learned a few semesters ago. It has something to do with countability and i remember using diagonal lines.

I did some searching through the resources left on my blackboard form the class and found this video. the part i am talking about starts at 2:10 https://www.youtube.com/watch?v=UPA3bwVVzGI

Looking for help or even online resources about how you would write a proof like this out.( maybe not even write the proof but just properly explain it in written form) If anyone has any suggestions I would appreciate it

note: this was listed under a chapter entitled set theory: denumerable, countability and infinity if that is helpful at all.

Taking this method:

you get the map:

which is bijective and thus $|\mathbb N|=|\mathbb Q^{+}|$.

Another more rigorous approach is to show, that there are injective functions $f:\mathbb N\rightarrow \mathbb Q^{+}$ and $g:\mathbb Q^{+}\rightarrow \mathbb N$. Now from the Cantor–Bernstein–Schroeder theorem follows that $\mathbb N$ and $\mathbb Q^{+}$ must have the same cardinality. Note that the existence of $f$ implies $|\mathbb N| \le |\mathbb Q^{+}|$ and the existence of $g$ implies $|\mathbb Q^{+}| \le |\mathbb N|$.

$f$ can be the idendity function $f(n)=\tfrac n1$ and $g$ can be the Cantor pairing function $g\left( \tfrac pq\right)=\tfrac 12 (p+q)(p+q+1)+p$.

I like an approach with mediants and the Stern-Brocot tree, since it makes it easy to convert between the integer and the rational.

Every positive rational has a position within the Stern-Brocot tree, which is a binary tree, so every positive rational corresponds to a finite binary string that specifies the path you take to get to it within the tree. You can create a one-to-one map between a finite binary string and a positive integer by prepending a '1' to it then interpreting the string as a binary number.

Say you wanted to convert $\dfrac{3}{11}$ to its Stern-Brocot path. Start with the bounds $\dfrac01$ and $\dfrac10$. The mediant is $\dfrac11$, which is greater than $\dfrac{3}{11}$. So we take the left branch, write down '0', and the new max bound is $\dfrac11$.

\begin{align} \left(\dfrac01,\dfrac10\right) & \dfrac11 > \dfrac{3}{11} & '0' \\ \left(\dfrac01,\dfrac11\right) & \dfrac12 > \dfrac{3}{11} & '0' \\ \left(\dfrac01,\dfrac12\right) & \dfrac13 > \dfrac{3}{11} & '0' \\ \left(\dfrac01,\dfrac13\right) & \dfrac14 < \dfrac{3}{11} & '1' \\ \left(\dfrac14,\dfrac13\right) & \dfrac27 > \dfrac{3}{11} & '0' \\ \left(\dfrac14,\dfrac27\right) & \dfrac{3}{11} = \dfrac{3}{11} & -\\ \end{align}

The path as a binary string is "00010", so prepend a 1 to get "100010" and that is the binary for 34.