A two player game on compact topological spaces
up vote
7
down vote
favorite
I've though of an infinite game that two players may play on a given topological space $(X,tau)$. It goes like this.
On turn $n$ Player I selects a point $x_nin X$ and Player II selects a neighborhood $U_n$ of $x$.
They play $omega$ times, and Player I wins if ${U_n}_n$ is a cover of $X$.
Thinking about it I've come up with what I believe are some true statements regarding this game.
-If $(X,tau)$ is not Lindelöf then Player II has always a winning strategy.
-If $(X,tau)$ is countable than Player I has always a winning strategy.
-If $X=[0,1]$ then Player II has a winning strategy (just choose interval neighborhoods with increasingly smaller diameter, in such a way that the series given by adding them converges to a value smaller that $1$).
-If $X=omega_1+1$ (or any successor ordinal) then Player I has a winning strategy.
Now I think it might be that, given that $(X,tau)$ is compact, one of the players always has a winning strategy (i.e. the game is determined), because open games are determined. I mean, this depends on whether open games on game spaces of the form $S^omega$, not necessarily the Baire space, are always determined.
My question is whether it is known if this dividing line among compact topologies, namely whether Player I or Player II has a winning strategy in this game, has strong consequences in any direction.
For example it might be that this can be framed in terms of classical topological properties.
general-topology compactness game-theory infinite-games
add a comment |
up vote
7
down vote
favorite
I've though of an infinite game that two players may play on a given topological space $(X,tau)$. It goes like this.
On turn $n$ Player I selects a point $x_nin X$ and Player II selects a neighborhood $U_n$ of $x$.
They play $omega$ times, and Player I wins if ${U_n}_n$ is a cover of $X$.
Thinking about it I've come up with what I believe are some true statements regarding this game.
-If $(X,tau)$ is not Lindelöf then Player II has always a winning strategy.
-If $(X,tau)$ is countable than Player I has always a winning strategy.
-If $X=[0,1]$ then Player II has a winning strategy (just choose interval neighborhoods with increasingly smaller diameter, in such a way that the series given by adding them converges to a value smaller that $1$).
-If $X=omega_1+1$ (or any successor ordinal) then Player I has a winning strategy.
Now I think it might be that, given that $(X,tau)$ is compact, one of the players always has a winning strategy (i.e. the game is determined), because open games are determined. I mean, this depends on whether open games on game spaces of the form $S^omega$, not necessarily the Baire space, are always determined.
My question is whether it is known if this dividing line among compact topologies, namely whether Player I or Player II has a winning strategy in this game, has strong consequences in any direction.
For example it might be that this can be framed in terms of classical topological properties.
general-topology compactness game-theory infinite-games
1
If $X$ is not compact, Player I may still have a winning strategy: consider the discrete topology on $mathbb{N}$. Player I just picks $n$ for each inning $n$. (If $X$ is not Lindelöf then Player II has a winning strategy: just play sets in an open cover without a countable subcover.)
– 1-3-7-Trimethylxanthine
Dec 1 at 19:17
@1-3-7-Trimethylxanthine you're right I'll change it to Lindelöf.
– Anguepa
Dec 1 at 19:25
The argument you used to show that Player II has a winning strategy if $X=[0,1]$ can be used to show, more generally, that Player II has a winning strategy if $Xsubseteqmathbb R$ does not have strong measure zero. Therefore, if Borel's conjecture holds, then Player II has a winning strategy for every uncountable set $Xsubseteqmathbb R$. (Borel's conjecture is the assertion that no uncountable subset of $mathbb R$ has strong measure zero; it has been shown by Richard Laver to be consistent.)
– bof
Dec 2 at 1:12
@bof sure, thank you, I edited.
– Anguepa
Dec 6 at 13:14
add a comment |
up vote
7
down vote
favorite
up vote
7
down vote
favorite
I've though of an infinite game that two players may play on a given topological space $(X,tau)$. It goes like this.
On turn $n$ Player I selects a point $x_nin X$ and Player II selects a neighborhood $U_n$ of $x$.
They play $omega$ times, and Player I wins if ${U_n}_n$ is a cover of $X$.
Thinking about it I've come up with what I believe are some true statements regarding this game.
-If $(X,tau)$ is not Lindelöf then Player II has always a winning strategy.
-If $(X,tau)$ is countable than Player I has always a winning strategy.
-If $X=[0,1]$ then Player II has a winning strategy (just choose interval neighborhoods with increasingly smaller diameter, in such a way that the series given by adding them converges to a value smaller that $1$).
-If $X=omega_1+1$ (or any successor ordinal) then Player I has a winning strategy.
Now I think it might be that, given that $(X,tau)$ is compact, one of the players always has a winning strategy (i.e. the game is determined), because open games are determined. I mean, this depends on whether open games on game spaces of the form $S^omega$, not necessarily the Baire space, are always determined.
My question is whether it is known if this dividing line among compact topologies, namely whether Player I or Player II has a winning strategy in this game, has strong consequences in any direction.
For example it might be that this can be framed in terms of classical topological properties.
general-topology compactness game-theory infinite-games
I've though of an infinite game that two players may play on a given topological space $(X,tau)$. It goes like this.
On turn $n$ Player I selects a point $x_nin X$ and Player II selects a neighborhood $U_n$ of $x$.
They play $omega$ times, and Player I wins if ${U_n}_n$ is a cover of $X$.
Thinking about it I've come up with what I believe are some true statements regarding this game.
-If $(X,tau)$ is not Lindelöf then Player II has always a winning strategy.
-If $(X,tau)$ is countable than Player I has always a winning strategy.
-If $X=[0,1]$ then Player II has a winning strategy (just choose interval neighborhoods with increasingly smaller diameter, in such a way that the series given by adding them converges to a value smaller that $1$).
-If $X=omega_1+1$ (or any successor ordinal) then Player I has a winning strategy.
Now I think it might be that, given that $(X,tau)$ is compact, one of the players always has a winning strategy (i.e. the game is determined), because open games are determined. I mean, this depends on whether open games on game spaces of the form $S^omega$, not necessarily the Baire space, are always determined.
My question is whether it is known if this dividing line among compact topologies, namely whether Player I or Player II has a winning strategy in this game, has strong consequences in any direction.
For example it might be that this can be framed in terms of classical topological properties.
general-topology compactness game-theory infinite-games
general-topology compactness game-theory infinite-games
edited Dec 6 at 13:11
asked Dec 1 at 18:53
Anguepa
1,346819
1,346819
1
If $X$ is not compact, Player I may still have a winning strategy: consider the discrete topology on $mathbb{N}$. Player I just picks $n$ for each inning $n$. (If $X$ is not Lindelöf then Player II has a winning strategy: just play sets in an open cover without a countable subcover.)
– 1-3-7-Trimethylxanthine
Dec 1 at 19:17
@1-3-7-Trimethylxanthine you're right I'll change it to Lindelöf.
– Anguepa
Dec 1 at 19:25
The argument you used to show that Player II has a winning strategy if $X=[0,1]$ can be used to show, more generally, that Player II has a winning strategy if $Xsubseteqmathbb R$ does not have strong measure zero. Therefore, if Borel's conjecture holds, then Player II has a winning strategy for every uncountable set $Xsubseteqmathbb R$. (Borel's conjecture is the assertion that no uncountable subset of $mathbb R$ has strong measure zero; it has been shown by Richard Laver to be consistent.)
– bof
Dec 2 at 1:12
@bof sure, thank you, I edited.
– Anguepa
Dec 6 at 13:14
add a comment |
1
If $X$ is not compact, Player I may still have a winning strategy: consider the discrete topology on $mathbb{N}$. Player I just picks $n$ for each inning $n$. (If $X$ is not Lindelöf then Player II has a winning strategy: just play sets in an open cover without a countable subcover.)
– 1-3-7-Trimethylxanthine
Dec 1 at 19:17
@1-3-7-Trimethylxanthine you're right I'll change it to Lindelöf.
– Anguepa
Dec 1 at 19:25
The argument you used to show that Player II has a winning strategy if $X=[0,1]$ can be used to show, more generally, that Player II has a winning strategy if $Xsubseteqmathbb R$ does not have strong measure zero. Therefore, if Borel's conjecture holds, then Player II has a winning strategy for every uncountable set $Xsubseteqmathbb R$. (Borel's conjecture is the assertion that no uncountable subset of $mathbb R$ has strong measure zero; it has been shown by Richard Laver to be consistent.)
– bof
Dec 2 at 1:12
@bof sure, thank you, I edited.
– Anguepa
Dec 6 at 13:14
1
1
If $X$ is not compact, Player I may still have a winning strategy: consider the discrete topology on $mathbb{N}$. Player I just picks $n$ for each inning $n$. (If $X$ is not Lindelöf then Player II has a winning strategy: just play sets in an open cover without a countable subcover.)
– 1-3-7-Trimethylxanthine
Dec 1 at 19:17
If $X$ is not compact, Player I may still have a winning strategy: consider the discrete topology on $mathbb{N}$. Player I just picks $n$ for each inning $n$. (If $X$ is not Lindelöf then Player II has a winning strategy: just play sets in an open cover without a countable subcover.)
– 1-3-7-Trimethylxanthine
Dec 1 at 19:17
@1-3-7-Trimethylxanthine you're right I'll change it to Lindelöf.
– Anguepa
Dec 1 at 19:25
@1-3-7-Trimethylxanthine you're right I'll change it to Lindelöf.
– Anguepa
Dec 1 at 19:25
The argument you used to show that Player II has a winning strategy if $X=[0,1]$ can be used to show, more generally, that Player II has a winning strategy if $Xsubseteqmathbb R$ does not have strong measure zero. Therefore, if Borel's conjecture holds, then Player II has a winning strategy for every uncountable set $Xsubseteqmathbb R$. (Borel's conjecture is the assertion that no uncountable subset of $mathbb R$ has strong measure zero; it has been shown by Richard Laver to be consistent.)
– bof
Dec 2 at 1:12
The argument you used to show that Player II has a winning strategy if $X=[0,1]$ can be used to show, more generally, that Player II has a winning strategy if $Xsubseteqmathbb R$ does not have strong measure zero. Therefore, if Borel's conjecture holds, then Player II has a winning strategy for every uncountable set $Xsubseteqmathbb R$. (Borel's conjecture is the assertion that no uncountable subset of $mathbb R$ has strong measure zero; it has been shown by Richard Laver to be consistent.)
– bof
Dec 2 at 1:12
@bof sure, thank you, I edited.
– Anguepa
Dec 6 at 13:14
@bof sure, thank you, I edited.
– Anguepa
Dec 6 at 13:14
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Neat question, and it has a neat answer for compact Hausdorff spaces. Namely, Player II can win in a compact Hausdorff space $X$ iff $X$ contains a nonempty perfect subset (a closed subset with no isolated points).
First, suppose $X$ has a nonempty perfect subset $A$. We may as well assume $X=A$ then (if Player I picks a point outside $A$, just pick $Xsetminus A$ as the open set), so that $X$ is perfect. Now note that if $Usubseteq X$ is open, then $U$ has no isolated points either and so $overline{U}$ is perfect as well. So, when Player I picks a point $x_1$, here's what Player II can do. Since $x_1$ is not isolated, there exists another point $yin X$. Since $X$ is Hausdorff, there are disjoint open sets $U,Vsubset X$ with $x_1in V$ and $yin U$. Player II then chooses $U_1=Xsetminus overline{U}$.
Now $A=overline{U}$ is again a nonempty perfect subset of $X$, and so we may again replace $X$ with this subset for subsequent turns. So, Player II can continue the game for any number of turns, ensuring that after every turn, there is still a nonempty perfect set which has not been covered by the open sets chosen so far. By compactness, the open sets cannot cover the whole space after infinitely many steps either, so Player II wins.
Conversely, suppose $X$ has no nonempty perfect subset. Recall that the Cantor-Bendixson derivative $X'$ of $X$ is the complement of the set of isolated points of $X$. We can then iterate this process transfinitely, defining $$X_0=X,$$ $$X_{alpha+1}=X_alpha',$$ and $$X_alpha=bigcap_{beta<alpha}X_beta$$ when $alpha$ is a limit ordinal. Each $X_alpha$ is a closed subset of $X$, and $X_{alpha+1}$ is always a proper subset of $X_alpha$ (unless $X_alpha$ is empty) since $X_alpha$ is not perfect. So, there must exist some ordinal $alpha$ such that $X_alpha=emptyset$. The least such $alpha$ will be a successor, and its predecessor $beta$ is called the Cantor-Bendixson rank of $X$.
We now prove that Player I has a winning strategy, by induction on the Cantor-Bendixson rank $beta$. Note that since $X_{beta+1}=emptyset$, $X_beta$ is a discrete space, which must be finite by compactness. So, Player I uses their first $|X_beta|$ turns to pick each of the points of $X_beta$. After those turns, let $Ysubset X$ be the subspace that has still not been covered by the open sets chosen. It is clear by induction that $Y_alphasubseteq X_alpha$ for all $alpha$, and so $Y_beta=emptyset$ since $Y$ contains no points of $X_beta$. Thus $Y$ has Cantor-Bendixson rank less than $beta$. So, by induction, Player I can win the game on $Y$. Since they have already covered all the points of $Xsetminus Y$, this is enough to win the game on $X$.
(In fact, we can relax the assumption that $X$ is compact Hausdorff a bit. For Player II to win by the first argument, we need only for $X$ to contain a nonempty closed compact Hausdorff subset with no isolated points. And for Player I to win by the second argument, we only need $X$ to be compact and contain no nonempty perfect subset.)
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
2
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
add a comment |
up vote
3
down vote
According to the Wikipedia article on topological games, your game is known as the point-open game. Wikipedia has no more information about this game, but refers to the paper Rastislav Telgârsky, Topological games: on the 50th anniversary of the Banach–Mazur game, Rocky Mountain J. Math. 17 (1987), 227–276, which has a lot of information about it.
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',
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%2f3021675%2fa-two-player-game-on-compact-topological-spaces%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Neat question, and it has a neat answer for compact Hausdorff spaces. Namely, Player II can win in a compact Hausdorff space $X$ iff $X$ contains a nonempty perfect subset (a closed subset with no isolated points).
First, suppose $X$ has a nonempty perfect subset $A$. We may as well assume $X=A$ then (if Player I picks a point outside $A$, just pick $Xsetminus A$ as the open set), so that $X$ is perfect. Now note that if $Usubseteq X$ is open, then $U$ has no isolated points either and so $overline{U}$ is perfect as well. So, when Player I picks a point $x_1$, here's what Player II can do. Since $x_1$ is not isolated, there exists another point $yin X$. Since $X$ is Hausdorff, there are disjoint open sets $U,Vsubset X$ with $x_1in V$ and $yin U$. Player II then chooses $U_1=Xsetminus overline{U}$.
Now $A=overline{U}$ is again a nonempty perfect subset of $X$, and so we may again replace $X$ with this subset for subsequent turns. So, Player II can continue the game for any number of turns, ensuring that after every turn, there is still a nonempty perfect set which has not been covered by the open sets chosen so far. By compactness, the open sets cannot cover the whole space after infinitely many steps either, so Player II wins.
Conversely, suppose $X$ has no nonempty perfect subset. Recall that the Cantor-Bendixson derivative $X'$ of $X$ is the complement of the set of isolated points of $X$. We can then iterate this process transfinitely, defining $$X_0=X,$$ $$X_{alpha+1}=X_alpha',$$ and $$X_alpha=bigcap_{beta<alpha}X_beta$$ when $alpha$ is a limit ordinal. Each $X_alpha$ is a closed subset of $X$, and $X_{alpha+1}$ is always a proper subset of $X_alpha$ (unless $X_alpha$ is empty) since $X_alpha$ is not perfect. So, there must exist some ordinal $alpha$ such that $X_alpha=emptyset$. The least such $alpha$ will be a successor, and its predecessor $beta$ is called the Cantor-Bendixson rank of $X$.
We now prove that Player I has a winning strategy, by induction on the Cantor-Bendixson rank $beta$. Note that since $X_{beta+1}=emptyset$, $X_beta$ is a discrete space, which must be finite by compactness. So, Player I uses their first $|X_beta|$ turns to pick each of the points of $X_beta$. After those turns, let $Ysubset X$ be the subspace that has still not been covered by the open sets chosen. It is clear by induction that $Y_alphasubseteq X_alpha$ for all $alpha$, and so $Y_beta=emptyset$ since $Y$ contains no points of $X_beta$. Thus $Y$ has Cantor-Bendixson rank less than $beta$. So, by induction, Player I can win the game on $Y$. Since they have already covered all the points of $Xsetminus Y$, this is enough to win the game on $X$.
(In fact, we can relax the assumption that $X$ is compact Hausdorff a bit. For Player II to win by the first argument, we need only for $X$ to contain a nonempty closed compact Hausdorff subset with no isolated points. And for Player I to win by the second argument, we only need $X$ to be compact and contain no nonempty perfect subset.)
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
2
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
add a comment |
up vote
2
down vote
accepted
Neat question, and it has a neat answer for compact Hausdorff spaces. Namely, Player II can win in a compact Hausdorff space $X$ iff $X$ contains a nonempty perfect subset (a closed subset with no isolated points).
First, suppose $X$ has a nonempty perfect subset $A$. We may as well assume $X=A$ then (if Player I picks a point outside $A$, just pick $Xsetminus A$ as the open set), so that $X$ is perfect. Now note that if $Usubseteq X$ is open, then $U$ has no isolated points either and so $overline{U}$ is perfect as well. So, when Player I picks a point $x_1$, here's what Player II can do. Since $x_1$ is not isolated, there exists another point $yin X$. Since $X$ is Hausdorff, there are disjoint open sets $U,Vsubset X$ with $x_1in V$ and $yin U$. Player II then chooses $U_1=Xsetminus overline{U}$.
Now $A=overline{U}$ is again a nonempty perfect subset of $X$, and so we may again replace $X$ with this subset for subsequent turns. So, Player II can continue the game for any number of turns, ensuring that after every turn, there is still a nonempty perfect set which has not been covered by the open sets chosen so far. By compactness, the open sets cannot cover the whole space after infinitely many steps either, so Player II wins.
Conversely, suppose $X$ has no nonempty perfect subset. Recall that the Cantor-Bendixson derivative $X'$ of $X$ is the complement of the set of isolated points of $X$. We can then iterate this process transfinitely, defining $$X_0=X,$$ $$X_{alpha+1}=X_alpha',$$ and $$X_alpha=bigcap_{beta<alpha}X_beta$$ when $alpha$ is a limit ordinal. Each $X_alpha$ is a closed subset of $X$, and $X_{alpha+1}$ is always a proper subset of $X_alpha$ (unless $X_alpha$ is empty) since $X_alpha$ is not perfect. So, there must exist some ordinal $alpha$ such that $X_alpha=emptyset$. The least such $alpha$ will be a successor, and its predecessor $beta$ is called the Cantor-Bendixson rank of $X$.
We now prove that Player I has a winning strategy, by induction on the Cantor-Bendixson rank $beta$. Note that since $X_{beta+1}=emptyset$, $X_beta$ is a discrete space, which must be finite by compactness. So, Player I uses their first $|X_beta|$ turns to pick each of the points of $X_beta$. After those turns, let $Ysubset X$ be the subspace that has still not been covered by the open sets chosen. It is clear by induction that $Y_alphasubseteq X_alpha$ for all $alpha$, and so $Y_beta=emptyset$ since $Y$ contains no points of $X_beta$. Thus $Y$ has Cantor-Bendixson rank less than $beta$. So, by induction, Player I can win the game on $Y$. Since they have already covered all the points of $Xsetminus Y$, this is enough to win the game on $X$.
(In fact, we can relax the assumption that $X$ is compact Hausdorff a bit. For Player II to win by the first argument, we need only for $X$ to contain a nonempty closed compact Hausdorff subset with no isolated points. And for Player I to win by the second argument, we only need $X$ to be compact and contain no nonempty perfect subset.)
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
2
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Neat question, and it has a neat answer for compact Hausdorff spaces. Namely, Player II can win in a compact Hausdorff space $X$ iff $X$ contains a nonempty perfect subset (a closed subset with no isolated points).
First, suppose $X$ has a nonempty perfect subset $A$. We may as well assume $X=A$ then (if Player I picks a point outside $A$, just pick $Xsetminus A$ as the open set), so that $X$ is perfect. Now note that if $Usubseteq X$ is open, then $U$ has no isolated points either and so $overline{U}$ is perfect as well. So, when Player I picks a point $x_1$, here's what Player II can do. Since $x_1$ is not isolated, there exists another point $yin X$. Since $X$ is Hausdorff, there are disjoint open sets $U,Vsubset X$ with $x_1in V$ and $yin U$. Player II then chooses $U_1=Xsetminus overline{U}$.
Now $A=overline{U}$ is again a nonempty perfect subset of $X$, and so we may again replace $X$ with this subset for subsequent turns. So, Player II can continue the game for any number of turns, ensuring that after every turn, there is still a nonempty perfect set which has not been covered by the open sets chosen so far. By compactness, the open sets cannot cover the whole space after infinitely many steps either, so Player II wins.
Conversely, suppose $X$ has no nonempty perfect subset. Recall that the Cantor-Bendixson derivative $X'$ of $X$ is the complement of the set of isolated points of $X$. We can then iterate this process transfinitely, defining $$X_0=X,$$ $$X_{alpha+1}=X_alpha',$$ and $$X_alpha=bigcap_{beta<alpha}X_beta$$ when $alpha$ is a limit ordinal. Each $X_alpha$ is a closed subset of $X$, and $X_{alpha+1}$ is always a proper subset of $X_alpha$ (unless $X_alpha$ is empty) since $X_alpha$ is not perfect. So, there must exist some ordinal $alpha$ such that $X_alpha=emptyset$. The least such $alpha$ will be a successor, and its predecessor $beta$ is called the Cantor-Bendixson rank of $X$.
We now prove that Player I has a winning strategy, by induction on the Cantor-Bendixson rank $beta$. Note that since $X_{beta+1}=emptyset$, $X_beta$ is a discrete space, which must be finite by compactness. So, Player I uses their first $|X_beta|$ turns to pick each of the points of $X_beta$. After those turns, let $Ysubset X$ be the subspace that has still not been covered by the open sets chosen. It is clear by induction that $Y_alphasubseteq X_alpha$ for all $alpha$, and so $Y_beta=emptyset$ since $Y$ contains no points of $X_beta$. Thus $Y$ has Cantor-Bendixson rank less than $beta$. So, by induction, Player I can win the game on $Y$. Since they have already covered all the points of $Xsetminus Y$, this is enough to win the game on $X$.
(In fact, we can relax the assumption that $X$ is compact Hausdorff a bit. For Player II to win by the first argument, we need only for $X$ to contain a nonempty closed compact Hausdorff subset with no isolated points. And for Player I to win by the second argument, we only need $X$ to be compact and contain no nonempty perfect subset.)
Neat question, and it has a neat answer for compact Hausdorff spaces. Namely, Player II can win in a compact Hausdorff space $X$ iff $X$ contains a nonempty perfect subset (a closed subset with no isolated points).
First, suppose $X$ has a nonempty perfect subset $A$. We may as well assume $X=A$ then (if Player I picks a point outside $A$, just pick $Xsetminus A$ as the open set), so that $X$ is perfect. Now note that if $Usubseteq X$ is open, then $U$ has no isolated points either and so $overline{U}$ is perfect as well. So, when Player I picks a point $x_1$, here's what Player II can do. Since $x_1$ is not isolated, there exists another point $yin X$. Since $X$ is Hausdorff, there are disjoint open sets $U,Vsubset X$ with $x_1in V$ and $yin U$. Player II then chooses $U_1=Xsetminus overline{U}$.
Now $A=overline{U}$ is again a nonempty perfect subset of $X$, and so we may again replace $X$ with this subset for subsequent turns. So, Player II can continue the game for any number of turns, ensuring that after every turn, there is still a nonempty perfect set which has not been covered by the open sets chosen so far. By compactness, the open sets cannot cover the whole space after infinitely many steps either, so Player II wins.
Conversely, suppose $X$ has no nonempty perfect subset. Recall that the Cantor-Bendixson derivative $X'$ of $X$ is the complement of the set of isolated points of $X$. We can then iterate this process transfinitely, defining $$X_0=X,$$ $$X_{alpha+1}=X_alpha',$$ and $$X_alpha=bigcap_{beta<alpha}X_beta$$ when $alpha$ is a limit ordinal. Each $X_alpha$ is a closed subset of $X$, and $X_{alpha+1}$ is always a proper subset of $X_alpha$ (unless $X_alpha$ is empty) since $X_alpha$ is not perfect. So, there must exist some ordinal $alpha$ such that $X_alpha=emptyset$. The least such $alpha$ will be a successor, and its predecessor $beta$ is called the Cantor-Bendixson rank of $X$.
We now prove that Player I has a winning strategy, by induction on the Cantor-Bendixson rank $beta$. Note that since $X_{beta+1}=emptyset$, $X_beta$ is a discrete space, which must be finite by compactness. So, Player I uses their first $|X_beta|$ turns to pick each of the points of $X_beta$. After those turns, let $Ysubset X$ be the subspace that has still not been covered by the open sets chosen. It is clear by induction that $Y_alphasubseteq X_alpha$ for all $alpha$, and so $Y_beta=emptyset$ since $Y$ contains no points of $X_beta$. Thus $Y$ has Cantor-Bendixson rank less than $beta$. So, by induction, Player I can win the game on $Y$. Since they have already covered all the points of $Xsetminus Y$, this is enough to win the game on $X$.
(In fact, we can relax the assumption that $X$ is compact Hausdorff a bit. For Player II to win by the first argument, we need only for $X$ to contain a nonempty closed compact Hausdorff subset with no isolated points. And for Player I to win by the second argument, we only need $X$ to be compact and contain no nonempty perfect subset.)
edited Dec 1 at 20:37
answered Dec 1 at 20:29
Eric Wofsey
177k12202328
177k12202328
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
2
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
add a comment |
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
2
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
Thank you this was awesome. Did you know this already? You've also shown that the game is determined for compact Hausdorff topologies.
– Anguepa
Dec 1 at 22:02
2
2
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
@Anguepa For compact spaces the game is determined for the reason you pointed out in the question, namely, open games are determined. If Player I has no winning strategy, then "keep it that way" is a winning strategy for Player II; i.e., Player II guarantees the win by never playing into a position where Player I has a winning strategy.
– bof
Dec 1 at 23:22
add a comment |
up vote
3
down vote
According to the Wikipedia article on topological games, your game is known as the point-open game. Wikipedia has no more information about this game, but refers to the paper Rastislav Telgârsky, Topological games: on the 50th anniversary of the Banach–Mazur game, Rocky Mountain J. Math. 17 (1987), 227–276, which has a lot of information about it.
add a comment |
up vote
3
down vote
According to the Wikipedia article on topological games, your game is known as the point-open game. Wikipedia has no more information about this game, but refers to the paper Rastislav Telgârsky, Topological games: on the 50th anniversary of the Banach–Mazur game, Rocky Mountain J. Math. 17 (1987), 227–276, which has a lot of information about it.
add a comment |
up vote
3
down vote
up vote
3
down vote
According to the Wikipedia article on topological games, your game is known as the point-open game. Wikipedia has no more information about this game, but refers to the paper Rastislav Telgârsky, Topological games: on the 50th anniversary of the Banach–Mazur game, Rocky Mountain J. Math. 17 (1987), 227–276, which has a lot of information about it.
According to the Wikipedia article on topological games, your game is known as the point-open game. Wikipedia has no more information about this game, but refers to the paper Rastislav Telgârsky, Topological games: on the 50th anniversary of the Banach–Mazur game, Rocky Mountain J. Math. 17 (1987), 227–276, which has a lot of information about it.
edited Dec 1 at 23:23
answered Dec 1 at 23:16
bof
49.8k457119
49.8k457119
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3021675%2fa-two-player-game-on-compact-topological-spaces%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
1
If $X$ is not compact, Player I may still have a winning strategy: consider the discrete topology on $mathbb{N}$. Player I just picks $n$ for each inning $n$. (If $X$ is not Lindelöf then Player II has a winning strategy: just play sets in an open cover without a countable subcover.)
– 1-3-7-Trimethylxanthine
Dec 1 at 19:17
@1-3-7-Trimethylxanthine you're right I'll change it to Lindelöf.
– Anguepa
Dec 1 at 19:25
The argument you used to show that Player II has a winning strategy if $X=[0,1]$ can be used to show, more generally, that Player II has a winning strategy if $Xsubseteqmathbb R$ does not have strong measure zero. Therefore, if Borel's conjecture holds, then Player II has a winning strategy for every uncountable set $Xsubseteqmathbb R$. (Borel's conjecture is the assertion that no uncountable subset of $mathbb R$ has strong measure zero; it has been shown by Richard Laver to be consistent.)
– bof
Dec 2 at 1:12
@bof sure, thank you, I edited.
– Anguepa
Dec 6 at 13:14