1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Taking this method:

bild

you get the map:

bild2

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.