Determinacy of Borel games III

September 5, 2013

My aim in this post (if I have enough space) is to prove that every closed game can be lifted to an open (and therefore, by continuity, which is part of the definition of lifting, clopen) game. Since I am discussing a formal proof, I shall be a little more formal with my definitions than I have been so far. Much of what I write to begin with will be repeating things I have already said in the two previous posts.

Trees and paths

Recall the definition of a pruned tree. This is an infinite rooted tree T such that from every vertex there is at least one directed infinite path. (Less formally, if you are walking away from the root, you never get stuck.) Given such a tree T, we write [T] for the set of infinite directed paths in T. If we are working in \mathbb{N}^{\mathbb{N}}, then the tree T we will work with has finite sequences as its vertices, with each sequence (n_1,\dots,n_k) joined to its extensions (n_1,\dots,n_k,n). Then [T]=\mathbb{N}^{\mathbb{N}}.
Read the rest of this entry »

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?
Read the rest of this entry »

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.
Read the rest of this entry »

The selected-papers network

June 16, 2013

This post is to report briefly on a new and to my mind very exciting venture in academic publishing. It’s called the Selected Papers Network, and it has been designed and created by Christopher Lee. If you want to know what it is and what you can do to help it become a success, then you may wish to stop reading this post and turn straight away to a post by John Baez, who has been closely involved with the venture and understands it better than I do. But let me just briefly mention the main point that has struck me so far.

A problem with the current situation is that it is easy to come up with ideas for websites where people can review papers, complete with clever protocols for how the reviewing should take place, whether it is open, reward systems, etc. etc. It’s much less easy to persuade people to use the sites that are created as a result: what is going to persuade them to make the effort, when there’s only rather a small chance that the site will become in any sense “official”?

The Selected Papers Network potentially solves this problem in a very interesting way: it is not a website with a system for reviewing, evaluating, rewarding etc.. Rather, it is an environment that makes it easy to build your own systems.
Read the rest of this entry »

Elsevier journals: has anything changed?

May 27, 2013

Greg Martin, a number theorist at UBC (the University of British Columbia in Vancouver) doesn’t think so, so he has decided to resign from the editorial board of Elsevier’s Journal of Number Theory. His resignation letter makes interesting reading: I reproduce it here with his permission.

Dear colleagues,

I am writing to inform you of my resignation from the editorial board of the Journal of Number Theory, effective immediately. I will also be adding my name publicly to the list of people who refrain from volunteering for, or submitting manscripts to, Elsevier journals.
Read the rest of this entry »

Answers, results of polls, and a brief description of the program

April 14, 2013

I have now closed the polls in the second mathematical writing experiment. Here are the results. I have also published the comments on the first and second experiments, which shed further light on the results and on (some) people’s reasons for voting the way they did.

The results were complicated slightly by the fact that after a couple of days the post was linked to from the front page of Hacker News, and suddenly the number of people who voted more than tripled in a few hours. Furthermore, there was a bit of discussion about the polls, so it is not clear that the votes were completely independent. Also, the profile of an average Hacker News reader is probably somewhat different from the profile of an average reader of this blog.

Fortunately, I had recorded the votes shortly before this happened, so below we (“we” means Mohan Ganesalingam and I) present both sets of results. As it happens, the proportions didn’t change too much. We begin with some bar charts. U stands for “undergraduate”, G for “graduate”, C for “computer” and D for “don’t know”. The portion coloured in blue represents people who claimed to be sure that they were correct, and the portion coloured in red represents those who were unsure.

At the end of the post we give the exact numbers.

A brief remark before we present the results is that none of the three “contestants” was explicitly trying to write proofs that would appear as human as possible. The two humans were asked to provide proofs and not told why. And the program was designed to produce passable write-ups, but not to fool people into thinking that those write-ups were written by a human. (There are some easy improvements that could have been made if we had intended to do that, but we did not originally envisage carrying out this second experiment.)

The general picture can be summarized as follows.

1. The computer was typically identified by around 50% of all those who voted.

2. Typically around half of those were confident that they were correct, and half not so confident.

3. A non-negligible percentage of respondents claimed to be sure that a write-up that was not by the computer was by the computer.

The results in bar-chart form

whichisthecomputer

Mohan Ganesalingam

There is quite a lot to say about these results, and also about the program. Most of the rest of this post is written jointly with my collaborator Mohan Ganesalingam (as indeed were the posts with the two experiments — we chose the wording very carefully), but first let me say a little about who Mohan is.
Read the rest of this entry »

A second experiment concerning mathematical writing.

April 2, 2013

The time has come to reveal what the experiment in the previous post was about. As with many experiments (the most famous probably being that of Stanley Milgram about obedience to authority), its real purpose was not its ostensive purpose.

Over the last three years, I have been collaborating with Mohan Ganesalingam, a computer scientist, linguist and mathematician (and amazingly good at all three) on a project to write programs that can solve mathematical problems. We have recently produced our first program. It is rather rudimentary: the only problems it can solve are ones that mathematicians would describe as very routine and not requiring any ideas, and even within that class of problems there are considerable restrictions on what it can do; we plan to write more sophisticated programs in the future. However, each of the problems in the previous post belongs to the class of problems that it can solve, and for each problem one write-up was by an undergraduate mathematician, one by a mathematics PhD student and one by our program. (To be clear, the program was given the problems and produced the proofs and the write-ups with no further help. I will have more to say about how it works in future posts.) We wanted to see whether anybody would suspect that not all the write-ups were human-generated. Nobody gave the slightest hint that they did.

Of course, there is a world of difference between not noticing a difference that you have not been told to look out for, and being unable to detect that difference at all. Our aim was merely to be able to back up a claim that our program produces passable human-style output, so we did not want to subject that output to full Turing-test-style scrutiny, but you may, if you were kind enough to participate in the experiment, feel slightly cheated. Indeed, in a certain sense you were cheated — that was the whole point. It seems only fair to give you the chance to judge the write-ups again now that you know how they were produced. For each problem I have created a poll, and each poll has seven possible answers. These are:

The computer-generated output is definitely (a).
I think the computer-generated output is (a) but am not certain.
The computer-generated output is definitely (b).
I think the computer-generated output is (b) but am not certain.
The computer-generated output is definitely (c).
I think the computer-generated output is (c) but am not certain.
I have no idea which write-up was computer generated.

I would also be interested in comments about how you came to your judgments. All comments on both experiments and all votes in the polls will be kept private until I decide that it is time to finish the second experiment. A small remark is that I transcribed by hand all the write-ups into a form suitable for WordPress, so the existence of a typo in a write-up is not a trivial proof that it was by a human.

If you did not participate in the first experiment but nevertheless want to try this one, that’s fine. [Update: I have now closed the polls. Very soon Mohan and I will post the results and a discussion of them. Further update: The results now appear below. They appear displayed in possibly a more convenient way in this post, which also contains a discussion of how the program works.]
Read the rest of this entry »

Another test

April 2, 2013

This time I want to test whether I can have polls where the results are not visible until the poll closes. So if you have a few seconds to vote, that would be very helpful. If the facility works, then my next post will include some secret ballots.

An experiment concerning mathematical writing

March 25, 2013

Update: comments on this post are now closed, since my latest post would compromise any further contributions to the experiment.

Most of this post consists of write-ups of proofs of five simple propositions about metric spaces. There are three write-ups per proof, and I would be very grateful for any comments that you might have. If you would like to participate in the experiment, then please state your level of mathematical experience (the main thing I need to know is whether you yourself have studied the basic theory of metric spaces) and then make any comments/observations you wish on the write-ups. The more you say, the more useful it will be (within reason). I am particularly interested in comparisons and preferences. For each proof, the order of the three write-ups has been chosen randomly and independently.

It would also be useful if you could rate each of the 15 write-ups for clarity and style. So that everyone rates in the same way, I suggest the following rating systems.

Clarity.

-2 very hard to understand
-1 hard to understand
0 neither particularly hard nor particularly easy
1 easy to understand
2 very easy to understand

Style.

-2 very badly written
-1 badly written
0 neither badly written nor well written
1 well written
2 very well written

I stress that ratings should not be regarded as a substitute for comments and observations, or vice versa. What I really need is both comments and numerical ratings.

I do not want people to be influenced by the answers that other people give, so all comments on this post will go to my moderation queue. When I have enough data for the experiment, probably in a week or so, I will publish all the comments (unless for some reason you specifically request that your comment should not be published).

The more people who participate, the more reliable the results of the experiment will be. I realize that it may take a little time, so thank you very much in advance to everybody who agrees to help. (Update 26th March: I now have over 30 responses; they have been very helpful indeed, so I am extremely grateful for those. If they keep coming in at a similar rate over the next few days it will be wonderful.)
Read the rest of this entry »

Test

March 24, 2013

I am testing the WordPress feature that allows me to moderate all comments before allowing them to appear. This has nothing to do with the discussion on the last post. Rather, I want to be sure that the feature works before my next post, where it will be important for people to comment without seeing what others have said. So if someone could make a quick comment on this post, that would be helpful. Once I’m sure the feature is working, I’ll put up the post for which it matters.

In an ideal world, I would use the feature just for that post. However, as far as I can tell, my only options are allowing all comments, moderating all comments, or disabling comments completely on individual posts. Sending comments to the moderation queue on a post-by-post basis doesn’t seem to be possible, but if anyone knows a way, then I’d be very pleased to hear about it. Assuming there isn’t a way, then for a short while, all comments on this blog will be moderated, but I will try to approve comments on other posts regularly, so I hope this won’t be too annoying.

Update. Good job I did this test. I changed the relevant setting but didn’t click “Save settings”. Hence the three comments below.

Further update. OK, now it seems to be working just fine. Many thanks to those who sent test comments. I’ll put up the new post later this evening (British time).


Follow

Get every new post delivered to your Inbox.

Join 1,545 other followers