The goal of this post is to compute the cohomology of the -torus in as many ways as I can think of. Below, if no coefficient ring is specified then the coefficient ring is by default. At the end we will interpret this computation in terms of cohomology operations.

**Newcomb’s paradox** is the name usually given to the following problem. You are playing a game against another player, often called Omega, who claims to be omniscient; in particular, Omega claims to be able to predict how you will play in the game. Assume that Omega has convinced you in some way that it is, if not omniscient, at least remarkably accurate: for example, perhaps it has accurately predicted your behavior many times in the past.

Omega places before you two opaque boxes. Box A, it informs you, contains $1,000. Box B, it informs you, contains either $1,000,000 or nothing. You must decide whether to take only Box B or to take both Box A and Box B, with the following caveat: Omega filled Box B with $1,000,000 if and only if it predicted that you would take only Box B.

What do you do?

(If you haven’t heard this problem before, please take a minute to decide on an option before continuing.)

Posted in Uncategorized | 40 Comments »

Previously we saw that Cantor’s theorem, the halting problem, and Russell’s paradox all employ the same diagonalization argument, which takes the following form. Let be a set and let

be a function. Then we can write down a function such that . If we **curry** to obtain a function

it now follows that there cannot exist such that , since .

Currying is a fundamental notion. In mathematics, it is constantly implicitly used to talk about function spaces. In computer science, it is how some programming languages like Haskell describe functions which take multiple arguments: such a function is modeled as taking one argument and returning a function which takes further arguments. In type theory, it reproduces function types. In logic, it reproduces material implication.

Today we will discuss the appropriate categorical setting for understanding currying, namely that of cartesian closed categories. As an application of the formalism, we will prove the Lawvere fixed point theorem, which generalizes the argument behind Cantor’s theorem to cartesian closed categories.

Posted in math.CT, math.LO | Tagged abstract nonsense, adjoint functors, self-reference | 1 Comment »

Often in mathematics we define constructions outputting objects which *a priori* have a certain amount of structure but which end up having more structure than is immediately obvious. For example:

- Given a Lie group , its tangent space at the identity is
*a priori*a vector space, but it ends up having the structure of a Lie algebra. - Given a space , its cohomology is
*a priori*a graded abelian group, but it ends up having the structure of a graded ring. - Given a space , its cohomology over is
*a priori*a graded abelian group (or a graded ring, once you make the above discovery), but it ends up having the structure of a module over the mod- Steenrod algebra.

The following question suggests itself: given a construction which we believe to output objects having a certain amount of structure, can we show that in some sense there is no extra structure to be found? For example, can we rule out the possibility that the tangent space to the identity of a Lie group has some mysterious natural trilinear operation that cannot be built out of the Lie bracket?

In this post we will answer this question for the homotopy groups of a space: that is, we will show that, in a suitable sense, each individual homotopy group is “only a group” and does not carry any additional structure. (This is not true about the collection of homotopy groups considered together: there are additional operations here like the Whitehead product.)

Posted in math.AT, math.CT | Tagged 2-categories, abstract nonsense, Lawvere theories | 12 Comments »

I’ve added a new page of reading recommendations, mostly for undergraduates, to the top. The emphasis is intended to be on well-written and accessible books. Comments and suggestions welcome.

Posted in Uncategorized | Leave a Comment »

The goal of this post is to collect a list of applications of the following theorem, which is perhaps the simplest example of a fixed point theorem.

**Theorem:** Let be a finite -group acting on a finite set . Let denote the subset of consisting of those elements fixed by . Then ; in particular, if then has a fixed point.

Although this theorem is an elementary exercise, it has a surprising number of fundamental corollaries.

Posted in math.CO, math.GR, math.NT | Tagged finite fields, fixed point theorems, group actions, walks on graphs | 12 Comments »

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_{1993} 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.

Posted in math.LO | Tagged self-reference | 7 Comments »