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 $$S = \set{X : X \in X \lthen \text{Santa exists}}.$$ Then $$S \in S \liff (S \in S \lthen \text{Santa exists}).\tag{$*$}$$ The forward implication of $(*)$ gives that $$S \in S \lthen \text{Santa exists}.$$ 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.1 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 $(*)$. The forward implication actually is $$S \in S \lthen (S \in S \lthen \text{Santa exists})$$ 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!!!

Notes

  1. As Andreas Blass pointed out in the comments, one can derive Russell’s Paradox in intuitionistic logic. (By the same argument, replacing Santa exists by $\bot$.) The real strength of Curry’s Paradox is that it does not even require negation!
 

5 thoughts on “Santa Exists!

  1. 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.

    1. 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$).

  2. 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$

    1. 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…

Leave a Reply

Your email address will not be published. Required fields are marked *