Saturday, 18 January 2014

An infinity of infinities.

So, I mentioned that there was an infinity of infinities. This is atually fairly technical to prove, but the reason why can be explained in a sort-of-intuitive manner, so that's what I'm setting out to do in this post: actually give a manner to, given a set, build a new, bigger set from it.

In the first post, I mentioned that set are defined by their cardinality, and that we can't make their elements interacts, this is true, but there is actually one operation we can do on a set: we can take a part of it.

For instance, if we have the set $\{a,b,c\}$, a part of it could be $\{a,b\}$. So let's consider that set $\{a,b,c\}$, and look at all the different parts it may have:

The part with 0 element: $\varnothing$
The parts with 1 element: $\{a\}, \{b\}, \{c\}$
The parts with 2 elements: $\{a,b\}, \{a,c\}, \{b,c\}$
The part with all 3 elements: $\{a,b,c\}$

(note: $\varnothing$ is a notation for the empty set, containing no element)

Now, and this is the funny part, all those things can now be considered elements... And we can build a new set containing those, so if X is a set, we can consider $\mathcal{P}(X)$, the set made of all the parts of the set X. So in our example, we would have:

$$X = \{a,b,c\} \\ \mathcal{P}(X)= \{\,\varnothing, \{a\}, \{b\}, \{c\},\{a,b\}, \{a,c\}, \{b,c\},\{a,b,c\}\, \}$$

So we can see what we managed to do: we had a set of size 3, and we've used it to build a set of size 8. Note that the process can be re-iterated, our $\mathcal{P}(X)$ is, itself, a set, so we can consider its parts, and create a new set containing all the parts of this set (what we would note $\mathcal{P(P}(X))$, but that's not important). And if I'm not mistaken, this new set would probably contain 256 elements.

Now the fact that a set is infinite can't stop up from considering its parts... Though obviously, they might be very weird-looking. For instance, in the case of the integers, a part might be just a finite number of integers, or it might be everything except a finite number of integers, or it can be an infinite part of the integers with an infinite part leftover (like, all odd integers for instance), it can be basically ANYTHING, it doesn't even have to be expressable as a formula, it could be an infinite set or arbitrarily chosen integer, it doesn't matter.

So already, we can see that there are a LOT of parts we can take, with a set as simple as "the integers".

Now the leap of faith, for which you'll have to take my word for it (partly because I don't remember the proof, but also because what I remember of it is too technical for this blog): but whatever your set X is, the set $\mathcal{P}(X)$ is always strictly bigger than the set X. And that is true for infinite sets too.

So our set of all integers $\mathbb{N}$ is infinite, but the set $\mathcal{P}(\mathbb{N})$ is a bigger infinite.

And now we just have to reiterate this process over and over again... The set $\mathcal{P}(\mathcal{P}(\mathbb{N}))$ is a bigger infinite than $\mathcal{P}(\mathbb{N})$, and is "two steps" bigger than $\mathbb{N}$, and so on... So here we have it, our infinite number of infinities. It's not very visual, so it might not be really satisfactory, but it still works.