I was watching Veritasium’s video about math having a fatal flaw. He explained that if we make a set of all the numbers in between 0 and 1, then added one to the first digit of the first number and added one to the second digit of the second number etc, we would always have a new number. He said this proved that there were more numbers in between 0 and 1 than natural numbers.
I was confused as to why you can’t do this with natural numbers, and how that proved one infinity was smaller than another.
In: Mathematics
Firstly, here is a key term: bijection.
A bijection is a pairing up of the elements of two sets such that every element of the first set is paired up with a single element of the second set, and there are no unpaired elements in the second set.
For example, if we have two sets {1, 2, 3} and {a, b, c}, we can create a bijection by pairing them up like this: 1→a, 2→b, 3→c. Since we can create a bijection between those two sets, that tells us that the two sets are the same size.
Similarly, if we can’t create a bijection between two sets, they must be different sizes. For example {4, 5} and {d, e, f}. No matter how we pair things up, we cannot create a bijection between those two sets. 4→d, 5→e pairs up every element of the first set, but ‘f’ gets left unpaired. 4→d, 4→e, 5→f makes sure there are no unpaired elements in the second set, but 4 got paired up twice, and it can only be paired up once to count as a bijection.
You might be wondering why mathematicians use bijections to compare the sizes of sets. Why don’t they just *count* the number of elements?
But, think about what you do when you count things. You look at one object and say “one”, then the next and say “two”, and so on until you’ve looked at each object and said a number. What you’ve just done is created a bijection between the group of objects and a subset of the natural numbers. If we go back to the example of {1, 2, 3} and {a, b, c}, if someone asked you to count the number of elements in that second set, then the pairing 1→a, 2→b, 3→c is probably exactly what you would do.
Now, to bring things back to your original question: as I said, if you can show that a bijection can’t be formed between two sets, then we must conclude that the two sets are different sizes. And that’s exactly what Cantor’s goal was with his diagonalization argument. The way the argument works is that it shows that for any pairing between the natural numbers and the interval (0, 1), there’s always going to be a number in the interval that gets left out, and isn’t paired with a natural number, similar to our example above with 4→d, 5→e leaving out ‘f’.
Why doesn’t this work with the natural numbers themselves? Well, let’s try it out. Firstly, we’re going to have to write the naturals with infinite zeros after the decimal place (as in 1.000…, 2.000…, etc.) so that we can talk about arbitrary digits (if we didn’t do this then we would have a problem if we had to talk about the 17th digit of the number 8 or something). Then, if we go down the list, creating a new number by adding 1 to nth digit of the nth number, what we’re going to end up with is a number that ends in an infinite string of ones after the decimal place.
Now, the thing about this number that we’ve created is that it’s not a natural number (it would be a rational number), which means it’s not supposed to be on list in the first place! It’s not a problem for the same reason that 1→a, 2→b, 3→c leaving out ‘f’ isn’t a problem. {a, b, c,} doesn’t include ‘f’, so a bijection shouldn’t (and can’t) include it. The set up I described above isn’t the only way to try to diagonalize the naturals, but they all have the same problem, in that whatever number you create isn’t going to be a natural.
So to sum it all up, with the interval (0, 1), a diagonalization is guaranteed to create a number between 0 and 1, but with the naturals a diagonalization is going to create a non-natural number. That’s the difference between the two and that’s why the same argument doesn’t apply.
Latest Answers