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 is a set and is a function without fixed points then for all and , then there exists a that is not representable as for some . This is proven by setting , which meant that if was representable then there would exist such that thus contradicting the assumption that doesn’t have a fixed point.
How is this related to the original diagonalization argument? Well if we let and we let then we basically recover the basic argument about cardinality of the real numbers. We can interpret as the tabularization of real numbers into columns and rows and then 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 , , , and .
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.