Gabeland

First, some background.
The number of natural numbers (1, 2, 3, 4, …) and the number of integers (…, -2, -1, 0, 1, 2, …) are both infinite. But are they the same kind of infinite?
The answer is yes, because you can match each integer to a natural number.
Order the integers like this:
0, 1, -1, 2, -2, 3, -3, 4, -4, …
and then match each integer to its position.

But what about rational numbers? You can’t order them that easily. Or can you?
Well, you can. Let’s look at only the positive ones for the moment; making it both is relatively easy.
Take a grid of fractions like this:
1/1 1/2 1/3 1/4 1/5 1/6
2/1 2/2 2/3 2/4 2/5 2/6
3/1 3/2 3/3 3/4 3/5 3/6
etc.
and take each successive diagonal, so you get the ones where the numerator and denominator add up to 1, then 2, then 3, then 4, etc.
The order would be 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, …
However, you would get things like 2/2 or 6/3 or 7/14. And the way I’ve always seen that resolved is to just skip over them. If a fraction is the same as one before it, ignore it and move on.

But that’s unsatisfying.
Is there a way to order the rational numbers without having to arbitrarily skip things?
Let’s find out!

The problem with the previous ordering is that you can have fractions which have a shared factor in the numerator and the denominator. So we need some way to make it so that each factor can only be in the numerator or the denominator, not both.

Enter the rational prime factorization:
12/7 = 2² × 3¹ × 7^-1
This effectively turns every rational number into a finite sequence of integers.
2² × 3¹ × 7^-1 -> (2, 1, 0, -1)
It has to be finite, because each positive integer has a greatest prime factor. So after the greatest prime factor of both the numerator and the denominator have passed, there’s no more.

For the next step, we’re going to want the integers to be converted to positive integers via the ordering at the top. So (2, 1, 0, -1) becomes (4, 2, 1, 3). Keep in mind that adding 1s to the end would make it the same fraction, namely 12/7.
Now, convert each number to binary. 4 becomes 100, 2 becomes 10, 1 stays 1, and 3 becomes 11.
Take off the initial 1 (every positive integer has one), and then make all the 0s into 1s and the 1s into 2s.
Our sequence after that is (11, 1, , 2). The 3rd term is… well, these aren’t exactly numbers. But if you want, you can think of it as 0.

Lastly, put them together into a ternary number, backwards, separated by 0s.
12/7 would be 2001011, and converting back into decimal gives us 1489. There we go! We did it!

…but how do I know we don’t need to skip things? Well, the only opportunity for two of the previous sequences to be the same rational number is if you put 1s on the end of the sequence. But if you put an extra 1 at the end of the sequence, it would put a 0 on the start of the ternary number. And putting a 0 at the start of a number does nothing. In fact, it might as well already be there.

Here’s part of the list of rational numbers gotten this way:
1, 2, 1/2, 3, 4, 1/4, 1/3, 8, 1/8, 5, 6, 3/2, 9, 16, 1/16, 1/9, 32, 1/32, 1/5, …
So, to tie it all together, this shows that the rational numbers and the natural numbers are the same size, because you can pair them and have none left over.