Prove that there are as many even numbers as natural numbers.
Solution
The natural numbers are the “counting” numbers like 1, 2, 3, 4 etc. There is an infinite number of natural numbers. There is also an infinite number of even numbers. You’d imagine that there are more natural numbers then even numbers because the natural numbers are comprised of both the evens and the odds, but you would be wrong.
1 <-> 2
2 <-> 4
3 <-> 6
4 <-> 8
5 <-> 10
6 <-> 12
7 <-> 14
8 <-> 16
. .
. .
. .
What does this mean? For every natural number, there is also an even number. This means that both infinite sets are the same size, which is what we call “countably infinite”. This distinguishes it from sets that are “uncountably infinite”, like the real numbers or the complex numbers. You can’t set up a one-to-one correspondence between the natural numbers and the real numbers, for example.
We can set up a one-to-one correspondence between the natural numbers and the even numbers that shows that for every natural number there is also an even number. Think about it this way: every natural number has a number that is twice as large as it, and every even number has a natural number that is half its size.
2 <-> 4
3 <-> 6
4 <-> 8
5 <-> 10
6 <-> 12
7 <-> 14
8 <-> 16
. .
. .
. .
What does this mean? For every natural number, there is also an even number. This means that both infinite sets are the same size, which is what we call “countably infinite”. This distinguishes it from sets that are “uncountably infinite”, like the real numbers or the complex numbers. You can’t set up a one-to-one correspondence between the natural numbers and the real numbers, for example.
Other countably infinite sets include the rational numbers and the odd numbers.
Source: thisinsider.com