Cantor’s theorem, the prisoner’s dilemma, and the halting problem

Cantor’s theorem is somewhat infamous as a mathematical result that many non-mathematicians have a hard time believing. Trying to disprove Cantor’s theorem is a popular hobby among students and cranks; even Eliezer Yudkowsky₁₉₉₃ fell into this trap once. I think part of the reason is that the standard proof is not very transparent, and consequently is hard to absorb on a gut level.

The goal of this post is to present a rephrasing of the statement and proof of Cantor’s theorem so that it is no longer about sets, but about a particular kind of game related to the prisoner’s dilemma. Rather than showing that there are no surjections , we will show that a particular kind of player in this game can’t exist. This rephrasing may make the proof more transparent and easier to absorb, although it will take some background material about the prisoner’s dilemma to motivate. As a bonus, we will almost by accident run into a proof of the undecidability of the halting problem.

Read Full Post »

Operations, pro-objects, and Grothendieck’s Galois theory

Previously we looked at several examples of -ary operations on concrete categories . In every example except two, was a representable functor and had finite coproducts, which made determining the -ary operations straightforward using the Yoneda lemma. The two examples where was not representable were commutative Banach algebras and commutative C*-algebras, and it is possible to construct many others. Without representability we can’t apply the Yoneda lemma, so it’s unclear how to determine the operations in these cases.

However, for both commutative Banach algebras and commutative C*-algebras, and in many other cases, there is a sense in which a sequence of objects approximates what the representing object of “ought” to be, except that it does not quite exist in the category itself. These objects will turn out to define a pro-object in , and when is pro-representable in the sense that it’s described by a pro-object, we’ll attempt to describe -ary operations in terms of the pro-representing object.

The machinery developed here is relevant to understanding Grothendieck’s version of Galois theory, which among other things leads to the notion of étale fundamental group; we will briefly discuss this.

Read Full Post »

A puzzle about operations

Previously we described -ary operations on (the underlying sets of the objects of) a concrete category , which we defined as the natural transformations .

Puzzle: What are the -ary operations on finite groups?

Note that is not representable here. The next post will answer this question, but for those who don’t already know the answer it should make a nice puzzle.

Read Full Post »

Operations and Lawvere theories

Groups are in particular sets equipped with two operations: a binary operation (the group operation) and a unary operation (inverse) . Using these two operations, we can build up many other operations, such as the ternary operation , and the axioms governing groups become rules for deciding when two expressions describe the same operation (see, for example, this previous post).

When we think of groups as objects of the category , where do these operations go? They’re certainly not morphisms in the corresponding categories: instead, the morphisms are supposed to preserve these operations. But can we recover the operations themselves?

It turns out that the answer is yes. The rest of this post will describe a general categorical definition of -ary operation and meander through some interesting examples. After discussing the general notion of a Lawvere theory, we will then prove a reconstruction theorem and then make a few additional comments.

Read Full Post »