Monday, September 29, 2014

God and the Big Bang Theory

The title caught your attention? Good! It would seem at the beginning that this has nothing to do with set theory, but trust me and go on.

This time I am going to talk about the Big Bang Theory. Yes, not the awe-inducing cosmological model for the early development of the universe, but the sitcom (notice the uppercase T?). What can I say about this sitcom that has never been said before? Extremely popular, it lures the nerds with tons of citations about science, science fiction and fantasy, but at the same time it ridiculizes them, but anyway less than other series in the past. The humour is predictable and comforting. Anyway, everybody agrees that, like all the TV series, with time it became less interesting, so I stopped seeing it.

Until this week! When this discussion on Mathematics Stack Exchange made me curious again, and I have seen the episode 8x02 "The Junior Professor Solution", aired the 22 September 2014. So, first of all, kudos to Doug Spoonwood for having spotted this, and to Asaf Karagila for being the first to realize its significance.  I cannot link the video, of course, so I'll describe the scene. Sheldon, the genius of the series, has to prepare a lesson for Wolowitz, and he wanted it to be as hard as possible. Sheldon is showing whiteboards full of difficult formulas, saying

Oh, I'm working on my lesson plan for Wolowitz. He is going to be so lost. Look at this section over here.

Even I don't really understand it.

I DO! I DO! You suck, Sheldon! Ha! Let's see it closer:

This is the famous proof by Gödel of the existence of God (better known as Gödel's ontological proof). Woah. I will leave you a moment to contemplate the magnificence of this discovery.

No, no, no, what are you thinking? Militant atheists, don't think that Gödel was a crackpot (well, he was, but after that). Dawkins, you got it wrong (not for the first time)! And militant religious, don't go around saying that the existence of God is logical (gah). Why do you always have to fight? He didn't really proved the existence of God, in reality. The right way to see it is as part of the history of philosophical logic.

It was pretty common in the old days to try to prove the existence of God via logical arguments. Think Anselm of Canterbury, Descartes, guys like that. Gödel found logical mistakes in those arguments, and just rewrote them in the current logic language, i.e. modal logic, which distinguishes between necessary truths (something that must be true, no matter what) and contingent truths (something that is true, but just because, if it weren't true everybody would be chill). Nothing really new, then, and nothing real. It is just syntax, empty words, he was interested in the reasoning, not in its connections with reality.

Basically (I am simplifying here) Gödel said:

A1) a positive property can have only positive properties as consequences (optimist)
A2) a property is positive if and only if its negation is not positive
A3) being God is positive (this is slightly an understatement)
A4) if a property is positive, it is because it must be positive (nothing left to chance here)
A5) necessary existence is a positive property (again, quite optimist, if something must exists, then it is good)

If this can be, then there exists an object with all the positive properties, i.e., God. That's it. All the details are in the Wikipedia link, it's pretty formal, but it is not difficult. He could have written "fairy" or "vegetable-y" instead of "positive", and "unicorn" or "carrot" instead of "God", and he would have proved the existence of a unicorn or of a carrot.

But look again at Sheldon's whiteboard! See, there are A1, A2 etc also there. I did it on purpose, what is written in the whiteboard correspond exactly to what I wrote here. Almost. There is a horrible mistake.

This is what Sheldon wrote, translated from formalese to English:

A2) a property is positive if and only if its negation is positive

But Sheldon! What did you write?! How can this be? You really didn't understand the proof.

And what about Set Theory? This is where things got interesting. I told you that God exists if  there exist positive properties. Do they? Harvey Friedman has a manuscript on that, where he defines God and positive properties more carefully, and proves that they exist if... if...


if there exists a measurable cardinal! Step aside, Pope. We did your job. Talking about solving unsolvable problems with large cardinals!

Update: it turns out that Gödel hit a wall here. In 2013 someone managed to prove (with Artificial Intelligence, nonetheless!) that the hypothesis A1-A5 are actually contradictory taken all together, so Gödel proof it's just wrong. Alas, all this post for nothing.

You want to build a measurable y yourself? Go here. You like to see discussions about infinity between theologians and set theorists? Then this page is just for you.

Monday, September 22, 2014

Artemis Fowl and the Large Cardinals Paradox (part two)

This post continues from here.

Thanks for waiting. So, we were talking about this:

this sentence in particular:

He focused on the high end of his intellect, solving unprovable theorems with large cardinals and composing an ending for Schubert's unfinished Symphony N° 8.

and we were trying to understand what it means "solving unprovable theorems with large cardinals". In the previous post I introduced large cardinals (seriously, if you haven't read it, do it now, otherwise it's going to be hard). Now we go back in time, to the beginning of the 20th century, deep in the paradox.

Mathematics, like art, politics, physics, was in a horrible crisis. There was the legitimate doubt that all mathematics was in fact a house of cards. Everything could collapse any minute: people just realized that the math building had no foundation. You know when you are having a deep and meaningful conversation with your friend, but suddenly there is that awkward moment when you realize you were talking about the Isis, and he was talking about recliners (you've got to chill out, dude, it's ok to hate them but not that much)? Or when you are well into adulthood, and you realize that all the choices your life is based on where made when you were too much young and immature, and now you are completely disconnected to what once had meaning to you, and it is too late too change, you are trapped in a cage of sorrow build by yourself where you can just float through your meaningless life until OH MY GOD STOP IT THIS IS TOO DEPRESSING.

Yep, mathematics was in a middle age crisis.

It works like this:

What is a triangle? A polygon with three edges and three vertices.

What is a polygon? A plane figure that is bounded by a finite chain of straight line segments closing in a loop to form a closed chain or circuit.

What is a plane? A flat, two-dimensional surface.

What is a dimension of an object? The minimum number of coordinates needed to specify any point within it.

What is a point? Ehm... something with no dimensions? No, we defined dimension using points. Then... What?

You can understand how, in a subject like mathematics that strives to be as objective as possible, the lack of well-defined basic notions was problematic. Before that, they were satisfied with primitive notions, but with the current level of sophistication it was not enough. Hilbert tried to solve this with a collective effort: let's write down a list of things we know for sure are true, and such that all the results of mathematics can be proved from those. If something make all the people say "Duh", then it is a right starting point.

This is how we came up with ZFC: a list of nine trivial sentences (like: two sets are the same if they have the same elements. Duh), that form the basis of all ordinary mathematics. Of course there are fringes who don't like it: some people want to drop the C and have ZF, others want ZC or just Z, others prefer KFC, some guy prefers NBG, or KP. Oh, and what about New Foundations? It's a mess, but we can say that the majority of people consider ZFC=mathematics.

But then Gödel (25 years old) came and said: careful! Whatever sentences you choose, there will be always mathematical statements that are unprovable, outside the scope of logic! So paradoxical!

So this is how one can say that something is unprovable in ordinary mathematics: it just cannot be proved from those nine sentences.

And here come the large cardinals! What if we add to the nine sentences a tenth sentence, like, there exists an inaccessible cardinal. Then we can prove more stuff! Remember: large cardinals are unprovable in ordinary mathematics, so we are adding something genuinely new! But then... something that before was unprovable, now it's provable, using large cardinals! Yay!

Has it ever happened? It happens every day. The most famous (but controversial) case is Fermat's Last Theorem. When Andrew Wiles proved it, he became a superstar: he was mentioned in Star Trek: Deep Space Nine, in Stieg Larsson's The Girl Who Played with Fire, and a jeans company asked him to pose for an advertisement (he turned it down, unfortunately). Well, the proof uses Grothendieck Universe, and you cannot have a Grothendieck Universe without an inaccessible cardinal. So yes, Wiles used a large cardinal. It is controversial, because many mathematicians claim that it is not necessary to use it, that it is possible to change the proof and avoid it, so maybe Fermat's Last Theorem is provable. (This is granted to start a flame war).

But there are many other technical results that we know need large cardinals. Also, we have many large cardinals, not just inaccessible, and they are stronger and stronger, therefore lead to more and more mathematical results that are not provable in ordinary mathematics. They have also funny names (I am talking to you, ineffable cardinals), so I'll end with a (partial) list of them completely without context for your amusement, from the weakest to the strongest:

Zero pistol

Icarus sets

So, good job, Artemis! If the problem you're thinking of is unprovable, then using large cardinals is the most sensible thing you can do. Start with an inaccessible cardinal, and if it is not enough, go up up up, until you find something useful.

And now you can try this at home too! (*) Enjoy your time solving unprovable theorems with large cardinals!

(*) Keep out of reach of children. Keep away from food, drink and animal foodstuffs.
When using do not smoke. Avoid contact with eyes.  If swallowed, seek medical advice immediately and show this container or label.

You want to know what is the use of large cardinals? How about... proving God? Or just waisting a lot of time for an addicting game, that is important too.

Monday, September 8, 2014

Artemis Fowl and the large cardinals paradox (Part one)

Let's go back to young adults literature.

This time I am picking a sentence from the book Artemis Fowl: the Time Paradox.

It's the sixth book in the series Artemis Fowl, by the talented Eoin Colfer. I won't compare it with Harry Potter, like everybody does, first because he dislikes it (it is like comparing an apple with an orange, he said), second because it is much more unique: it is a mixture of sci-fi technology and typical fantasy lore, and the main character is not a whiny do-gooder but an unpleasant sociopathic teenager, extremely intelligent and sort-of-criminal. I feel him. The books are full of action, but they reward the brainy young reader.

So, at a certain point Artemis Fowl in this book is time-traveling (I hope it's not a spoiler, but come on, it is in the title!), and during his travel he's looking for ways to fill this time. How does a genius spend his time? Like this:

He focused on the high end of his intellect, solving unprovable theorems with large cardinals and composing an ending for Schubert's unfinished Symphony N° 8.

Yes! YES! Infinitytimesinfinity times yes! This is so exact it hurts. Oh boy. I am not talking about the decades-long row on whether the Unfinished Symphony is the 8th or the 7h, of course (for this, go to, but I am talking about large cardinals and unprovability! In fact, I think that in the whole world there are just, like, two thousands people able to come up with that sentence? Who tipped Eoin Colfer? I want to know!

Well, be prepared, now, after reading this you will be one of those!

Let me start with large cardinals. What are these?

Pictured: not what I am talking about

Cardinals are just math-speech for numbers and infinities. In practice, they are the measure of the largeness of a set: if a set is finite it will be a number (finite cardinals), if it is infinite it will be some infinity (infinite cardinal).

Wait, if this is the first time you read this blog, then maybe you are not aware of Cantor's Theorem. Read this, and be prepared to have your mind blown. Or just don't read it, and believe me: there are many infinities, some bigger, some smaller, and not just one. Booom.

But then what can be considered large for the people that are used to handle infinities like it's nothing? Here you can find some infinite sets that needs some serious brainpower to be visualized, and yet they are all extremely small. We have to pick an inaccessible cardinal, the smallest of the large cardinals, to just start to realize how large these guys are.

Again, not what I am talking about. Stop it.

Think: how many infinities there are under the first infinite cardinal? 0, that was a trick question. How many under the second infinite cardinal? 1. Well, under an inaccessible cardinal, there are as many as the cardinal itself. Woah, that's big. Really big. In a certain sense, it is an infinity so powerful that all the smaller ones are like finite (*). It's really a jump in another dimension.

It is so big, that it trascends mathematics. With that I mean that it is completely outside mathematics, it cannot be reached with proofs. One cannot prove that it exists. And here we are with unprovability, the other key word in Artemis Fowl's thought. Please remark: he says unsolvable, not unsolved. He is not trying to prove theorems no one else ever proved, he is trying to prove theorems it is impossible to prove. How come?

To understand this, we must do like Artemis Fowl and go back in time, precisely in the beginning of the 20th century! Prepare all the luggage, next Monday we start!


(*) I am a mathematician, so I cannot leave this sentence so vague. This is what I mean: if you have around you just a finite amount of finite objects, you cannot reach infinity. No way. You can add them, multiply them, stack them, exponentiate them, the result will always be finite. The same thing with an inaccessible cardinal: if you have less than an inaccessible cardinal objects around you, you cannot "reach" the inaccessible. Yep, this is why it's called inaccessible. Duh.

Aaaand, here is the second part