In proving set of positive rational numbers is countable, normally we use the way "Connecting the numbers diagonally". Connecting rational numbers "Diagonally"
In this way,we can list out all the rational numbers. But may I know what the bijective function that connects Q and N is?, since we need a bijection between two sets to show that they are having same cardinality.
Thank you.
The way you get a bijection is to simply skip the duplicates. The easiest way to do it is to only count the fractions in maximally cancelled form.
Note that for the purpose of this post, I assume that $0\notin\mathbb N$.
So you start with $1/1$. That is the totally cancelled form, so it gets assigned the number $1$. Next come $2/1$ and $1/2$. They are also totally cancelled, so they get assigned $2$ and $3$.
The next diagonal is where it gets interesting: $3/1$ is still totally cancelled, so we assign is the next number, $4$. But $2/2$ is not totally cancelled (numerator and denominator have a common factor $2$), therefore we skip it and do not assign it a number. If we did, we would have assigned two different numbers to the value $1=1/1=2/2$. Since we skip it, the next number considered is $1/3$, which again is totally cancelled and therefore gets assigned the next natural number, $5$.
Note that (apart from the fully-cancelled shortcut) this generally applies: Whenever for any infinite set $X$ you have a surjection $f:\mathbb N\to X$, you can get a bijection $g:\mathbb N\to X$ by simply skipping duplicates.
Moreover note that to show that a bijection exists, you don't need to provide an explicit bijection. The Schröder-Bernstein theorem guarantees you that whenever you have an injection both ways, there does exist a bijection.
Moreover, if we have a surjection $X\to Y$, then there exists also an injection $Y\to X$ (assuming the axiom of choice, but in the case of $X=\mathbb N$, not even that is needed). The way to get that is basically the skipping process outlined above. Therefore if you can show both an injection and a surjection from $X\to Y$ you have proved that a bijection exists.
Since the diagonal counting without skipping gives a surjection $\mathbb N\to\mathbb Q^+$ (every number is reached), and an injection $\mathbb N\to\mathbb Q^+$ is trivial, this already proves the existence of a bijection.
