Timeline for Explicit examples of undetermined games
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2014 at 6:36 | vote | accept | Wojowu | ||
| Oct 5, 2014 at 6:35 | comment | added | Wojowu | Now I can see that your idea can be made into an explicit example of the game. Thanks! | |
| Oct 5, 2014 at 0:47 | comment | added | Joel David Hamkins | @bof, yes, I agree; I was mentioning the game only as an interesting one of a similar type. I believe it is consistent that there are sets for which it is not determined. | |
| Oct 5, 2014 at 0:43 | comment | added | bof | @JoelDavidHamkins Of course your infinite-Dedekind-finite-set game is not necessarily undetermined, e.g., if the infinite Dedekind-finite set $A$ happens to be the union of a set of disjoint two-element sets, then the second player has a winning strategy. | |
| Oct 4, 2014 at 21:55 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 73 characters in body
|
| Oct 4, 2014 at 21:49 | comment | added | Joel David Hamkins | The argument of my answer is explicit, by simply combining the cases into one game. I have edited to explain this. | |
| Oct 4, 2014 at 21:48 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Added explicit game
|
| Oct 4, 2014 at 21:33 | comment | added | Wojowu | Yes, games can be played on any set, and can also have transfinite length. | |
| Oct 4, 2014 at 21:30 | comment | added | Joel David Hamkins | I assumed we were considering games on any set. In ZF+AD, for example, one can prove open determinacy, etc., for games on any set. And Borel determinacy similarly holds for these kinds of games quite generally. | |
| Oct 4, 2014 at 21:28 | comment | added | Asaf Karagila♦ | @Wojowu, Joel: I think there is some misunderstanding here, as to what sort of games we are playing. What is the set from which we choose elements? Are we only talking about games played on $\omega$, or are we talking about general games played on general sets? | |
| Oct 4, 2014 at 21:24 | comment | added | Joel David Hamkins | We don't have to go to sets arbitrarily high, since if AC holds for families of sets of reals, then AD fails for the usual reason. | |
| Oct 4, 2014 at 21:24 | comment | added | Wojowu | @JoelDavidHamkins As far as I can understand, your game isn't really explicit, because it either requires the existence of a family without choice function, or existence of specific choice function for some family. In either case, it doesn't fit my definition of "explicit". | |
| Oct 4, 2014 at 21:22 | comment | added | Wojowu | @AsafKaragila I know this example cannot be made more constructive, but maybe we can use other means to get such a game. | |
| Oct 4, 2014 at 21:21 | comment | added | Asaf Karagila♦ | Joel, "(because we have to take set $X$ without specifying it)", taken from the first comment. | |
| Oct 4, 2014 at 21:14 | comment | added | Joel David Hamkins | Asaf, if you notice, wowoju is using a peculiar notion of "explicit", to mean just "provable in ZF". So I think the observation actually provides what he asked for. I have edited my answer to make this more explicit. Namely, ZF refutes $\text{AD}_{P(\mathbb{R})}$. | |
| Oct 4, 2014 at 21:12 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 1219 characters in body
|
| Oct 4, 2014 at 21:11 | comment | added | Asaf Karagila♦ | @Wojowu: Unless you can specify exactly what is the set witnessing the failure of the axiom of choice, and to what degree it fails, I don't see how you can make this more constructive. Since the axiom of choice can hold up to an arbitrary rank, and then fail badly, there's really no way around it. If you want this to be explicit, you can always assume that $X$ is $\Bbb R$, for example, something. But that's a stronger assumption than just "$\sf DC$ fails". The slogan to this situation is that if you want more, you have to assume more. | |
| Oct 4, 2014 at 15:52 | comment | added | Joel David Hamkins | Yes, that's right. There is another related game, given an infinite Dedekind finite set $A$. Players play $a_0,a_1,a_2,\ldots$ from $A$, and the first player to repeat or play outside $A$ loses. Since $A$ has no countably infinite subset, this always happens. | |
| Oct 4, 2014 at 15:50 | comment | added | Wojowu | Very interesting example! Too bad that it isn't really constructive (because we have to take set $X$ without specifying it). I'll modify a question to disallow that, but this is still very cool game! This can be also adapted to make an undetermined game given that AC fails. Let F be family of nonempty sets for which choice fails. If first player chooses set A in F, then player 2 has to choose element B of A. By similar reasoning this game is undetermined. | |
| Oct 4, 2014 at 15:39 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |