Player II has a winning strategy in the *-game, G*(A), iff A is countable
$begingroup$
I have a question concerning the proof of this theorem in Kechris' "Classical Descriptive Set Theory."
The rules of the game i as follows:
Let $X$ be a nonempty perfect Polish space with compatible complete metric $d$. Fix a basis ${V_n}$ of nonempty open sets for $X$. Given $Asubseteq X$, consider the game $G^*(A)$, where Player 1 (I) plays pairs of basic open sets (with certain requirements, but they are not necessary for my question), while Player 2 (II) moves by choosing one of those open sets, I plays two open sets from the set that II chose, and so on... (p. 149, Kechris).
Now, in the proof of $Rightarrow$, Kechris does as follows: Assume $sigma$ is a winning strategy for II. Given $xin A$, call a position
begin{align*}
p=((U_0^{(0)},U_1^{(0)}), i_0,...,(U_0^{(n-1)},U_1^{(n-1)}),i_{n-1}),
end{align*}
$i_jin {0,1}$, "good" for $x$, if it has been played according to $sigma$ and $xin U_{i_{n-1}}^{(n-1)}$. He then concludes that for each $xin A$ there is a maximal good $p$ for $x$. Now, if $p$ is maximal good for $x$, then
begin{align*}
xin A_p ={yin U_{i_{n-1}}^{(n-1)}:forall ,, text{legal} ,, (U_0^{(n)},U_1^{(n)}), ,, text{if i is what},, sigma,, text{requires II to play next, then},, ynot in U_i^{(n)}}.
end{align*}
He then claims that $A_p$ contains at most one point, and this is what I cannot convince myself of! Can anyone help me? :)
logic descriptive-set-theory
asked Jan 9 at 18:24
MLSMLS
233
$endgroup$
add a comment |
$begingroup$
I have a question concerning the proof of this theorem in Kechris' "Classical Descriptive Set Theory."
The rules of the game i as follows:
Let $X$ be a nonempty perfect Polish space with compatible complete metric $d$. Fix a basis ${V_n}$ of nonempty open sets for $X$. Given $Asubseteq X$, consider the game $G^*(A)$, where Player 1 (I) plays pairs of basic open sets (with certain requirements, but they are not necessary for my question), while Player 2 (II) moves by choosing one of those open sets, I plays two open sets from the set that II chose, and so on... (p. 149, Kechris).
Now, in the proof of $Rightarrow$, Kechris does as follows: Assume $sigma$ is a winning strategy for II. Given $xin A$, call a position
begin{align*}
p=((U_0^{(0)},U_1^{(0)}), i_0,...,(U_0^{(n-1)},U_1^{(n-1)}),i_{n-1}),
end{align*}
$i_jin {0,1}$, "good" for $x$, if it has been played according to $sigma$ and $xin U_{i_{n-1}}^{(n-1)}$. He then concludes that for each $xin A$ there is a maximal good $p$ for $x$. Now, if $p$ is maximal good for $x$, then
begin{align*}
xin A_p ={yin U_{i_{n-1}}^{(n-1)}:forall ,, text{legal} ,, (U_0^{(n)},U_1^{(n)}), ,, text{if i is what},, sigma,, text{requires II to play next, then},, ynot in U_i^{(n)}}.
end{align*}
He then claims that $A_p$ contains at most one point, and this is what I cannot convince myself of! Can anyone help me? :)
logic descriptive-set-theory
asked Jan 9 at 18:24
MLSMLS
233
$endgroup$
$begingroup$
Kechris explains why $A_p$ contains at most one point in the proof ("Now notice that $A_p$ contains at most one point, since..."). What part of this explanation did you not understand?
$endgroup$
– Alex Kruckman
Jan 9 at 19:46
$begingroup$
Yeah. I don't get, why he assumes that $y_iin U_i^{(n)}$.
$endgroup$
– MLS
Jan 9 at 20:18
add a comment |
$begingroup$
I have a question concerning the proof of this theorem in Kechris' "Classical Descriptive Set Theory."
The rules of the game i as follows:
Let $X$ be a nonempty perfect Polish space with compatible complete metric $d$. Fix a basis ${V_n}$ of nonempty open sets for $X$. Given $Asubseteq X$, consider the game $G^*(A)$, where Player 1 (I) plays pairs of basic open sets (with certain requirements, but they are not necessary for my question), while Player 2 (II) moves by choosing one of those open sets, I plays two open sets from the set that II chose, and so on... (p. 149, Kechris).
Now, in the proof of $Rightarrow$, Kechris does as follows: Assume $sigma$ is a winning strategy for II. Given $xin A$, call a position
begin{align*}
p=((U_0^{(0)},U_1^{(0)}), i_0,...,(U_0^{(n-1)},U_1^{(n-1)}),i_{n-1}),
end{align*}
$i_jin {0,1}$, "good" for $x$, if it has been played according to $sigma$ and $xin U_{i_{n-1}}^{(n-1)}$. He then concludes that for each $xin A$ there is a maximal good $p$ for $x$. Now, if $p$ is maximal good for $x$, then
begin{align*}
xin A_p ={yin U_{i_{n-1}}^{(n-1)}:forall ,, text{legal} ,, (U_0^{(n)},U_1^{(n)}), ,, text{if i is what},, sigma,, text{requires II to play next, then},, ynot in U_i^{(n)}}.
end{align*}
He then claims that $A_p$ contains at most one point, and this is what I cannot convince myself of! Can anyone help me? :)
logic descriptive-set-theory
asked Jan 9 at 18:24
MLSMLS
233
$endgroup$
I have a question concerning the proof of this theorem in Kechris' "Classical Descriptive Set Theory."
The rules of the game i as follows:
Let $X$ be a nonempty perfect Polish space with compatible complete metric $d$. Fix a basis ${V_n}$ of nonempty open sets for $X$. Given $Asubseteq X$, consider the game $G^*(A)$, where Player 1 (I) plays pairs of basic open sets (with certain requirements, but they are not necessary for my question), while Player 2 (II) moves by choosing one of those open sets, I plays two open sets from the set that II chose, and so on... (p. 149, Kechris).
Now, in the proof of $Rightarrow$, Kechris does as follows: Assume $sigma$ is a winning strategy for II. Given $xin A$, call a position
begin{align*}
p=((U_0^{(0)},U_1^{(0)}), i_0,...,(U_0^{(n-1)},U_1^{(n-1)}),i_{n-1}),
end{align*}
$i_jin {0,1}$, "good" for $x$, if it has been played according to $sigma$ and $xin U_{i_{n-1}}^{(n-1)}$. He then concludes that for each $xin A$ there is a maximal good $p$ for $x$. Now, if $p$ is maximal good for $x$, then
begin{align*}
xin A_p ={yin U_{i_{n-1}}^{(n-1)}:forall ,, text{legal} ,, (U_0^{(n)},U_1^{(n)}), ,, text{if i is what},, sigma,, text{requires II to play next, then},, ynot in U_i^{(n)}}.
end{align*}
He then claims that $A_p$ contains at most one point, and this is what I cannot convince myself of! Can anyone help me? :)
logic descriptive-set-theory
logic descriptive-set-theory
asked Jan 9 at 18:24
MLSMLS
233
asked Jan 9 at 18:24
MLSMLS
233
asked Jan 9 at 18:24
MLSMLS
233
asked Jan 9 at 18:24
MLSMLS
233
asked Jan 9 at 18:24
MLSMLS
233
233
$begingroup$
Kechris explains why $A_p$ contains at most one point in the proof ("Now notice that $A_p$ contains at most one point, since..."). What part of this explanation did you not understand?
$endgroup$
– Alex Kruckman
Jan 9 at 19:46
$begingroup$
Yeah. I don't get, why he assumes that $y_iin U_i^{(n)}$.
$endgroup$
– MLS
Jan 9 at 20:18
add a comment |
$begingroup$
Kechris explains why $A_p$ contains at most one point in the proof ("Now notice that $A_p$ contains at most one point, since..."). What part of this explanation did you not understand?
$endgroup$
– Alex Kruckman
Jan 9 at 19:46
$begingroup$
Yeah. I don't get, why he assumes that $y_iin U_i^{(n)}$.
$endgroup$
– MLS
Jan 9 at 20:18
$begingroup$
Kechris explains why $A_p$ contains at most one point in the proof ("Now notice that $A_p$ contains at most one point, since..."). What part of this explanation did you not understand?
$endgroup$
– Alex Kruckman
Jan 9 at 19:46
$begingroup$
Kechris explains why $A_p$ contains at most one point in the proof ("Now notice that $A_p$ contains at most one point, since..."). What part of this explanation did you not understand?
$endgroup$
– Alex Kruckman
Jan 9 at 19:46
$begingroup$
Yeah. I don't get, why he assumes that $y_iin U_i^{(n)}$.
$endgroup$
– MLS
Jan 9 at 20:18
$begingroup$
Yeah. I don't get, why he assumes that $y_iin U_i^{(n)}$.
$endgroup$
– MLS
Jan 9 at 20:18
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose for contradiction that $A_p$ contains more than one point. So we have distinct points $y_0neq y_1$ in $A_psubseteq U^{(n-1)}_{i_{n-1}}$. Now because we're in a Polish space, we can find basic open neighborhoods $y_0in U^{(n)}_0$ and $y_1in U^{(n)}_1$, each with diameter less than $2^{-n}$, such that $overline{U^{(n)}_0}cap overline{U^{(n)}_1} = emptyset$ and $overline{U^{(n)}_0cup U^{(n)}_1} subseteq U^{(n-1)}_{i_{n-1}}$.
So it is legal for Player I to play $(U^{(n)}_0, U^{(n)}_1)$, and the strategy $sigma$ requires Player II to respond with $iin {0,1}$. If $i = 0$, then $y_0in U^{(n)}_i$, contradicting $y_0in A_p$. And if $i = 1$, then $y_1in U^{(n)}_i$, contradicting $y_1in A_p$.
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
$endgroup$
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067794%2fplayer-ii-has-a-winning-strategy-in-the-game-ga-iff-a-is-countable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose for contradiction that $A_p$ contains more than one point. So we have distinct points $y_0neq y_1$ in $A_psubseteq U^{(n-1)}_{i_{n-1}}$. Now because we're in a Polish space, we can find basic open neighborhoods $y_0in U^{(n)}_0$ and $y_1in U^{(n)}_1$, each with diameter less than $2^{-n}$, such that $overline{U^{(n)}_0}cap overline{U^{(n)}_1} = emptyset$ and $overline{U^{(n)}_0cup U^{(n)}_1} subseteq U^{(n-1)}_{i_{n-1}}$.
So it is legal for Player I to play $(U^{(n)}_0, U^{(n)}_1)$, and the strategy $sigma$ requires Player II to respond with $iin {0,1}$. If $i = 0$, then $y_0in U^{(n)}_i$, contradicting $y_0in A_p$. And if $i = 1$, then $y_1in U^{(n)}_i$, contradicting $y_1in A_p$.
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
$endgroup$
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
add a comment |
$begingroup$
Suppose for contradiction that $A_p$ contains more than one point. So we have distinct points $y_0neq y_1$ in $A_psubseteq U^{(n-1)}_{i_{n-1}}$. Now because we're in a Polish space, we can find basic open neighborhoods $y_0in U^{(n)}_0$ and $y_1in U^{(n)}_1$, each with diameter less than $2^{-n}$, such that $overline{U^{(n)}_0}cap overline{U^{(n)}_1} = emptyset$ and $overline{U^{(n)}_0cup U^{(n)}_1} subseteq U^{(n-1)}_{i_{n-1}}$.
So it is legal for Player I to play $(U^{(n)}_0, U^{(n)}_1)$, and the strategy $sigma$ requires Player II to respond with $iin {0,1}$. If $i = 0$, then $y_0in U^{(n)}_i$, contradicting $y_0in A_p$. And if $i = 1$, then $y_1in U^{(n)}_i$, contradicting $y_1in A_p$.
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
$endgroup$
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
add a comment |
$begingroup$
Suppose for contradiction that $A_p$ contains more than one point. So we have distinct points $y_0neq y_1$ in $A_psubseteq U^{(n-1)}_{i_{n-1}}$. Now because we're in a Polish space, we can find basic open neighborhoods $y_0in U^{(n)}_0$ and $y_1in U^{(n)}_1$, each with diameter less than $2^{-n}$, such that $overline{U^{(n)}_0}cap overline{U^{(n)}_1} = emptyset$ and $overline{U^{(n)}_0cup U^{(n)}_1} subseteq U^{(n-1)}_{i_{n-1}}$.
So it is legal for Player I to play $(U^{(n)}_0, U^{(n)}_1)$, and the strategy $sigma$ requires Player II to respond with $iin {0,1}$. If $i = 0$, then $y_0in U^{(n)}_i$, contradicting $y_0in A_p$. And if $i = 1$, then $y_1in U^{(n)}_i$, contradicting $y_1in A_p$.
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
$endgroup$
Suppose for contradiction that $A_p$ contains more than one point. So we have distinct points $y_0neq y_1$ in $A_psubseteq U^{(n-1)}_{i_{n-1}}$. Now because we're in a Polish space, we can find basic open neighborhoods $y_0in U^{(n)}_0$ and $y_1in U^{(n)}_1$, each with diameter less than $2^{-n}$, such that $overline{U^{(n)}_0}cap overline{U^{(n)}_1} = emptyset$ and $overline{U^{(n)}_0cup U^{(n)}_1} subseteq U^{(n-1)}_{i_{n-1}}$.
So it is legal for Player I to play $(U^{(n)}_0, U^{(n)}_1)$, and the strategy $sigma$ requires Player II to respond with $iin {0,1}$. If $i = 0$, then $y_0in U^{(n)}_i$, contradicting $y_0in A_p$. And if $i = 1$, then $y_1in U^{(n)}_i$, contradicting $y_1in A_p$.
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
answered Jan 9 at 20:28
Alex KruckmanAlex Kruckman
28.4k32758
28.4k32758
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
add a comment |
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
That really helped me - thank you so much!
$endgroup$
– MLS
Jan 9 at 20:34
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
@MLS You're welcome! Instead of thanking me in a comment, you can upvote my answer (if you think it's a good answer) and/or accept it (if it settles the question).
$endgroup$
– Alex Kruckman
Jan 9 at 20:40
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
I'm afraid I can't upvote, I'm too new here.
$endgroup$
– MLS
Jan 9 at 20:42
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
$begingroup$
@MLS Ah, that's right, I forgot about the reputation restriction on voting.
$endgroup$
– Alex Kruckman
Jan 9 at 20:43
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067794%2fplayer-ii-has-a-winning-strategy-in-the-game-ga-iff-a-is-countable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Kechris explains why $A_p$ contains at most one point in the proof ("Now notice that $A_p$ contains at most one point, since..."). What part of this explanation did you not understand?
$endgroup$
– Alex Kruckman
Jan 9 at 19:46
$begingroup$
Yeah. I don't get, why he assumes that $y_iin U_i^{(n)}$.
$endgroup$
– MLS
Jan 9 at 20:18