# Why is it sufficient to show something is countable as follows?

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? • 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. – Joppy Mar 20 '18 at 7:46
• 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 – Prince M Mar 20 '18 at 22:05

## 1 Answer

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