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 Yudkowsky1993 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.
Continue Reading »
Posted in computer science, game theory, logic and set theory | Tagged prisoner's dilemma, self-reference | 7 Comments »
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.
Continue Reading »
Posted in category theory, Galois theory, group theory | Tagged abstract nonsense, adjoint functors, duality, filtered colimits, Lawvere theories, profinite groups | 6 Comments »
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.
Continue Reading »
Posted in category theory, differential geometry, functional analysis, topology, universal algebra | Tagged abstract nonsense, adjoint functors, duality, Lawvere theories, pointless topology, reconstruction theorems | 10 Comments »
Occasionally I see mathematical questions that seem “grammatically incorrect” in some sense.
Example. “Is open or closed?”
Example. “Is a group?”
Example. “What’s the Fourier series of ?”
Here are some sillier examples.
Example. “Is a rectangle prime?”
Example. “Is ?”
Example. “What’s the Fourier series of the empty set?”
What all of these examples have in common is that they are type errors: they are attempts to apply some mathematical process to a kind of mathematical object it was never intended to take as input. If you tried to write a program in some highly mathematical programming language to answer these questions, it (hopefully!) wouldn’t compile.
Mathematical objects are usually not explicitly thought of as having types in the same way that objects in a programming language with a type system has types. Ordinary mathematics is supposed to be formalizable within Zermelo-Fraenkel (ZF) set theory, possibly with the axiom of choice, and in ZF every mathematical object is constructed as a set. In that sense they all have the same type. (In particular, the question “is ?” is perfectly meaningful in ZF! This is one reason not to like ZF as a foundation of mathematics.) However, I think that in practice mathematical objects are implicitly thought of as having types, and that this is a mental habit mathematicians pick up but don’t often talk about.
Instead of thinking in terms of set theory, thinking of mathematical objects as having types allows us to import various useful concepts into mathematics, such as the notions of type safety, typecasting, subtyping, and overloading, that help us make more precise what we mean by a mathematical sentence being “grammatically incorrect.” The rest of this post will be a leisurely discussion of these and other type-based concepts as applied to mathematics in general. There are various categorical ideas here, but for the sake of accessibility we will restrict them to parenthetical remarks.
Continue Reading »
Posted in category theory, combinatorial game theory, remarks, type theory | Tagged philosophy of mathematics, self-reference, universal properties | 22 Comments »
What does it mean to define a mathematical object?
Roughly speaking, there are two strategies you could use. One is to construct that object from other objects. For example, can be constructed from using Cauchy sequences or Dedekind cuts.
Another is to give a list of properties that uniquely specify the object. For example, can be defined as the unique Dedekind-complete totally ordered field.
Let’s call these strategies construction and specification. Construction has the advantage of concreteness, and it also proves that the object exists. However, it has the disadvantage that constructions are not unique in general and you might not be working with the most useful construction at a given time; to prove things about an interesting mathematical object you might have to switch between various constructions (while also proving that they all construct the same object).
Relying excessively on construction also has a curious disadvantage when talking to students about the object in question: namely, they might ask you how to show that object satisfies property , and you might respond “well, it’s obvious if you use construction ,” and they might respond “but I was taught that is [construction ]!” The possibility of multiple different constructions of the same mathematical object makes construction somewhat unsatisfying in terms of describing what you even mean when you say “object .”
This is the appeal of specification. Although specification is more abstract and harder to grasp at first, it has the advantage you don’t have to use any particular construction of an object to prove things about it: instead, you should in principle be able to prove everything from the properties alone, since those uniquely specify the object. This often leads to cleaner proofs. Specifications also usually give a better motivation for looking at an object: it’s easier to make sense of the claim that we want a mathematical object with various properties than to make sense of the claim that we want a mathematical object which is constructed in some arbitrary-looking (to the uninitiated) fashion.
Below we’ll go through a few examples of mathematical objects and some constructions and specifications of them.
Continue Reading »
Posted in remarks | Tagged philosophy of mathematics, universal properties | 7 Comments »