Talk:Determinacy

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
High Importance
 Field: Foundations, logic, and set theory

Rationale for this page[edit]

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)

Too technical[edit]

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)

Query[edit]

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)

chess example[edit]

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)

Discussion from the AC page[edit]

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)

Split out Gale-Stewart games?[edit]

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^\omega 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)

Angle brackets[edit]

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)

Determinacy from ZFC[edit]

Quote from the article:

"Martin's proof uses the powerset axiom in an essential way. There is a level-by-level result detailing what fragment of the powerset axiom is necessary to guarantee determinacy through what level of the Borel hierarchy."

I am curious about what "fragment of the powerset axiom" means more precisely. Does it mean that in this and that model, built not using the full power set operation but something that is possibly weaker (like when L is built compared to when V is built), then determinacy is guaranteed through a lower degree inte the model? YohanN7 (talk) 14:47, 14 September 2009 (UTC)

It means: how many iterations of the powerset axiom are required in order to guarantee the desired amount of determinacy. In other words, there is result giving the minimum necessary α for Vα to be a model of the desired amount of determinacy. Now the powerset axiom itself says nothing about iteration; it is really the axiom of replacement that is used to ensure that the ordinals in the model are long enough. — Carl (CBM · talk) 15:18, 14 September 2009 (UTC)
Ah, that explains it. Would you mind if I attempt a rewording of that passage in the article? YohanN7 (talk) 16:37, 14 September 2009 (UTC)
It appears to be done already. Things happen quickly here;) YohanN7 (talk) 16:49, 14 September 2009 (UTC)

Blackwell Games[edit]

Didn't Donald Martin prove that determinacy for a set implies Blackwell determinacy for that set? I don't think that's mentioned on the page (and I don't have access to the paper).Chimpionspeak (talk) 17:33, 12 March 2011 (UTC)

I don't believe he ever proved that, no, though I wouldn't swear to it. I think that's still open. Generally what has been proved is consistent with that (e.g. I think that the large cardinals you need to prove Π11-determinacy are the same as you need to prove Π11-Blackwell determinacy) but as far as I know the proof has not been uniformized. I could be completely wrong though. Get in touch with Benedikt Löwe if you really want to know. --Trovatore (talk) 21:21, 12 March 2011 (UTC)
Hi, I checked this, and it is as I remembered. Have made the necessary changes. Chimpionspeak (talk) 16:30, 14 March 2011 (UTC)
I just took a ten-second look at the paper, and I don't actually see that result. Could you point me to it? What it says in the opening is that if all (length-ω on the naturals) perfect-information games are determined, then so are all Blackwell games, which is not the same thing as saying that if an individual game is determined then it's determined as a Blackwell game. --Trovatore (talk) 18:23, 14 March 2011 (UTC)
I found Martin's 1998 paper. What he says is
[W]e associate with each Blackwell game a family of perfect information games, and we show that the (mixed strategy) determinacy of the former follows from the (pure strategy) determinacy of the latter. The complexity of the payoff function for the Blackwell game is approximately the same as the complexity of the payoff sets for the perfect information games. In particular, this means that the determinacy of Blackwell games with Borel measurable payoff function follows from the known determinacy of perfect information games with Borel payoff sets.
So this is close to the idea you were trying to get across, but does not appear to justify the precise text you added. --Trovatore (talk) 19:00, 14 March 2011 (UTC)
I think I have the outline of a refutation of the game-by-game claim. First, consider the trivial "matching game": The players play zeroes and ones and, at the end, II wins if his every move exactly matches I's immediately previous move. Clearly II has a winning strategy for this game, as a perfect-information game. On the other hand, as a Blackwell game, I simply plays each value with probability 0.5, and then any strategy for II has value 0 for II.
That by itself doesn't refute the claim — the game is determined in both senses; it just has a different winner.
But now take some non-Blackwell-determined game G (with a 0-1 payoff function). Now I and II play the matching game on even pairs of moves, and G on odd pairs of moves. For I to win, he has to win both games.
As a perfect-information game, this is a win for II. He just plays his winning strategy on the even pairs of moves, and doesn't care what happens on the odd.
But as a Blackwell game, presumably I plays his winning strategy on the even pairs, and then the game (more or less) reduces to G on the odd pairs, which is not determined.
There's some work to be done in the "(more or less)" part. You have to make sure that the even moves don't in some tricky way help one of the players win on the odd moves. But I'm confident it can be done (might require a careful choice of G). --Trovatore (talk) 20:28, 14 March 2011 (UTC)
Right, there is some subtlety that I had missed out on, sorry. I searched a little more, and theorems 7 and 12 here say that for boldface pointclasses, determinacy for omega-games in the pointclass implies Blackwell-determinacy for the same pointclass. Have made the necessary changes. Chimpionspeak (talk) 20:37, 14 March 2011 (UTC)
We were editing at the same time. I think your argument should work (again, modulo the "more or less"). I am a little embarrassed to admit that I do not know much about Blackwell games! But your argument does make sense. Chimpionspeak (talk) 20:48, 14 March 2011 (UTC)

Does an infinite game ever end?[edit]

Yes it does. At least in the sense that if both players actually have strategies as described in the article, then the recursion theorem guarantees that there is a sequence f:ω->ω whose values can be matched against the lookup table. This escaped me when I first read the article (quite some time ago). Perhaps the article could point out that (and why) the infinite games end? YohanN7 (talk) 19:57, 5 April 2011 (UTC)

Payoff sets[edit]

Hi!

Q: Does the payoff set (A in the article) by definition include finite sequences too?

If not, the subsection "Winning Strategies" need to be clarified. I.e. there is a sequence in A beginning with the old moves plus our new one.

/Johan — Preceding unsigned comment added by 90.225.13.43 (talk) 09:52, 5 April 2012 (UTC)

I'm not entirely clear what you're saying here. The sequence
\langle\sigma(\langle\rangle),a_1,\sigma(\langle\sigma(\langle\rangle),a_1\rangle),a_3,\ldots\rangle
is infinite (that's what the dot dot dot means), so I don't see any issue raised by the fact that A consists of infinite sequences. Did you have some other piece of text in mind? --Trovatore (talk) 21:59, 5 April 2012 (UTC)