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.

To infinity... And beyond !

Last time I mentioned that there are an infinity of infinities, and yet, the only proof I gave was of two infinities who were the same... In this post, I'll show an example of a bigger infinity (which, surprisingly, won't be that big) as well as prove that it is, indeed, bigger.

But first things first, let's remember what it means for two sets to have the same cardinal: it means that we're able to create a function that has a one-to-one correspondence between the elements of the first set, and the elements of the second set.

Also, before we even start, I'd like to explain what I'm going to do: it's called a proof by contradiction, though I like our french expression better which would translate by "reasoning to the absurd". The point is that we have something we want to prove is false, so we consider it true and we reason from there. The goal being to end up with a contradiction, something absurd. In which case one of two things happened: either we went wrong during our proof, or our original assumption was not true (thus false).

First, a tiny bit a of notation. The set of all positive integers is usually noted $\mathbb{N}$. The set containing all numbers (including decimals, and so on) between 2 numbers is noted between square brackets, like this: $[0,1]$. This would be the set containing any real number between 0 and 1, including 0 and 1, as well as every fraction between 0 and 1, as well as some numbers that aren't even possible to write as a fraction (and there's a metric shit-ton of those). 

Anyway, what we're going to do is prove that the second set is bigger than the first. Sounds counter-intuitive ? That's half the fun ! Here we go.

Let 
$$X = \mathbb{N}
\\
Y = [ 0, 1]
\\
f: X \rightarrow Y $$

That last notation means that f is a function that takes an element of X and associates it an element of Y. On top of that, let's ask for that function to be a bijection.

Now comes the hard part. We're going to prove that even though the function is supposed to be a bijection, so among other things supposed to reach every number between 0 and 1, we can actually find a number between 0 and 1 that isn't reached by the function.

The argument we're going to use is both pretty cool and pretty weird at the same time, it's called Cantor's diagonal argument. We're going to look at all the numbers between 0 and 1 that are reached by our function, and create a new one from that.

The first thing to consider, is that every number can be written with an infinite decimals. It's actually pretty stupid: if you consider 0,5, nothing's stopping you from writing it "0,500000000...". What we're going to do is this: for each integer, we'll look at the number it's associated to, and look at the number of the decimal part at the position equal to the integer we're considering. Read that sentence several times, realise it's still not super-clear, and let me give you an example.

Let's say that 1 is associated to 0,723; then we'll look at the first number of the decimal part, which is 7. If 5 is associated to 0,2 3 6 4 2 3 7 3; we'll consider the 5th number, which is 2. Clearer ? If not, don't worry, an other example is coming.

And now, on to building our new number. We'll build it bit by bit: first we're going to look at the number associated to 1, and look at the 1st number of his decimal writing. If it's a 1, the number we're building will get a 2, and if it's not a 1, we'll write a 1. Then we'll do that for 2, but by looking the 2nd number of the decimal part, and so on... Like this:

$$\begin{align}
&1 \rightarrow 0,\; \textbf{7}\; 2\; 3\dots \\
&2 \rightarrow 0,\; 3\;\textbf{2}\;1\;5\;6\;2 \dots \\
&3 \rightarrow 0,\;5\;4\;\textbf{1}\;5\;1\;6\;5 \dots \\
&4 \rightarrow 0,\;9\;8\;4\;\textbf{6}\;5\;1\;8 \dots \\
&5 \rightarrow 0,\;8\;9\;0\;0\;\textbf{1}\;0\;0 \dots \\
&\dots
\end{align}$$

In this example, the number we're building would be 0,11212... And we can see the diagonal too (which explains the name). Each time a number in bold is different than 1 we put a 1 in the decimal writing, and when it's 1, we put a 2. Still following ? Good ! You've made it through the hard part !

Because now the whole argument has been laid out, and if you think about it, REALLY think about it, you'll realise that absolutely no integer can reach the number we've built. I'll try and make it even clearer:

Let's assume a certain integer, let's call him n, reached our mystery number, let's call him x. We would then have:

$ n \rightarrow x = 0,\dots \underbrace{1}_\text{n-th position}\dots$

In which case our mystery number should have, by construction, a 2 in this place. So this can't be true.

OR we would have:

$ n \rightarrow x = 0,\dots \underbrace{not \; one}_\text{n-th position}\dots$

In which case our mystery number should have, by construction, a 1 in this place. So this can't be true either.

It instantly follows that our mystery number is indeed not reached by an integer, so the function isn't a one-to-one correspondence, and we've actually found a set with a bigger infinity ! Yay us !

And yes, it does mean that there are more numbers between 0 and 1 than there are integers.

This is actually a pretty elaborate proof, so again, don't panic if you don't get it on first read, and maybe try to build a few examples, try to replace n by a small number and test it out, and you should be able to see why it works.

I remember I promised to prove that there actually was an infinity of infinities, but this post is already quite long, so it'll have to wait for next time. But if you're definitely lost after this post, don't worry, none of this will be useful for the next and final one.

Some math-y weirdness, part 1.

So yeah, I love maths. It's actually one of the reasons I started this whole thing: because I wanted to talk about maths. I've actually got a post in the works explaining my love for maths, but I'm starting to realise it's a bit too much for one post. I thought I might try to work my way through there by making a series of posts, each showing a different thing about maths, walking my way up in complexity (but trying to remain as pedagogic as possible) and to give as wide a picture of the reality of what maths are as possible.

One thing to realise is that maths works through logic, by which I mean that it's the science of inferring from the properties of the stuff you're given. So obviously these posts will be a bit dry, and filled with definitions, because if you don't know WHAT you're talking about, how can you deduce anything about it ?

So, here we go. I thought I'd begin with the crudest things: sets. This might get technical at times, there will be strange words with even stranger definitions, just breathe, take your time to read, and don't hesitate to ask for any clarification.

A set is just a thing filled with stuff, and nothing more really. You don't know how those stuff interact (by which I mean you don't have anything like an addition, you have NOTHING, just your stuff). 

For instance, you can have numbers, like 1, 2, and 3, and if you take them collectively, you get the set containing the objects "1, 2, 3". What we will usually note {1,2,3} : the brackets denote a set. You forget any properties those elements might have. I used numbers, but we can totally imagine a set containing letters, like {a,b,c,d}. The objects inside do not really matter for the purpose of what a set is.

It follows that if you have two sets you want to compare, there aren't a lot of things you can do: you can see if one contains more objects than the others. It's what we call the cardinality, the size of a set.

If I give you these two sets for instance: {1,2,3} and {1,2}, you can easily tell that the first one have more elements than the second one... But what if they contained an infinity of elements ? How would you know if one is bigger ?

Or, more accurately, what does "bigger" even MEAN when we're talking infinity ?

The answer comes with a cool-looking word that will make you look smart if you manage to use it correctly: isomorph, "iso" comes from greek, and means "same", while "morph" also comes from greek, and means shape, or form. An isomorphism is a function something that tells us that two things are isomorph, which means they're basically the same, or at least indistinguishable when considering their properties.

So, for two sets, being "the same thing", would mean having the same properties. The only property a set have is its cardinality, so for two sets to be considered equivalent, they need only to have the same cardinality. 

To compare the cardinality of two things, we actually have a pretty nice way: we create a function between these two things, and we try to give it certain properties.

A function at its core is a pretty simple thing: it takes something from set X, and associate it something else from set Y. You can see it as an arrow, pointing out from each element of X and arriving on elements on Y.

The first property is that we want to try and make it injective, this means that two distinct elements from set X are associated to two distinct elements of set Y.

The second property is that we want it to be surjective, it means that EVERY elements of set Y is reached by an element of set X.

If a function qualify for these two properties, it will be called bijective. Which basically means that every point of Y is reached, and that no two points of X are connected to the same point in Y. Or said differentely, that we have a one-to-one correspondance.

And because a drawing is worth a hundred words, here's a cool image I found on wikipedia:

The first one is surjective because every element of set Y is reached, but not injective because the first two elements of set X reach the element of Y.

The second one is injective (every element of X is connected to a different element of Y), but not surjective, because some elements of Y aren't reached.

The last one is indeed bijective: each element of Y is reached, and no two elements of X are associated to the same thing.

Already we can see that when it comes to finite set, having the same cardinality is indeed the same as being able to link each element of X to an element of Y in a manner that no two elements are linked to the same thing.

So for sets, being isomorph actually mean having a bijection between the two sets.

Now let's just expand that to our infinite sets and see how that works... And we'll (FINALLY) get some funny results !

Let X be the set of all positive integers.
Let Y be the set of all even positive integers.

Take your bets now, will one be bigger ? If so, which ? Will they be the same size ? The suspense is killer.

Well, to see that let's try and make a function that goes from X to Y, and be subjective.

The answer is actually pretty easy: the function f will be the function that, for each element of X, associate two times this element... So :
0 will give 0
1 will give 2
2 will give 4
3 will give 6
and so on...

Our function is indeed injective: if you take two integers and multiply each by two, the only way you get the same result is if the two integers were equals to begin with.
It is also surjective: if you take an element y from the set Y, you can find an element x in X such as f(x) = y. Namely, x = y/2.
So it is injective and surjective, thus bijective, these two sets are actually of the same size. Which means there are as many *even* integers than there are positive integers.



But that doesn't really answer my original question: can there be an infinity "bigger" than the other one ? Right now we've managed to split an infinity in two, and still have the same infinity... And yet, the answer is yes, it's not that easy to prove though. But what we're actually able to prove is that there exists an infinity of infinities. Try and wrap your brain around that. If someone's interested, I could try making a small post about it, but that might get really technical.

Basically, the set of all integers is the smallest infinity there is, it's what we call countable. So if you have an infinite set containing only integers, you already know its cardinality: it will be a countable set, and will have the same cardinality as the set of all integers. Strange, isn't ? You have an infinity of integers, you take an infinity away (in our example, all odds numbers), and yet you can be left with the same infinity you started with. How is that not wonderful ?

Still, an example of set of a "bigger infinity" would simply be what we call the set of real numbers, which is basically any number you can think of, and where you'll find strange numbers such as pi.


And if it makes you feel better, one of the biggest name in this kind of thing was Georg Cantor, and he died crazy, so don't feel bad if you don't get it all on first read. Some of these concepts aren't necessarily easy to grasp.

My point with this post was to show that maths aren't about numbers, we've barely used them here, and really about a vision of the mind. You begin by visualising a simple thing (a thing containing stuff), and then you just kick it up a notch by giving it a name, properties, a definition, and working out from there: how can you compare two items, what are their properties, and so on... 

I am very familiar with each of these concepts because, well, that's kind of what I do, but it's totally normal to feel overwhelmed the first time, and to mix everything up. Just take it slow, one step at the time, and I hope you'll be all right !

Anyway, this was my first attempt at talking things maths, so tell me how that worked out for you ! Was it too technical ? Too superficial ? Too explain-y ?

So... Yeah.

Apparently, the thing I'm having the hardest time coming up with is the opening. Let's just assume I've done that and jump right into the fray.

So why this blog ? Well, simply put, there often are news events, cultural stuff, or various subjects on which I'd like to expand, and often can't, simply because I don't have the tools for it. Making a point on twitter is tantamount to baking cookies one at a time, and that really isn't the point of Facebook. So I needed a place to express myself, make the points I want to make, and I guess this will be it.

I'm realising as I'm typing this the hardness of the task though: while a discussion is an iterative process, where you bounce off each other and amend or clarify your statements as you go, a blog post would need to be as extensive as possible on first try. Even this very post, where I'm honestly not saying much, took more time and iterations than I care to admit.

And I haven't even started on the design yet. Can't I just put Clooney's bat-nipples on repeat in the background and call it a day ?