"Infinity and Beyond" is a series of posts about the concept of infinity, its mathematical properties and how misleading our intuition about infinity can be. It will get rather technical but I will try my best to make it as easily digestible as possible. You do not need to have studied Mathematics or a related field to understand this series.
These are the already planned parts. This list may be subject to change.
In the previous part of this article we discovered an infinite set with which we are all familiar, the set of natural numbers
Now that we have an infinite set to play around with, lets see what happens to its size if we add something to it. Say we want the number 0 to be part of it as well (as stated in part 1 we defined zero to not be a natural number). Also lets call the new set
We take the natural numbers and join them with the set that only contains the number 0 and we end up with the set we wanted. At this point try to make a prediction of how the sizes of
Our intuition may claim that
If you don't believe me or don't see how this can work keep reading. I will guide you step by step to understand this.
Warning mathematical formulae incoming. Brace yourselves but do not be worried. I will go though everything step by step and make everything as comprehensive as possible.
The great thing about mathematics is that you don't just have to (or even should) believe me. You don't even have to (or should) believe a highly decorated maths professor. Only ever trust in hard proof. So let me prove it to you.
Intermission
At this point a rather famous paradox/thought experiment should be mentioned: "Hilbert's Grand Hotel". This thought experiment used to confuse me more than it helped though, because it tries to give a pseudo real-world example of an infinite hotel, something which obviously can't exist. I am not good in wrapping my head around pseudo real-world examples trying to explain something purely theoretical. For this reason I will not go into Hilbert's Hotel but give a purely theoretical proof for our little problem. If you, esteemed reader, are interested in Hilbert's Hotel, or if those pseudo real-world examples help you, here is a good article about Hilbert's Grand Hotel.
So let's take a moment to think about how we could do this. We have two sets. Each set has elements and we need some way to compare these sets. There is one thing in mathematics that you may not have associated with sets if you are not "into" maths: Functions. Mathematically speaking function are just mappings from one set into another. Take for example this basic function:
The function g is defined to map from the real numbers into the real numbers in such a way, that the number x is mapped to the square root of x. Most everyday functions are defined over the real numbers but those too are just a set and you are free to chose different ones for your function.
Since we want to compare the two sets from earlier, namely
With our rather limited sets we now need to check that this is actually a valid function by confirming that we stay within the sets we defined. Meaning if you apply the function to any element of
(Remember that
Yup, this is okay. What else do we need to check, well for any
Okay, we have a function that maps from one of our sets into the other. Were we not here though to prove that they are the same size? How does a function help us here? As will become apparent in a moment the choice of function was deliberate. This function has some very useful properties that will help us prove what we came here to prove.
Our function
Injective means that any two distinct elements from the input set (
Surjective on the other hand means that all elements from the output set are reached by means of the function and the input set. Or in other words, there exists no element in the output set that can not be produced by the function and an element from the input set.3
Again, I will not formally prove that our function is bijective for the sake of readability, but prove it informally: Since the function
Anyone, who wants to see a formal proof of our function being a bijection can look it up here.
We have established the following.
Lets see again what bijective means. Bijective means, that the function maps each distinct element of
Image made by me
Since a bijective function from
If the input set was bigger than the output set we would have to map more than one input element to the same output element (we would run out of outputs), which would mean there can be no injective function.
If the output set was bigger than the input set we would have output elements that are not mapped at all (we would run out of inputs), which would mean there can be no surjective function.
However we did find a bijective function from
In general we can say that any two sets are the same size iff. (read "if and only if") there exists a bijective mapping/function from one set into the other.4 Casting this into mathematical terms may look like this.
(
Intermission
The abbreviation "iff." is often used in mathematics and means "if and only if". This is a convention to avoid the imprecisions of natural language. To say "A is true iff. B is true" means if A is true, B has to be true, but also if A is not true B cannot be true, and vice versa. If we used the simple "if" on the other hand, we would have an implication instead of an equivalence. I. e. a statement that is not reversible. To say "A is true if B is true" means that A is true if B is true, but if we know that B is true we do not know whether or not A is true as well.
We have just proven that adding one element to an infinite set does not change its size.
In fact adding any amount of finite elements to an infinite set does not change its size. Analogously to our function from before we could just increase how much we add to the input number.
Amazing, isn't it?
But does that mean that there is only one kind of infinity and all infinities are the same size? No, not at all! If you are curious to see something bigger than the amount of natural numbers, stay tuned for the next part.
In the meantime I hope this was understandable for everyone. If you have any questions, want to see more formal proof or want to give me some feedback, the comment section is right there for you.
There are of course more sets that are seemingly bigger than one another but are really the same size. I'll give you some examples and if you want, you can try to figure out what function would give a bijective mapping in order to prove that they are the same size. In order of increasing difficulty:
Note: Most of the proofs were informal for the sake of digestibility. However, if you want to see formal proofs for anything in this article let me know in the comments and I will provide them.
Equations created with latex2png.
