How can you tell that the list [a,b,c] is smaller than the list [w,x,y,z]? You can count them both and then compare the sizes, or you can check if every object in the first list can be compared with another different object in the second list. If we try, we'd end up with something like this:
[a:w, b:x, c:y, ?:z]
Since not every object in the first list can be paired up with the objects in the second, we know that the first is smaller. This is related to the "pigeon hole principle", which says that if you try to associate every object in a list with every object in a smaller list, then you'd have to reuse some objects in the smaller list.
So, since we cannot count the number of objects in infinite lists, we can only try to see what happens if we try to pair up the objects in the lists.
Let's start with the simplest case. Is the list of whole numbers starting from 0 [0,1,2,...] larger than the list of whole numbers starting from 1 [1,2,3,...]? Now remember than both lists are infinite in size, that is, there is no last number in either list, so you cannot reach the end in either list. So if we pair up the numbers by first, second, etc, we get this pairing:
[0:1, 1:2, 2:3, 3:4, ...]
So it is clear that every object can be paired up in both lists and so both lists are of equal size. You might not think that this makes sense because clearly the first list contains all of the numbers in the second list. That's true, but it is also true that no number will every be left out if we try to pair them up, so determining which list if bigger by checking which list contains which is not useful in infinite lists.
A more accurate proof for showing that both lists are of equal size is by writing the equation which gives the number in the second list that is paired up with a particular number in the first list. In this case, if we call the number in the first list y and the number in the second list x, such that our pairing list would be [(x:y), (x:y), (x:y), ...], then y = x+1.
What about the list of even numbers [0,2,4,...] and the list of whole numbers starting from 0 [0,1,2,...]? Well we can pair up the even numbers with their halves in the second list, like this:
[0:0, 1:2, 2:4, 3:6, ...]
Will any number be left out? Doesn't look like it will, given that there is no last number in either list.
In this case, the relationship between each pair is y = 2x.
What about the list of positive and negative whole numbers [...,-2,-1,0,1,2,...] and the list of whole numbers starting from 0 [0,1,2,...]? We can pair up the zeros together and then pair up the positive numbers with the even numbers and the negative numbers with the odd numbers, like this:
[0:0, 1:-1, 2:1, 3:-2, 4:2, ...]
Can you think of an equation which gives you which number in the second list is mapped with a particular number in the first? It requires the use of the modulo operator which gives the remainder that would result when two numbers are divided together. For example 3 mod 2 gives 1 and 4 mod 2 gives 0.
What about fractions [1/1, 1/2, 1/3, ..., 2/1, 2/2, 2/3, ..., ...] with whole numbers starting from 0 [0,1,2,...]? Well, the way we ordered the fractions makes it look impossible, but if we look at the fractions as a grid like this:
1/1 1/2 1/3 1/4 ... 2/1 2/2 2/2 2/3 ... 3/1 3/2 3/2 4/3 ... 4/1 4/2 4/2 3/3 ... ...Then we see that what we were doing was looking at the fractions row by row. But we can instead look at the diagonals. We start from the corner 1/1, then we take 2/1 and 1/2, then 3/1, 2/2 and 1/3, and we keep on going from one diagonal to the next. We end up with this pairing:
[0:1/1, 1:2/1, 2:1/2, 3:3/1, 4:2/2, ...]
Can you think of an equation to determine which fraction is paired up with a particular whole number? It requires the use of "triangular numbers" in order to know which whole number starts a new diagonal in the grid.
What about the list of all triples of numbers [(1,1,1), (1,1,2), ..., (1,2,1), (1,2,2), ..., (1,3,1), (1,3,2), ..., (2,1,1), (2,1,2), ...] and the list of all whole numbers starting from 0 [0,1,2,...]? Again, this is just a matter of changing the order just like the fractions. This time instead of a grid we have a cube of triples, which cannot be shown in text. So instead we need to order them in diagonal squares around the corner of the cube.
Can you think of an equation to determine which triple, quadruple or any size of number group will be paired with a particular whole number?
You may be thinking that any infinite list is of equal size to the whole numbers starting from zero. But what about the list of all numbers, including irrational numbers, that is, numbers which never end after the decimal point such as pi?
Let's assume that there is such a pairing. For example:
[0:0.000000000..., 1:0.100000000..., 2:1.002040000..., ...]
Can you think of a number in the list of all numbers which will not be a part of the pairings? Since the list of pairings is infinite in size and even the number of digits in each number in the list is, then we have an infinite grid, like this:
0:0.000000000... 1:0.100000000... 2:1.002040000... ...
Since we have this infinite grid of digits, we can create the following number: Take the diagonal of the grid going from the top left corner downwards. If the next digit in the diagonal is a 0, the next digit in our number must be a 9, but if it is any other digit then the next digit in our number must be a 0. In this way our new number will be different from every number in the grid. Here's an example:
0:0.000000000... 1:0.100000000... 2:1.002040000... ...
0:0.#########... 1:#.1########... 2:#.#0#######... ...
First digit in the diagonal is a 0, so the first digit in our new number must be a 9. Second digit in the diagonal is a 1, so the second digit in our new number must be a 0, third digit must be a 9, etc. So our new number in this case will look like this:
9.09...
This number will not be in the grid. Even if we included it, we can find another number which isn't in the grid using the same method. No matter how many new numbers we add to the grid, we can always find another number which isn't in the grid.
So there is no way we can pair up all the numbers with all the whole numbers starting from 0, or with all the whole numbers (positive and negative) or all the fractions. You can always find numbers which weren't paired up.
Infinite lists which can be paired up with all the whole numbers are called "countable infinite lists". These lists have a way to be ordered in such a way that no object in the list will be left out if you check every object in the list from the beginning. Infinite lists which cannot be paired up in this way are called "uncountable infinite lists". These lists cannot be ordered in such a way that you can reach any object by moving forward from the start.
This is a very interesting concept which can be extended to think about if every number can be generated using computer programs, like pi can. The number of computer programs is countable but the number of numbers isn't, so no.
What to learn more? Look up Georg Cantor who came up with these concepts.
