François G. Dorais

Topics
• Mathematical Philosophy
• Proof Theory
• Set Theory

Santa Exists!

Here is a theorem that I like to mention during the first week when I teach set theory.

Theorem. Santa exists!

Proof. Consider the set

Then $S \in S \liff (S \in S \lthen \text{Santa exists}).\tag{🎅}\label{hohoho}$ The forward implication of \eqref{hohoho} gives that

But then, the backward implication of $(*)$ gives that $S \in S.$

Knowing that $S \in S$ and $S \in S \lthen \text{Santa exists}$, we conclude that Santa does exist! QED

As you probably noticed, this is actually a disguised version of Russell’s Paradox, which is due to Haskell Curry. Should Santa fail to exist, $S$ would simply become the usual paradoxical set $R = \set{X : X \notin X}$ (but we all know that $S$ simply consists of all sets).

What I like about this variant of Russell’s Paradox is that it does not rely on the law of excluded middle.¹ The usual argument for Russell’s Paradox proceeds by reaching a contradiction from $R \in R$ and another contradiction from $R \notin R$. In order to reach a final contradiction, this argument assumes that $R \in R \lor R \notin R$ is true, so all of your intuitionist students will immediately be disappointed.

On the other hand, Curry’s Paradox works even in minimal logic! The only sketchy step is the deduction of $S \in S \lthen \text{Santa exists}$ from \eqref{hohoho}. The forward implication actually is

and the desired conclusion is reached by contraction (the fact that assuming $S \in S$ twice is not more powerful than assuming it once). Odds are that very few students will bother counting how many times the assumption $S \in S$ is used in this step.

This shows that self-reference is not a problem unique to classical logic. It applies equally well to intuitionistic and minimal logic. In fact, to avoid self-referential paradoxes through logic it seems necessary to reject the contraction rule (as in linear logic). This is rather extreme from the foundational perspective, so we’re probably better off resolving self-referential issues by other means.

My personal conclusion from this story is that logicians will never be out of work… so Santa does exist!!!

Originally posted on October 15, 2011, by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.

Comments

• Andreas Blass wrote on October 23, 2011, at 01:49

  I don’t think the Russell paradox needs the law of the excluded middle. Once you’ve derived (as you said) a contradiction from $R \in R$ and another contradiction from $R \notin R$, the first proves (even intuitionistically) that $R \notin R$ (thanks to the intuitionistic meaning of negation as implying a contradiction), and then the second gives you an outright contradiction.

  ---

• François G. Dorais replied to Andreas Blass on October 23, 2011, at 02:13

  Right! The same argument works replacing “Santa exists” by $\bot$…

  I was thinking of a different argument (which I think is how the paradox is usually described): Since $R \in R \lthen (R \notin R \land R \in R)$ and $R \notin R \lthen (R \notin R \land R \in R)$, from $R \in R \lor R \notin R$ we conclude $R \notin R \land R \in R$.

  I guess the real difference is that Curry’s version doesn’t require negation (or $\bot$).

  ---

• Buschi Sergio wrote on November 21, 2011, at 13:40

  This is simply (seem to me) a wrong proof (no a different version of Russel paradox).

  When you write: “The forward implication of (∗) gives that…” forget to mention $if\ S\in S$

  ---

• François G. Dorais replied to Buschi Sergio on November 21, 2011, at 13:56

  This is explained later on in the post. The forward implication is $S \in S \lthen (S \in S \lthen \text{Santa exists})$ which gives $S \in S \lthen \text{Santa exists}$ by contraction.

  Of course, this is an invalid proof in linear logic, which does not admit the contraction rule, but then I would have to be more precise about what implication means…

  ---