Archive for August, 2013

Determinacy of Borel games II

August 31, 2013

By the end of the previous post, I had said what a Borel subset of \mathbb{N}^{\mathbb{N}} was, and what a determined subset was. Martin’s theorem is the statement that all Borel sets are determined.

I also commented that an intersection of two determined sets does not have to be determined, which suggests that in order to prove that all Borel sets are determined, we will need to find a clever inductive hypothesis. This hypothesis should be of the form, “All Borel sets of index less than \alpha have property P,” where having property P implies that you are determined, and it is also preserved when you take countable intersections and unions.

Since the property of being determined is quite a strange property, it seems rather unlikely that we will be able to find a much simpler property that does the job. So it is natural to look for a property that is itself related to games and determinacy. But what might such a property be?

Determinacy of Borel games I

August 23, 2013

I’m trying to understand the famous result of Donald Martin that Borel games are determined, and by that I mean not just understand the proof line by line, but also understand why the lines are as they are. I have found some nice presentations online, in particular these notes by Shehzad Ahmed and this Masters thesis by Ross Bryant, which have been very helpful, not just in presenting the proofs line by line but also, to some extent, in doing things like explaining certain definitions that would otherwise seem a little strange. (Ahmed’s notes are good for a quick overview and Bryant’s thesis is good if you want full details.) Nevertheless, I think one can go further in that direction and speculate about how Martin came up with his proof. I’m actually talking not about his original 1975 proof but about a simpler argument he discovered about ten years later in a paper that, thanks to the generosity of the AMS, I have not been able to look at. (I am on holiday in France, or I suppose I could have trudged over to my departmental library, but for some reason I find I can never bear to do that even if I’m in Cambridge.)

Understanding a proof in that kind of detailed way takes some effort, and usually everybody has to make that kind of effort for themselves. However, that ought not to be the case in the internet age: in this post I’m going to try to write an account of the proof in a way that makes it possible for others to understand it properly without making much effort. Whether I’ll succeed I don’t know. [Added later: I have now written three posts, and expect to finish in one more. I have got far enough to be confident that I will actually manage to write that fourth post. So at least I will end up with a reasonable understanding of the proof, even if I don’t manage to transmit it to anyone else.]

One thing I believe quite strongly is that it is better to be in a position where you can remember the ideas in a way that makes it easy to reconstruct the details than to be in a position where you have all the details in front of you but are less certain of the underlying ideas. So I may skimp on some of the details, but only if I am confident that they really have been reduced to easy exercises.