Hanf Numbers for Poset Games
Fabián Rivero Herrera · 2025
Read Hanf Numbers for Poset Games by Fabián Rivero Herrera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-07317.txt.
Introduction
Fabián Rivero Herrera studied in 2025 a take-away game played on ordered sets. In the game Chomp, two players nibble at a product of two orders, and the question is who can force a win. Answers swing sharply with the orders chosen, so Herrera limits the field to powers of one fixed order, stacked by rank.
A key fact shapes the hunt: if the second player fails to win somewhere in the tower, there is a cutoff rank after which the second player never wins again. Finding that cutoff for each base order is the paper's main goal. The cutoff plays the role of a Hanf number from logic.
Catalog record
| CREATOR | Fabián Rivero Herrera |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-07317
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hanf Numbers for Poset Games Fabián Rivero Herrera Abstract . Given two well partial orders ( P ; ≤ P ) (P;\leq_{P}) and ( T ; ≤ T ) (T;\leq_{T}) , each with a minimum element, we study the following question: which player has a winning strategy for Chomp on the poset ( P × T ; ≤ P × T ) (P\times T;\leq_{P\times T}) ? Here, ( P × T ; ≤ P × T ) (P\times T;\leq_{P\times T}) denotes the poset obtained as the Cartesian product of P P and T T , equipped with the corresponding lexicographic order. The answer to this very natural question depends strongly on the specific choice of ( P ; ≤ P ) (P;\leq_{P}) and ( T ; ≤ T ) (T;\leq_{T}) . For this reason, we restrict our attention to classes of posets given by powers of a fixed poset: { ( P σ ; ≤ P σ ) ∣ σ ∈ Ord } \{(P^{\sigma};\leq_{P^{\sigma}})\mid\sigma\in\mathrm{Ord}\} . A fundamental fact about these classes of structures is that, if the second player does not have a winning strategy for all the posets in { ( P σ ; ≤ P σ ) ∣ σ ∈ Ord } \{(P^{\sigma};\leq_{P^{\sigma}})\mid\sigma\in\mathrm{Ord}\} , there exists an ordinal ξ \xi such that the second player has a winning strategy on ( P ξ ; ≤ P ξ ) (P^{\xi};\leq_{P^{\xi}}) but not on ( P γ ; ≤ P γ ) (P^{\gamma};\leq_{P^{\gamma}}) for all γ ≥ ξ + 1 \gamma\geq\xi+1 . Determining the corresponding ordinal for this Hanf number-style property constitutes the main objective of this work. Inspired by results of García-Marco and Knauer, we focus on classes of posets with a purely algebraic definition. These posets arise from submonoids (with respect to the natural sum, or Hessenberg sum) of ordinals of the form ω σ \omega^{\sigma} and are generated by sets of ordinals. In the process, we provide a test to determine whether a finite set Γ \Gamma of ordinals indeed yields well partial orders, and, using set-theoretic techniques, we establish an upper bound for the ordinal ξ \xi : if Γ ⊂ ω \Gamma\subset\omega , then ξ < ω 1 \xi<\omega_{1} , and otherwise ξ < | ⋃ Γ | + \xi<|\bigcup\Gamma|^{+} . 1. Introduction In a poset game, two players take turns choosing elements from a partially ordered set and, on each turn, removing the chosen element and all those above it. The first player to run out of elements to choose loses. A particular case (and one of the most popular poset games) is the game Chomp : the poset is a rectangle of dimension n\times m where each element is smaller than all the elements above it and to its right; the first player to eliminate the minimum (the element at the bottom left) loses. We can also define this game on any poset with a global minimum and, of course, by removing it, we obtain a poset game with the rules we explained at the beginning. The history of this combinatorial game dates back to 1952, when the Dutch mathematician Frederik Schuh introduced the “game of divisors”. Quite some time later, David Gale described in [ Gal74 ] the Chomp game in the way just mentioned. A natural question one may ask is the following: given two posets (P;\leq_{P}) and (T;\leq_{T}) , each with a global minimum, what can we say about the Chomp game on the poset (P\times T;\leq_{P\times T}) ? Here, P\times T denotes the set of pairs (p,q) with p\in P and q\in T , and \leq_{P\times T} is the lexicographic order; that is, (p,q)\leq_{P\times T}(p^{\prime},q^{\prime}) iff p\leq_{P}p^{\prime} or p=p^{\prime} and q\leq_{T}q^{\prime} . More specifically, a similar question can be asked for successive powers (P^{n+1};\leq_{P^{n+1}}):=(P\times P^{n};\leq_{P\times P^{n}}) of (P;\leq_{P}) , with n\geq 1 . We will see that the answer to these questions depends heavily on the posets (P;\leq_{P}) and (T;\leq_{T}) that we choose. We will focus on addressing the second question and, in particular, we will work with a generalization of the Chomp game that was introduced in [ GMK18 ] . There, the Chomp game is studied on the posets given by numerical semigroups \mathcal{S}\subset\mathbb{N} with the order defined by a\leq_{\mathcal{S}}b iff b-a\in\mathcal{S} . This is a huge generalization of the original game, so that, as in the classic Chomp, there is no known constructive way to find winning strategies, except in particular cases. Specifically, we propose a generalization of the game studied in [ GMK18 ] to a set-theoretic context: as in \mathbb{N} , any additively indecomposable ordinal has a monoid structure on which we can define a partial order and, thus, play the Chomp game. In particular, we will focus on submonoids with natural sum (also called Hessenberg sum). The following sections will make clear that this family of submonoids is very interesting for our purposes. For example, we prove that it is possible to apply results from [ GMK18 ] to this context to obtain constructive winning strategies. Apart from that, we will see that the algebraic definition of these posets allows us to use purely set-theoretic techniques to draw some conclusions about the game. Since this paper may attract readers interested in game theory or set theory, the following section presents some very basic facts from both disciplines that will be necessary later. In the third section, we present some basic results about Chomp on (P\times T;\leq_{P\times T}) and study some order-theoretic properties of the well partial order generators; that is, sets of ordinals that generate monoids in which we can define a natural well partial order structure. For instance, we provide a very general test to determine whether a finite set of ordinals is a well partial order generator. In the final section, we will investigate classes of well partial orders \{(\mathcal{S}^{\tau};\leq_{\mathcal{S}^{\tau}})\mid\tau\geq\sigma\} generated by sets of ordinals \Gamma , where the sets \mathcal{S}^{\tau}\subseteq\omega^{\tau} are monoids under natural sum. In particular, if the second player does not have a winning strategy on all the posets of the corresponding class, then there exists a successor ordinal \xi+1 , which we denote by \text{ch}(\Gamma) , such that the second player has a winning strategy on (\mathcal{S}^{\alpha};\leq_{\mathcal{S}^{\alpha}}) , for \alpha\leq\xi , but not on (\mathcal{S}^{\gamma};\leq_{\mathcal{S}^{\gamma}}) for all \gamma\geq\xi+1 . Our main result states that, if \Gamma is finite, \text{ch}(\Gamma)<\omega_{1} if \Gamma\subset\omega and \textnormal{ch}(\Gamma)<|\bigcup\Gamma|^{+} otherwise. 2. Preliminaries 2.1. Game theory The game-theoretic concepts required in this work are fairly simple; however, for a reader not well acquainted with these topics, we shall briefly mention the tools that will be needed in what follows. From now on, we will refer to the first player as player A and the second player as player B . Theorem 2.1 (Zermelo’s theorem) . In any finite and impartial two-player game there exists a winning strategy for either A or B . Here, a finite game is a game in which any play of the game ends after a finite number of moves. In the case of games on partially ordered sets, we can ensure that the game is finite by requiring that there are no infinite antichains or infinite descending chains; that is, we shall work with well partial orders . Proposition