17
$\begingroup$

The Banach-Mazur game on a poset $\mathbb P$ is the $\omega$-length game where the players alternate choosing a descending sequence $a_0 \geq b_0 \geq a_1 \geq b_1 \geq \dots$. Player II wins when the sequence has a lower bound.

A strategy is a function $\sigma : \mathbb P^{<\omega} \to \mathbb P$ such that for each linearly ordered $\vec x \in \mathbb P^{<\omega}$, $\sigma(\vec x) \leq \min(\vec x)$.

A tactic is a descending function $\tau : \mathbb P \to \mathbb P$. (Meaning $\tau(p) \leq p$ for all $p$. Thanks to Joel for the better terminology.)

The Banach-Mazur game on $\mathbb P$ is $\omega$-strategically closed when there is a strategy $\sigma$ such that II wins whenever II plays according to $\sigma$, meaning if the sequence of plays so far is $\vec x$ and it is II’s turn, then II plays $\sigma(\vec x)$. The game is $\omega$-tactically-closed when II has a winning tactic, meaning II wins when they always play $\tau(a)$, where $a$ is the last move by I.

These notions have generalizations to games of length longer than $\omega$. The separation of tactical and strategic closure for games of uncountable length has been studied by Yoshinobu. The situation is different because the games involve limit stages. However, I don't know whether these notions have been separated for games of length $\omega$.

Question: Suppose $\mathbb P$ is $\omega$-strategically-closed. Is it $\omega$-tactically-closed?

$\endgroup$
15
  • $\begingroup$ Have you looked at the standard examples of strategically closed forcings? $\endgroup$
    – Asaf Karagila
    Dec 2, 2022 at 10:18
  • $\begingroup$ @AsafKaragila A bit. It is hard to find examples that are not just forcing-equivalent to countably closed. Jech and Shelah show that consistently such an example exists, but it is somewhat complicated and I don't know if it is tacitcally closed. A google search suggests that my question may be equivalent to a long-standing open problem in topology. $\endgroup$ Dec 2, 2022 at 12:41
  • 1
    $\begingroup$ Club shooting cannot be $\sigma$-closed, since it would imply it being proper and therefore SSP, and the whole point is to destroy the stationarity of a set. There is a classical theorem that it is $\sigma$-distributive, but I think you can also show that it is in fact strategically closed. $\endgroup$
    – Asaf Karagila
    Dec 2, 2022 at 13:29
  • 1
    $\begingroup$ A similar distinction appears in the Chocolatier's game, where the Glutton has a winning strategy, but no winning tactic. mathoverflow.net/questions/401151/… But I don't see immediately how to transform this to your setting, so I'm not sure whether this is helpful. $\endgroup$ Dec 2, 2022 at 13:36
  • 2
    $\begingroup$ @Joel: Interesting you say that. Every time I try to count the types of chocolate, there seem to be new ones. I can only conclude that there are uncountably many types, and therefore, you seem to be saying, gluttony is a bad way to experience chocolate... $\endgroup$
    – Asaf Karagila
    Dec 2, 2022 at 14:31

5 Answers 5

10
$\begingroup$

The answer to the topological version of Banach-Mazur games is negative, proved by Gabriel Debs in 1985:

The paper is in French, but here is the MathScinet review:

A Banach-Mazur game on a topological space is a two-person infinite game in which a move of each player is to choose an open set contained in that previously picked by the opponent. The first player wins if the resulting descending sequence of open sets has empty intersection. Otherwise the second player wins. It is proved that if the second player has a winning strategy depending on the entire sequence of previous moves of both players then [they also have] a winning strategy depending on the last two moves played ([their] own last move and [their] opponent's). This was independently discovered by F. Galvin and R. Telgarskybut the author proves it for a more general class of games. The second result is the construction of a completely regular space on which the second player has a winning strategy depending on the last two moves of the opponent but does not have a winning strategy depending only on the opponent's last move.

Reviewed by Andrzej Pelc

As Will Brian mentions in the comments, however, this does not quite settle the partial order version of the question.

$\endgroup$
12
  • 1
    $\begingroup$ If someone could post an answer explaining the construction, I'd be grateful. $\endgroup$ Dec 2, 2022 at 15:30
  • 4
    $\begingroup$ Hi Joel, unfortunately, I don't think Debs' example answers Monroe's question. The problem is that the Banach-Mazur game on a topological space is not generally equivalent to the Banach-Mazur game on the poset consisting of its nonempty open sets. The problem is that in the topological version, II wins if there is a point contained in every set that's been played. In the poset version, II wins if there is a member of the poset included in every set that's been played. These are different conditions. Debs' space answers the topological-Banach-Mazur version of this question . . . (continued) $\endgroup$
    – Will Brian
    Dec 2, 2022 at 20:29
  • 4
    $\begingroup$ . . . but it does not answer the poset version. In fact, one of Debs' spaces (there are two -- one that's Hausdorff but non-regular, and a much more complicated one that is $T_{3 \frac{1}{2}}$) refines a metric space, and this means that player I can play in such a way that the sequence of moves is guaranteed to contain at most one point in the end, and therefore not contain a nonempty open set. $\endgroup$
    – Will Brian
    Dec 2, 2022 at 20:31
  • 2
    $\begingroup$ @WillBrian Thanks for the explanation. So I will leave the question open for more answers. $\endgroup$ Dec 2, 2022 at 22:28
  • 1
    $\begingroup$ @bof Set theorists use the term “Banach–Mazur game” for the poset game as I defined it. Maybe it is unjustified. $\endgroup$ Dec 3, 2022 at 6:59
7
$\begingroup$

For a partial answer, let me prove that every strategically closed partial order admits a nearly tactical winning strategy, one that depends only on the previous two moves, that is, on the previous move of each player. (On first move, it uses only player I's initial move.) In the comments, it is pointed out that the nearly tactical strategies are also known as coding strategies.

Theorem. Every strategically closed partial order $\newcommand\P{\mathbb{P}}\P$ admits a nearly tactical winning strategy for player two, one that depends only on the two previous moves, one move for each player.

Proof. Assume $\P$ is a strategically closed partial order, with winning strategy $\sigma$ for player II.

For simplicity let me assume initially that every lower cone $p\downarrow=\{q\in\P\mid q\leq p\}$ in $\P$ has the same cardinality as $\P$. In this special case the lower cones are also equinumerous with the finite tuples from $\P$, and so we may attach labels to every condition $p$ with a finite sequence $p^{\to}=(p_0,\ldots,p_n)$, and furthermore, we may do this in such a way that every finite sequence occurs densely often as a label.

Let me now describe the nearly tactical strategy $\tau$. If the previous two moves were $p>q$, then we consider the label $p^{\to}$, and if this is a finite sequence that corresponds to having played the game as I am now describing, then we interpret $q$ as player I's move in that game, compute the response $r$ of $\sigma$ to that play, and then extend $r$ to a chosen condition $r^+$ whose label codes the sequence $p^{\to},q$.

The point is that player II's moves will in effect code the playing history, and this is enough information to get by with nearly tactical strategy, since from the previous move of player II, we will be able to recover the entire play. That is, the next move of player I will be some $q^+$ below $r^+$, and player II will now be looking at $r^+,q^+$, from which he can compute $p^{\to},q$ and thus reconstruct the play according to $\sigma$.

This nearly tactical strategy is therefore a winning strategy, because at the start of the game, we can ensure that the very first play by II starts the coding sequence properly to indicate that, and then at each subsequent play, it will build on that encoding, and so the tactical play will correspond to a play according to $\sigma$, and so it will have a lower bound.

Note that although we had player II extend $\sigma$'s play from $r$ to $r^+$, in order to code the right play, nevertheless in the simulated $\sigma$ game, we can pretend player II played only $r$, and that player I had extended $r^+$ to the response $q^+$. That is, whenever one has a winning strategy, then it is also winning to play any stronger move than the winning strategy, since the extension can be absorbed into player I's next play.

Now finally let me explain how to handle the general case, without the homogeneous cardinality assumption on the lower cones of $\P$. Consider any strategically closed partial order $\P$. I claim that there is a dense suborder $\newcommand\Q{\mathbb{Q}}\Q$ in $\P$, such that every lower cone $q\downarrow$ in $\Q$ is at least as large as the corresponding upper cone $q\uparrow$. (We allow that these lower cones may have different cardinalities themselves.) To see this, consider first the dense suborder of conditions $p\in\P$ such that the lower cone $p\downarrow$ has a minimal cardinality — it cannot be made smaller by refining $p$. This is dense, since below any condition we may find one whose cone has smallest cardinality. Next, take a maximal antichain in that dense set, and let $\Q$ be the conditions in the dense set below a condition in that antichain. It follows that every downset in $\Q$ has size at least as large as the corresponding upset in $\Q$, since that upset is contained in the downset of the corresponding element of the antichain.

Notice next that every dense suborder of a strategically closed order is also strategically closed, as player II can pretend that all moves occur in the suborder, simply by strengthening all moves of either player so as to be in the dense set, but otherwise following the original strategy. So $\Q$ is strategically closed. But now, since every lower cone $p\downarrow$ in $\Q$ is at least as large as the up set $q\uparrow$, we can label the nodes below $q$ with finite sequences from the upset, such that every descending play to $q$ occurs densely often below $q$. This is enough to implement the nearly tactical strategy above. And so every strategically closed partial order admits a nearly tactical winning strategy. $\Box$

This answer amounts to the partial-order analogue of the Debs result I mentioned in my other answer, which he proved for the topological Banach-Mazur games. I am unsure whether his argument is like mine or not, since I haven't yet been able to read his paper.

$\endgroup$
5
  • 2
    $\begingroup$ As an aid in searching, it may be helpful to know that your "nearly tactical" strategies are also called "coding strategies" as in jstor.org/stable/2275110 $\endgroup$
    – bof
    Dec 4, 2022 at 21:35
  • $\begingroup$ Thank you, bof, this is helpful. But although it may be good to know this terminology for finding articles, I think I prefer my terminology as more apt. A strategy is tactical if it depends only on the previous move, and nearly tactical if it depends on the previous two moves. Note that one can consider tactical and nearly tactical strategies without the moves necessarily coding anything at all. $\endgroup$ Dec 4, 2022 at 23:15
  • 2
    $\begingroup$ On the other hand the term "$k$-tactic" has been used for a strategy which relies on the opponent's last $k$ moves, and that seems a more natural notion. In general, it seems that a strategy is best thought of as a function of the opponent's moves. It may not be a necessary feature, but in practice "nearly tactical" strategies seem to use one's move to encode information about the history of the play. $\endgroup$
    – bof
    Dec 5, 2022 at 2:43
  • $\begingroup$ I agree with that. $\endgroup$ Dec 5, 2022 at 2:45
  • 1
    $\begingroup$ Yes, I think the terminology "coding strategy" is quite standard as I'm not sure I've ever seen a proof that turned perfect information into "nearly tactical" information without an encoding of the game's history. $\endgroup$ Dec 5, 2022 at 2:49
6
$\begingroup$

Here is another partial answer.

Theorem. Suppose Player II has a winning strategy $\sigma$ in the Banach–Mazur game on a poset $P$. If there is a subset $D\subseteq P$ such that
(1) $\forall p\in P\ \exists d\in D\ d\le p$ and
(2) $\forall p\in P\ |\{d\in D:d\ge p\}|\le\aleph_0$,
then Player II has a winning tactic.

Proof. Suppose $p\in P$; I have to define $\tau(p)\le p$.

Let $S_p$ be the set of all partial $\sigma$-plays $u_1\ge v_1\ge\cdots\ge u_k\ge v_k\ge p$ ($k\in\omega$) (so that it is Player I's turn to move, and anything $\le p$ is a legal next move) with all $u_i\in D$. Note that $S_p$ is countable; fix an enumeration $S_p=\{s_{p,n}:n\in\omega\}$. Construct an infinite sequence $$p\ge d_0\ge x_0\ge y_0\ge d_1\ge x_1\ge y_1\ge\cdots\ge d_n\ge x_n\ge y_n\ge\cdots$$ satisfying the conditions:
(i) $d_n\in D$;
(ii) $s_{p,n}$ followed by $d_n$ and $x_n$ is a partial $\sigma$-play;
(iii) $y_n=\sigma(x_0,x_1,\dots,x_n)$.

Since the sequence $x_0,y_0,x_1,y_1,\dots,x_n,y_n,\dots$ is a $\sigma$-play, it is bounded below; choose a lower bound and call it $\tau(p)$.

Now any $\tau$-play is interlaced with a $\sigma$-play and therefore bounded below, i.e., $\tau$ is a winning tactic.

$\endgroup$
1
  • 1
    $\begingroup$ Ah, you beat me to it---I just awoke this morning prepared to post nearly this same argument! Very nice. $\endgroup$ Dec 5, 2022 at 12:18
5
$\begingroup$

This post is an addition to the argument posted by bof last night. In bof's post, it is proved that posets having a special kind of dense subset cannot provide a counterexample for Monroe's question. It turns out that exactly this property of posets has been studied before, as it is relevant to similar questions arising from the topological version of the Banach-Mazur game. Furthermore, a large class of posets are known to have this property assuming CH. So, combined with bof's anwer, this significantly narrows the search for the kind of poset Monroe has asked about.

Let's say that a poset $P$ has property bof if there is a dense $D \subseteq P$ with "countable upper cones", by which we mean that $\{ d \in D : p \leq d\}$ is countable for every $p \in P$.

Let's say that a poset $P$ has the descending ccc if for every $X \subseteq P$ there is some countable $Y \subseteq X$ such that $X$ and $Y$ both have the exact same set of lower bounds in $P$. Note that every ccc poset has the descending ccc. However, there are many other posets that have this property as well. (For example, the poset $[A]^\omega$ of countable subsets of some set $A$, when ordered by inclusion, has the descending ccc. Also, the poset of subsets of Baire space $\omega^\omega$ that are homeomorphic to the Cantor space, when ordered by inclusion, has the descending ccc. Both these examples are far from being ccc.)

Theorem: Suppose $P$ is a separative poset with the descending ccc. $(1)$ If $|P| < \aleph_2$, then $P$ has property bof. Assuming the Continuum Hypothesis: $(2)$ If $|P| < \aleph_\omega$ then $P$ has property bof. $(3)$ More generally, if $\square_\kappa$ holds for every singular $\kappa \leq |P|$, then $P$ has property bof.

The argument for $(1)$ is fairly straightforward: enumerate $P = \{p_\alpha :\, \alpha < \omega_1\}$, then define $D$ to be all the $p \in P$ such that no extension of $p$ appears before $p$ in this enumeration. The other two parts of the theorem (as well as part (1)) can be found in the following paper:

Brian, Will; Dow, Alan; Milovich, David; Yengulalp, Lynne, Telgársky’s conjecture may fail, Israel Journal of Mathematics 242 (2021), pp. 325-358. ZBL07370902.

In this paper, we look at a conjecture of Telgarsky concerning the topological Banach-Mazur game. Generalizing the terminology of Monroe's question, let's say that a 1-tactic is a strategy for II that depends only on the previous move of I. But more generally, a $k$-tactic is a strategy for II that depends only on the previous $k$ moves of I.

As mentioned in a post by Joel, Debs described a space $X$ in which II has a winning $2$-tactic, but no winning tactic, in the topological Banach-Mazur game on $X$. Shortly after this discovery of Debs', Telgarsky conjectured that for every $k$, there is a space $X_k$ for which II has a winning $k$-tactic but no winning $(k+1)$-tactic. Notice that, by taking the disjoint union of all the $X_k$, this gives a space in which II has a winning strategy but no winning $k$-tactic for any $k$. Roughly, the conjecture is that there should be "complicated" spaces in which II can win the game, but not with any simple strategy.

Our paper shows that this conjecture is false under the assumption of GCH+$\square_\kappa$ for every singular $\kappa$. The main combinatorial principle is one that we denote $\nabla$:

$\nabla$ is the assertion that for every separative poset $P$ with the descending $\kappa$-cc, there is a dense $D \subseteq P$ such that every upper cone of $D$ has size $<\!\kappa$.

Note that property bof is simply $\nabla$ restricted to ccc ($=\, \aleph_1$-cc) posets. The reason this principle resolves Telgarsky's conjecture is essentially the argument that Joel gives in his second post about this question. If $\nabla$ holds, then II is able to code up the history of the game into each consecutive pair of I's moves, and thereby convert an arbitrary winning strategy into a winning $2$-tactic.

Let me point out that, unfortunately, the assumption of CH in this theorem cannot be removed. If $\mathfrak{b} > \aleph_1$, then the Hechler poset fails to satisfy $\nabla$. The assumption of $\square$ at limits is also necessary: it is consistent (relative to large cardinals) that the poset $([\omega_\omega]^\omega,\subseteq)$ fails to satisfy $\nabla$. (This is sometimes referred to as having no sparse cofinal family in $\omega_\omega$.)

It is interesting to me that the same principle used to resolve this conjecture for the topological Banach-Mazur game seems so relevant to Monroe's question for the poset Banach-Mazur game.

$\endgroup$
0
1
$\begingroup$

Edit: leaving this up just in case (and for the comments), but I'm pessimistic that the idea is recoverable - see discussion below.

As JDH observed, there are topological spaces $X$ for which Player II has a winning strategy (and in fact a winning 2-tactic), but no winning tactic in the topological Banach-Mazur game. So we proceed by attempting to find a poset that mimicks the topological game.

Naively one might let choose $\mathcal T_X\setminus\{\emptyset\}$. But as observed by Will Brian, this isn't quite right: in the topological game, P2 doesn't win by finding an open set below all chosen sets; they win if these sets have non-empty (not necessarily open) intersection.

Another attempt might be to "add in" a minimal point at the bottom of a chain of open sets with non-empty but empty-interior intersection to mimic this win condition for P2. But then P2 would just pick this new valid move immediately and end the game.

So instead, for each such chain in $\mathcal T_X\setminus\{\emptyset\}$, take each open set $U$ that contains the non-empty intersection, and insert a copy of $\mathcal T_U\setminus\{\emptyset\}$ below the chain. Rinse and repeat for these copies (taking only open subsets of the top $U$ for the copy), $\omega_1$ times. At the limits, the same thing is happening: any descending chain still corresponds to a bunch of open sets, so if their intersection is nonempty, add appropriate copies.

I think it's clear that if the players agree to play within the top $\mathcal T_X\setminus\{\emptyset\}$, the result is the same as the topological game. So we should argue that each player can enforce equivalent play to show strategies in the topological game translate here.

To see this, note that given however many moves of the opponent they're allowed to see, a player with a winning topological strategy/tactic can obtain an open set $U$ and choose the top element of a copy of $\mathcal T_U\setminus\{\emptyset\}$. (If they couldn't, then all infinite descending chains have empty intersection and the game is already set for P1.) The opponent then has to choose a subset of $U$ for the rest of the game.

So the winning player has ensured the game descends down our poset copies countably-far, and both players are essentially picking open subsets of each other. Let $\alpha<\omega_1$ be the least limit ordinal below this descent. If the open subsets have empty intersection, we didn't insert anything below that chain; otherwise, we did. This preserves the winning strategy/tactic for whichever player had one.

It remains to be shown that winning strategies in the poset game produce winning strategies in the topological game. Given a winninng strategy for either player in the poset game, note that it must handle the situation where the opponent always chooses the top of a lower copy of $\mathcal T_U$ for each move. This enforces the winning strategy to essentially choose subsets of the opponent at each step. Then this can be translated down to the topological game. If the poset game resulted in no lower bound, it's because the intersection of open sets was empty; otherwise it's because the intersection of open sets was non-empty.

$\endgroup$
6
  • $\begingroup$ There's an error at the limit stage of my construction: there's no immediate successor to restrict the open sets to, so there's no way to force the opponent to pick subsets. So I think just sticking $\mathcal T_X\setminus \{\emptyset\}$ at each stage may work, but the rest of the argument needs to adjust for a "cheater" who doesn't choose subsets. $\endgroup$ Dec 5, 2022 at 5:18
  • $\begingroup$ I wonder whether the construction will fall prey to the argument of bof's answer? Namely, if Deb's space has the property that one can find a basis for the topology with only countably many basis elements in every upper cone, then there will be a winning tactic in the poset game. Your limit construction idea would seem to preserve that property. $\endgroup$ Dec 5, 2022 at 13:11
  • $\begingroup$ @JoelDavidHamkins: Debs' space does indeed have bof's property. This is essentially how he proves that II has a winning $2$-tactic in the BM game. $\endgroup$
    – Will Brian
    Dec 5, 2022 at 14:02
  • $\begingroup$ Steven, what if you use the poset on $\omega_1 \times (X \cup \mathcal T_X^{\neq \emptyset})$ where $(\alpha,U) \leq (\beta,V)$ if and only if $\alpha > \beta$ and $U \subseteq V$, and $(\alpha,x) \leq (\beta,V)$ if and only if $\alpha > \beta$ and $x \in V$, and $(\alpha,x) \leq (\beta,y)$ if and only if $\alpha > \beta$ and $x=y$? $\endgroup$
    – Will Brian
    Dec 5, 2022 at 14:04
  • $\begingroup$ @Will on that poset as P2 I would immediately pick some $(\alpha,x)$ in the initial round. Then the set below me is a copy of $\omega_1$ and I believe I win regardless of the space. $\endgroup$ Dec 5, 2022 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.