Paper Reading: A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points

So I wanted to include a brief review of a paper I saw the other day from the twitter account Philosophic Logic: A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points

In this paper the author gives a very acessible introduction to the underlying algebraic structure behind Cantor’s Diagonalization, Russell’s Paradox, the Halting Problem, and similar proofs that involve paradox. The basic approach is that they first recast Cantor’s classic argument into a more general form: if Y is a set and \alpha : Y \to Y is a function without fixed points then for all T and f : T \times T \to Y, then there exists a g : T \to Y that is not representable as g = f(-,t_0) for some t_0. This is proven by setting g(t) = \alpha(f(t,t)), which meant that if g was representable then there would exist t_0 such that g(t_0) = f(t_0,t_0) = \alpha(f(t_0,t_0)) thus contradicting the assumption that \alpha doesn’t have a fixed point.

How is this related to the original diagonalization argument? Well if we let Y, T = \mathbb{Z_{10}} and we let \alpha = \lambda x. x+1 then we basically recover the basic argument about cardinality of the real numbers. We can interpret f as the tabularization of real numbers into columns and rows and then g is the real number that doesn’t correspond to any row in the table, given by changing all the digits along the diagonal of the table.

The paper goes on the relate the same basic argument to a bunch of other problems, relating the witness of various paradoxes to a choice of T, Y, f, and \alpha.

The paper also relates the contrapostive of the generalized cantor theorem to a number of results, including the first Goedel incompleteness theorem and the recursion theorem.

Overall, I thought this was a cute paper and I’d never actually seen these results that are sortof intuitively all the same construction cast as the formally the same construction. Since the mathematics required are very simple I think I’m going to give this to my students in my theoretical computer science course to read.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s