Talk:Determinacy

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class High Priority  Field: Foundations, logic, and set theory
This article may be too technical for a general audience.
Please help improve this article by providing more context and better explanations of technical details to make it more accessible, without removing technical details.

Contents

[edit] Rationale for this page

I can easily imagine someone stumbling across this page and thinking it's an unnecessary duplication of Axiom of determinacy, an article of long standing, and ask why I don't simply try to improve that page.

Well, that was my thought originally, but I was running into all sorts of difficulties figuring out where things should go. Axiom of determinacy didn't have a good definition of "game", "strategy", or "winning strategy", and it wasn't clear where to put them. There's a winning strategy article, but it wants to be useful to game theorists as well, which was too much of a constraint.

Moreover, lots of times one wants to talk about determinacy but is not, in context, particularly interested in the axiom of determinacy. In particular, several pages had links that looked like [[Axiom of determinacy|determinacy]], when AD was perhaps not the main point of interest.

So it occurred to me that there should be a central article about determinacy in general. This is it, or rather the start of it. My vision is that this article will give the basic notions and say something about how they stand in relation to each other. Then there will be links out to more detailed articles on particular topics, such as axiom of determinacy, axiom of real determinacy, projective determinacy, long games, Blackwell games, axiom of quasideterminacy.

This article should be the central reference point for the new Category:Determinacy. If a major aspect of determinacy theory has been left out, then ideally in addition to writing an article on that particular topic, a new section or subsection should be added to this article, describing the topic briefly and saying how it relates to the other determinacy topics. --Trovatore 05:46, 2 September 2005 (UTC)

[edit] Too technical

This page needs some help to make it more accessible. I have a semi-math background (CS + statistics) and I have no idea what is going on. This needs a bit of a gentler intro (like the one for NP vs. P article which is very good ) novacatz 13:17, 13 January 2006 (UTC)

Well, that's what I had in mind for the Determinacy#Basic notions section. That strikes me as being of roughly the same level of technicality as the lead section of Complexity classes P and NP. Would you look over the "Basic notions" section again and see if you agree, and if not, let me know where it is you get lost? (As for the rest of the article, I wouldn't really expect it to be accessible to anyone without a set theory background; it's an inherently technical subject.) Thanks, Trovatore 00:13, 14 January 2006 (UTC)
Currently, the basic notions section reads like a math textbook (cf. 'firstly we shall consider...' and 'More formally, ... , recall that the latter consists of...'). If you look at the gentle introduction of NP vs. P article intro, you will see they spend a lot of time explaining what is the problem using layman English (cf. the 'time space tradeoff' has an explanation what 'time' mean and what 'space' means. You can see that the page has a lot of somewhat loose descriptions that are useful on helping people grasp why the area is interesting (eg. 'NP Complete problems can be loosely described as...'). For determinacy - the intro is a bit weak on why the field is important (some examples might help) and starts getting into the results without explaning why they are significant (eg. determinacy from ZFC). Someone with some elementary set theory knowledge (me) can appeciate this result a lot more if some explaination is provided on interepetations of the result. novacatz 04:58, 14 January 2006 (UTC)

[edit] Query

What does this phrase mean? (for example, if we say that Black wins draws at chess) Stephen B Streater 07:54, 1 April 2006 (UTC)

It means, if we modify the rules of chess, keeping everything the same except that if the play ends in a draw according to traditional chess, we'll say that Black has won. It hadn't occurred to me that this wasn't clear. Can you think of better, but still hopefully concise, language? --Trovatore 15:28, 1 April 2006 (UTC)
I misread "draws" as a verb like "wins". It makes sense as a noun. How about "wins all draws"? Stephen B Streater 16:37, 1 April 2006 (UTC)
Or "wins all drawn positions". Stephen B Streater 16:37, 1 April 2006 (UTC)
Go for it. You might also mention that Black should win if play continues forever (that's optional because it doesn't really matter; in any play that continues forever there are opportunities for Black to claim a draw, and therefore a win). --Trovatore 16:40, 1 April 2006 (UTC)
I've made the first change. Is your second point about play continuing for ever referring only to the modified chess (ie repeated positions leading to a draw)? Presumably there are games which can go on for ever without leading to a draw eg two sides take turns to write down numbers and the one with the biggest number written down wins. I'll have to think this game through to see if it counts as a game in this article, as the game may never finish but it never be obvious this is going to happen so never be a draw either. Stephen B Streater 18:37, 1 April 2006 (UTC)
Oh yes, that point was specific to chess. In most of the interesting cases studied, play can go on forever without any finite part of the play determining the winner. (However I don't really follow your "biggest number" example; why should the set of numbers written down have a greatest element?) --Trovatore 18:40, 1 April 2006 (UTC)
Thanks - I'll put something in, though the chess example is getting quite long, particularly as we can't necessarily assume that everyone understands the draw-by-repetition rule - I might put all the chess bits together and not in brackets. The game I described may not have a biggest element, but it may do. But if it did have a biggest element, I was thinking you wouldn't know in finite time, so couldn't end the game. But then perhaps you could find the maximum element in an infinite set. Stephen B Streater 19:20, 1 April 2006 (UTC)
An infinite set of naturals cannot have a maximal element. However, you could make rules like:
  • If there is a greatest number played, then the player who played it, wins. If both players have played that number, then the first one to play it wins.
  • If there is no greatest number played, then the second player wins.
This game is trivially a win for the second player, who can guarantee that no greatest number is played, just by playing ever-bigger numbers on subsequent plays. But it is an example of a game whose winning condition is not determined by any finite part of the play (after any finitely many moves, it is still possible for either player to win; while the second player can always force a win if he wants to, there's no guarantee that he will). --Trovatore 19:26, 1 April 2006 (UTC)

[edit] chess example

So I agree that the wording is now clearer, but I see a couple of problems:

  • You assert that "Black can eventually force a win", which assumes that unmodified chess is not an outright win for White. Surely this is still unknown?
  • Yes - it is unknown whether white can force a win in chess. I assumed that if play continued long enough then repetition would have occurred, so Black could claim a draw/win. Stephen B Streater 21:47, 1 April 2006 (UTC)
I think your wording makes this clear. Stephen B Streater 21:49, 1 April 2006 (UTC)
  • You've lost the point about the connection with clopen sets. --Trovatore 19:39, 1 April 2006 (UTC)
Fixed the first point. I await your input on the second (your help here could be very useful in making this section accessible). --Trovatore 21:33, 1 April 2006 (UTC)
I didn't change the mention of clopen sets - it is now in the first paragraph general description. Would you prefer it to be referred to again in the particular example of modified chess? Stephen B Streater 21:47, 1 April 2006 (UTC)
Sorry, you're right; I looked at the diff too fast. --Trovatore 23:03, 1 April 2006 (UTC)

[edit] Discussion from the AC page

Aleph4 pointed out at Talk:Axiom of choice that determinacy for games on arbitary sets implies the axiom of choice, and also implies that a countable union of countable sets is countable. The second result can be modified to show in AD that a countable union of countable sets of reals is countable. These facts are very interesting to me and ought to appear here. Also, Martin's later paper on Borel Determinacy would be good to reference; it is much easier to read than his first one from the Annals. I will get to this sometime, so you can view this message as a reminder to myself as much as a prod to everyone else. CMummert 12:09, 6 October 2006 (UTC)

[edit] Split out Gale-Stewart games?

I want to suggest making an article on Gale-Stewart games, which would be an expansion of the Games section here. Then this article could just have a summary of the topic with a link to the main article. The topics for the Gale-Stewart games article would be:

  • The definition of a Gale-Stewart game on Xω where X is any set (as in Martin's paper on Borel determinacy). The specific cases for Cantor and Baire space.
  • The definition of a winning strategy.
  • A statement of the theorem that closed games are determined.
  • A link to Determinacy.

I am willing to do the writing; I want to see if there are objections before I do it. CMummert 17:37, 15 November 2006 (UTC)

Well, I guess my concern is, what exactly is a Gale–Stewart game? One with a clopen payoff set? Is this really standard terminology? Gale's and Stewart's result is key, of course, but I really don't recall coming across this nomenclature for the games. --Trovatore 19:48, 15 November 2006 (UTC)
A Gale-Stewart game is just a two-player game of perfect information of length ω. This is standard terminology in some parts of the world; a google search turned up quite a few papers such as [1] [2] that use the term without further citation. From JStor, I found that Jockusch uses the term (The Journal of Symbolic Logic Vol. 38, No. 2 (Jun., 1973), pp. 293-294) and so does Becker (The Journal of Symbolic Logic Vol. 50, No. 1 (Mar., 1985), pp. 110-122). So I think it is standard. CMummert 20:35, 15 November 2006 (UTC)
Hm, still not too excited about giving the concept a name I'd never really heard for it. This is the content I'd intended to treat in the "games played on trees" section of the article. --Trovatore 21:36, 15 November 2006 (UTC)
The idea I had in mind is to separate the material on games (which don't require strong axioms to define and are of interest in ZFC) from the material on determinacy beyond ZFC, which is more esoteric. Since Gale-Stewart game is a standard term describing these games, that was the title I suggested, but any other title is OK with me. The present article, if all the sections were filled in, would be quite long and intimidating. CMummert 22:02, 15 November 2006 (UTC)
The article might be a good idea. I think it would be unfortunate, though, if it presented ZFC as some sort of natural dividing line. I really don't think it is. --Trovatore 07:07, 9 December 2006 (UTC)

[edit] Angle brackets

I think the angle brackets should be written as "\langle" and "\rangle" instead of "<" and ">". --Trigamma 18:15, 8 December 2006 (UTC)

I don't like \langle and \rangle; never have. They are too tall, and the angle is too obtuse. It would be nice to have something a little bit in between. --Trovatore 18:46, 8 December 2006 (UTC)
My problem is that < and > are typeset the wrong way: they are not treated as delimiters but as binary relations. You can see that in the first formula, where the closing > is next to the \in. But by the way: Why do you use angle brackets at all and not round parentheses? --Trigamma 19:54, 8 December 2006 (UTC)
Um. In my experience, angle brackets are just more usual, in set theory, as a way to indicate tuples, than are round brackets. I don't really know why this should be so. Maybe they have fewer other meanings (for example, (αβ) could be the pair <α,β> or the open interval from α to β). --Trovatore 21:09, 8 December 2006 (UTC)