Does Santa Exist?

This post is a favourite of mine, so I’ll try to keep posting it every year it when Christmas is getting closer.

Just a few months before Christmas! But be prepared when your children start asking you whether Santa really exists or not. It’s not as easy to convince them as it once were. The solution to convincing today’s enlightened children is of course to be very rigorous. We need to prove to them that Santa really exists.
So, let’s be pretty formal, and assume that S is the sentence “If S is true, then Santa exists”. That’s just a definition; nothing unusual going on. Seems that if we prove that S is true, then we’ll be done. But we’ll see. Now, the actual logical proof starts.

Suppose S is true. This is just an assumption.
By the definition of S, we can just replace S by its definition, and we get
“If S is true, then Santa exists” is true.

Well, not much gained yet. Probably we’re just warming up. But we can in fact use the assumption, “S is true” once more, together with that. Then we get “Santa exists”. Not bad! But this is of course only because we assumed that S is true. So we’re not there yet. Let’s summarize what we got from the assumption:
“If S is true, then Santa exists”. OK, well, this is the same as what S itself says. Finally something; we’ve proved S itself to be true!

But wait, if S is true, and “If S is true, then Santa exists” is also true, then obviously Santa exists. Done!

So, just sit down together, the whole family, a few days before Christmas, and carefully go through this proof, and you have removed one uncertainty from the celebrations. Also you need to know that there are also grownups who haven’t understood this fact yet.

This is my contribution for the people out there who still want to celebrate that old-fashioned Christmas!
(The proof freely from Boolos and Jeffrey, “Computability and Logic”.)

Advertisement

Complexity of Songs

Scientists have analyzed the complexity of the songs of the humpback whale. It’s quite advanced, they found! I’m sure you already know of the corresponding analysis of human songs, as demonstrated in Donald Knuth’s seminal paper.

Christmas

Since it’s almost Christmas, don’t forget to prove to your children that Santa really exists!

Santa and Contradictions

Perhaps you just happened to notice that my previous "proof" that Santa exists could be used for proving other things, too. For example, that Santa doesn’t exist. Or your children have already proved that they don’t need to go to bed.

OK, so what’s the catch? It seems possible to prove anything using this method, even contradictions. Is Mathematics inconsistent, after all? Well, no. It’s just that we’re not used to definitions causing contradictions. This is something that mathematicians realized at the beginning of the 20th century, when they investigated the foundations of mathematics.

For example, Bertrand Russell found a "paradox", when he postulated a set X that contained all sets that didn’t contain themselves. Which leads to a contradiction: Suppose X contains itself. Then X can’t contain itself, since it’s a member of X. Then suppose X doesn’t contain itself. Then X contains itself, by definition! So both cases give us contradictions. The conclusion Russell didn’t draw from this (I think) is "So X isn’t a set". Just to be extreme, suppose that S is a set that does contain 0 and does not contain 0. Anyone surprised that we get a contradiction from that? I guess not.

So, let’s check where S in the Santa example leads us. S is defined as "If S is true, then Santa exists". If S is to make sense, it must have a well-defined truth value; either true or false. We’ll check: can S be true? OK, then it seems to be the case when Santa exists, because if S is true, certainly Santa exists. It’s a logical possibility. But if S is false? Then the left-hand-side of the logical implication described by S will be false, and the implication itself will be true. Which means that S is true. But S is false! So the definition of S implies that S has to be true, and that Santa exists!

But if we view definitions as equations, things make sense. The definition of S is really an equation, which only has the solution "S is true". Other definitions have no solutions (like the set of all sets not containing themselves), and other might have several.

Christmas is Coming

Just a few months before Christmas! But be prepared when your children start asking you whether Santa really exists or not. It’s not as easy to convince them as it once was. The solution to convincing today’s enlightened children is of course to be very rigorous. We need to prove to them that Santa really exists.

So, let’s be pretty formal, and assume that S is the sentence "If S is true, then Santa exists". That’s just a definition; nothing unusual going on. Seems that if we prove that S is true, then we’ll be done. But we’ll see. Now, the actual logical proof starts.

Suppose S is true. This is just an assumption.
By the definition of S, we can just replace S by its definition, and we get
"If S is true, then Santa exists" is true. Well, not much gained yet. Probably we’re just warming up. But we can in fact use the assumption, "S is true" once more, together with that. Then we get "Santa exists". Not bad! But this is of course only because we assumed that S is true. So we’re not there yet. Let’s summarize what we got from the assumption:
"If S is true, then Santa exists". OK, well, this is the same as what S itself says. Finally something; we’ve proved S itself to be true!
But wait, if S is true, and "If S is true, then Santa exists" is also true, then obviously Santa exists. Done!

So, just sit down together, the whole family, a few days before Christmas, and carefully go through this proof, and you have removed one uncertainty from the celebrations. Also you need to know that there are also grownups who haven’t understood this fact yet.

This is my contribution for the people out there who still want to celebrate that old-fashioned Christmas!

(The proof freely from Boolos and Jeffrey, "Computability and Logic".)