The category of Conway games

Several years ago I typed up a rough English translation of André Joyal’s hard-to-find 1977 paper Remarques sur la théorie des jeux à deux personnes, describing the category of Conway games.

My version was on the web server of the University of Manchester mathematics department for a while: I’ve just noticed that it’s not there any more, which is understandable. I’ll put a copy here, in case it’s useful to somebody.

 

Bad news for naïve sets

I’ve been fascinated by dialetheism ever since I first heard about it in 2005, from RM Sainsbury’s wonderful book Paradoxes. The pleasure I derive from the notion that contradictions can be true is, I admit, the same as the dizziness obtainable from the best sort of science fiction; but I don’t think that constitutes an argument against the idea.

If you’re going to countenance true contradictions, but you are not yet ready to embrace the view of truth espoused by Malaclypse the Younger in Principia Discordia, then you need a system of logic in which a single contradiction does not necessarily entail everything whatsoever. Such systems are studied under the banner of Paraconsistent Logic.

One of the early hopes of this line of enquiry was that it would be possible to rehabilitate naïve set theory by embedding it into a paraconsistent setting. For example, let be the Russell set

From we can conclude that , and vice versa, but in a paraconsistent setting that need not be a problem. All we’ve done is to locate a true contradiction, an occasion for excitement rather than despair!

I’m obviously not a specialist in the area, but from what I’ve read as a curious outsider I have the impression that the wheels have rather come off this initially-plausible endeavour. Not all the paradoxes of naïve set theory are so comfortably dispatched; in particular, paraconsistency is no defence against Curry’s paradox. Some have proposed to modify the logic of implication to forbid that reasoning, though doesn’t that smack a little of desperation?

Anyway, the always-interesting Greg Restall has just lobbed rather a fun grenade into the ring. He has concocted a version of the paradox that doesn’t even use implication, though it does require an “initial” proposition from which everything follows.

(Incidentally, I have no idea whether or why anything is gained by using the word “property” instead of “set”, and tweaking the notation to use pointy brackets and curly epsilons rather than the other way around.)

The funny thing from my point of view is that I’m more suspicious of logical “units” than of implication. (They cause no end of trouble in linear logic for little or no gain, which is what motivated the topic of my thesis.)

Because I happen to be suspicious of , I’m therefore mildly suspicious of arguments that depend on it — I take Restall’s point that would do just as well, though it increases the demands made on the ambient logic.

Anyway, I thought it would be interesting to see how one could modify the argument to remove the dependency on , without making other new demands on the ambient logic. (The lovely thing about Restall’s proof is that it depends hardly at all on the logic: as far as I can see it assumes only equality, contraction and .) My variation is here – it assumes a (primitive or derived) subset predicate that satisfies the obvious introduction and elimination rules, but of the logic demands nothing more than contraction.

This may well seem very naive to any philosopher who should happen across it. Perhaps there are already well-known objections to such an argument. In the context of this particular philosophical discourse it is presumably weaker than Greg Restall’s argument — it invites the objection that the subset predicate is disguised implication, for example — but personally it’s enough to convince me that tinkering with the logic is not going to rescue na\”ive set theory without unacceptable collateral damage. And that’s a shame, because it was a cool idea.

Because I happen to be suspicious of , I’m therefore mildly suspicious of arguments that depend on it — though I take Restall’s point that would do just as well, it increases the demands made on the ambient logic.

Anyway, I thought it would be interesting to see how one could modify the argument to remove the dependency on , without making other new demands on the ambient logic. (The lovely thing about Restall’s proof is that it depends hardly at all on the logic: as far as I can see it assumes only equality, contraction and .) My variation is here – it assumes a (primitive or definable) subset predicate that satisfies the obvious introduction and elimination rules, but of the logic demands nothing more than contraction.

This may seem naive to any philosopher who should happen across it. Perhaps there are already well-known objections to such an argument. In the context of this particular philosophical discourse it is presumably weaker than Greg Restall’s version — it invites the objection that the subset predicate is disguised implication, for example — but personally it’s enough to convince me that tinkering with the logic is not going to rescue naïve set theory without unacceptable collateral damage. And that’s a shame, because it was a cool idea.

Reboot

I’ve been thinking about restarting this blog for more than a year, but my plans to do so were always so ambitious that I never completed them: the charming essay Procrastination and Perfectionism is perhaps relevant here. I read somewhere that it is a cardinal violation of blog etiquette to apologise for – or even to make reference to, if I remember rightly – a gap in posting. I cannot now remember what the reason for that was supposed to be, but a two-year delay surely cannot pass unremarked?

For what it’s worth, I anticipate my frequency of posting to have a small mean and a large variance. The subject matter will be more varied than before, since I have a job that does not involve category theory, and if I tried to confine my postings to categories I would post about once every five years at present rates. At some point I did change the subtitle from “categorical maundering” to “miscellaneous maundering” in anticipation of this.

One piece of very old news that I never mentioned here: I did eventually finish writing up my thesis in September 2007. If anyone is interested, it’s available at Linear Logic without Units.

Games II

Last time, I explained how the category of finite simple games is equivalent to the initial lift-product category. Now I want to show how this fact can be used to find nice ways of representing strategies.

Games I

When I started doing research, I mostly worked on categories of games. I even went so far as to write a first-year report that suggested — even confidently claimed — that I would write a thesis on the subject. Well, I’m writing that thesis now, and games appear only in passing in a single paragraph. But recently, one or two people have expressed some interest in some of the ideas in that first-year report, so I’d like to flesh out one of idea that is only sketched very vaguely in what I wrote.

The starting point is the idea that a simple category of games is (equivalent to) the initial model of a certain simple theory.

Radical lax monoidal functors

In my previous entry, I deferred the problem of defining lax monoidal functors between radical monoidal categories. But yesterday evening on the train I realised that there is a cute way to think about lax monoidal functors, which makes it possible to simply calculate the answer.

Suppose we have monoidal categories C and D, and a functor F: C → D. To give a lax monoidal structure on F is to give a monoidal structure on the comma category C↓F, such that the projections C↓F → C and C↓F → D are strict monoidal.

I wasn’t going to explain that, because it’s fun to figure it out and rather dull to explain, but in the end I decided to put an explanation at the bottom of this post (appendix B).

Rethinking monoidal categories

As you can probably tell, I’m hugely excited about Joachim Kock’s paper. I apologize to those of you who read it a year ago, and think I’m a bit late to the party.

Most late-stage PhD students, I imagine, have written an imaginary textbook entitled Things I wish I’d known three years ago. My own contribution to this genre has a snappier title – it’s called Monoidal categories – and since yesterday it’s been frantically rewriting itself. (The advantage of imaginary books over real ones is that they can do that.)

Kock on units

This morning’s crop of arxiv updates included a new version of Joachim Kock’s Elementary remarks on units in monoidal categories. Somehow I hadn’t noticed the earlier version; it’s a beautiful result, and it implies the lemma of mine that I mentioned in Paré’s observation.

Paré’s observation

It’s a curious (though well known) phenomenon that an equivalence in a bicategory can always be converted into an adjoint equivalence by tweaking one of the 2-cells. There are two ways to prove it, that I know of. The elementary way is just to write down a (rather complicated) definition and laboriously prove that it has the desired properties. I always found this rather baffling, so I preferred the more abstract approach: in essence, it’s easy to show that equivalences in Cat have this property by using the Yoneda lemma, then one can use the bicategorical Yoneda lemma to transfer the result to an arbitrary bicategory. But recently I learnt something that makes the direct approach a lot easier for me to understand.

Fun with Rel

One of the great joys of category theory is the way you can so often watch familiar structures emerge unexpectedly from general constructions. It’s particularly amusing to apply the formal theory of monads to the 2-category Rel of sets and relations. (I mean the 2-category whose objects are sets, whose 1-cells are relations, and where there is a unique 2-cell from R to S just when R is a subset of S.) This is an easy example to study because all diagrams of 2-cells commute, since by definition there is at most one 2-cell between any pair of relations.