I was going around searching how to prove a set is countable and came across this that was used to prove that rational numbers are countable. From what I've gathered so far, a set is countable if it is either finite or if it has the same size as $\mathbb{N}$, the set of natural numbers. To show that it is countable, a correspondence must be found. How exactly does the image below show correspondence?

enter image description here

  • $\begingroup$ It shows that you can create a list of all the positive rationals, by following the arrows. Number each item of the list 0, 1, 2, ..., then this gives a bijection between $\mathbb{N}$ and the positive rationals. $\endgroup$ – Joppy Mar 20 '18 at 7:46
  • $\begingroup$ I’m leaving this in comments since it doesn’t have to do with explaining the picture, but if you have seen the Cantor Schroeder Bernstein theorem, to show a set A is countable, if you have already established that A is infinite I believe it suffices to only establish an injection from A —> N because then you have |A| geq |N| and |A| leq |N| thus by CSB |A| = |N| so that bijection must exist $\endgroup$ – Prince M Mar 20 '18 at 22:05

This diagram describes how to define a bijection $f$ from $\mathbb{N}$ to the positive rational numbers one element at a time. You define $f(0)=\frac{1}{1}$, $f(1)=\frac{2}{1}$, $f(2)=\frac{1}{2}$, $f(3)=\frac{1}{3}$, and so on, tracing out the path of the arrows. You skip the fractions marked with an X since those are equal to another fraction reached earlier (for instance, you skip $\frac{2}{2}$ because it is equal to $\frac{1}{1}$ and so you define $f(4)=\frac{3}{1}$).

Since every positive fraction occurs in the diagram and will be reached eventually by the arrows, this function $f$ will a surjection from $\mathbb{N}$ to the positive rationals. It is injective since we skip fractions which are equal to one we've already reached, so that no rational number appears more than once as an output of $f$.

(To get a bijection with all rational numbers and not just the positive rational numbers, you must modify this argument or otherwise use some additional argument.)


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.