REVIEW 4 minor 6 references
A game-theoretic proof of Shelah's theorem on labeled trees
T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proves Shelah's theorem on labeled trees by translating 'no homomorphism' into a winning strategy in a closed game.
desk verdict A sound, elegantly written new proof of a known theorem; the only real weakness is a sketched induction that deserves expansion. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the game $G(T,U)$, in which player I builds a branch in $T$ and player II must build the corresponding branch in $U$ with the same labels at every finite stage; player II wins exactly when a label-preserving tree homomorphism exists (Lemma 2.2). The proof's second mechanism is the triangular combination of several player-I winning strategies: for each increasing sequence $\langle\alpha_0,\dots,\alpha_n\rangle$, the strategies $\Sigma_{\alpha_i\alpha_{i+1}}$ are fed each other's outputs, and the resulting top row labels define a coloring $f:[\kappa]^{<\omega}\to\lambda$; the partition relation supplies an infinite homogeneous set whose shift-invariance property makes the induction in Claim 3.1 go through.
What would settle it
Take a concrete family of $\lambda$-labeled trees and run the Section 3 construction for a finite increasing tuple of length 4: write out the $3\times3$ and $4\times4$ move arrays from the winning strategies $\Sigma_{\alpha_i\alpha_{i+1}}$, and check whether equality of the two $f$-values on overlapping intervals forces every dashed label-matching rule in the fourth triangle. Any $n\ge3$ where this local check fails would break Claim 3.1 and point to the missing general case; no such example should exist if the proof is sound.
Extended reading notes
Core claim
The paper's central claim is Theorem 1.1: if $\kappa\to(\omega)^{<\omega}_\lambda$ holds, then for every sequence $\langle T_\alpha:\alpha<\kappa\rangle$ of $\lambda$-labeled trees there are $\alpha<\beta<\kappa$ with a homomorphism $T_\alpha\to T_\beta$. The new content is that this can be proved by translating the absence of a homomorphism into the existence of a winning strategy for player I in the game $G(T_\alpha,T_\beta)$, invoking closed-game determinacy (Gale\textendash{}Stewart) rather than better-quasi-ordering theory, and then deriving a contradiction by playing all the strategies against one another in a triangular array indexed by finite increasing sequences from $\kappa$. Homogeneity of the coloring produced by this array gives a shift-invariance condition that forces every finite interval of the homogeneous set to be good, and the infinite play thereby obtained makes player II win each game, contradicting the chosen strategies.
Load-bearing premise
The proof depends on the standard fact that closed infinite games are determined, so the failure of a homomorphism can be converted into a winning strategy for player I; it also relies on the unstated generalization of the triangular diagram chase from $n=3$ to all $n$, flagged in the proof by 'The general case is similar.'
Editorial extensions
If this is right
- For any $\lambda$-labeled tree family indexed by a cardinal $\kappa$ with $\kappa\to(\omega)^{<\omega}_\lambda$, a homomorphism between two trees is guaranteed; no additional structural assumption on the trees is needed.
- In the case $\lambda=1$, the theorem reduces to the familiar fact that among infinitely many unlabeled trees one embeds into another, and the paper notes its game proof covers this case without appealing to tree ranks.
- The game characterization makes the existence of a homomorphism absolute between transitive models of ZFC, since closed games are absolutely determined; the paper records this consequence as a remark.
- The proof needs only closed determinacy, whereas previous proofs used better-quasi-ordering theory, so the theorem is shown to follow from a more basic Ramsey-theoretic property of $\kappa$.
Reading between the lines
- The same triangular strategy-combination might be reusable for other embeddability theorems that are normally proved by better-quasi-ordering arguments, such as variants for trees with additional structure or for finitely many labels; the paper does not explore this.
- Because the proof needs only closed determinacy, it is plausible that the argument formalizes in weak set theories, and for countable trees in second-order arithmetic, which would strengthen the case that the theorem does not secretly depend on the full theory of better-quasi-orderings; this is an extension, not a paper claim.
- One could test the reach of the method by replacing $\kappa\to(\omega)^{<\omega}_\lambda$ with weaker or modified partition relations and checking whether the strategy-combination still forces a homomorphism; the paper does not state such bounds.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents a new proof of Shelah's theorem on labeled trees: assuming the partition relation κ → (ω)^{<ω}_λ, every κ-sequence of λ-labeled trees contains two trees T_α, T_β (α<β) with a homomorphism T_α → T_β. The proof introduces a game G(T,U) in which player II builds a partial homomorphism by matching labels; Lemma 2.2 states that player II has a winning strategy exactly when a homomorphism exists. Lemma 2.4, via Gale-Stewart determinacy, turns the non-existence of homomorphisms into a family of winning strategies for player I in each pair T_α, T_β. Assuming no homomorphism exists, the author plays these strategies against each other to form triangular arrays of moves for each finite increasing sequence of ordinals, and uses the array to define a coloring f of [κ]^{<ω}. The partition relation yields an infinite homogeneous set H; homogeneity gives a shift-invariance equation (1). Claim 3.1 proves by induction that every finite interval in H is 'good' (all rules followed). Passing to the infinite limit then produces, for every adjacent pair in H, an infinite play in which player II follows all rules, contradicting that player I had a winning strategy. The paper is self-contained apart from standard Gale-Stewart determinacy.
Significance. The result is not new—Shelah's theorem is known—but the proof is. Its principal strengths are the clean game-theoretic reformulation, the avoidance of Nash-Williams' better-quasi-order theory, and the use of only ZFC plus the classical Gale-Stewart theorem for closed games. The strategy-combination argument (Figures 1 and 2) is elegant and gives a concrete mechanism through which the partition relation produces a homomorphism. If the proof is accepted, it will make Shelah's theorem accessible to a broader audience and may be adaptable to other Ramsey-type statements. The manuscript is well written and the mathematical claims are clearly stated; the proof appears sound. The minor presentation issues listed below do not affect correctness.
minor comments (4)
- [Section 3, Claim 3.1] The induction step is only shown for i=0, n=3, with the sentence 'The general case is similar.' Since this claim is the heart of the proof, please expand the general case explicitly, or at least state the precise induction hypothesis and the configuration of the sub-triangles for arbitrary i and n. As written, the reader must reconstruct the diagram chase for arbitrary shifts.
- [Section 3, notation] The symbols x^i_j are used in the figures but never defined in the text. Please add a sentence defining x^i_j as the j-th move of player I in the game G(T_{α_i},T_{α_{i+1}}), or the appropriate convention, and clarifying how the triangular array is generated recursively.
- [Abstract] The abstract contains a typo ('eve ry family').
- [Footnote 2] The claim that the shift-invariance version is easily proved equivalent to Silver's weak partition relation κ^w → (ω)^{<ω}_λ would benefit from a reference or a one-line proof sketch, since the equivalence is not immediate.
Circularity Check
No significant circularity: the proof derives Shelah's theorem from the partition relation and Gale–Stewart determinacy without assuming its own conclusion.
full rationale
The derivation chain is self-contained. The paper assumes the partition relation κ → (ω)^{<ω}_λ and, toward a contradiction, the nonexistence of any homomorphism Tα→Tβ. By Lemma 2.2, existence of a homomorphism is equivalent to player II having a winning strategy in G(T,U); by Gale–Stewart determinacy (Lemma 2.4) the nonexistence assumption yields winning strategies Σ_{αβ} for player I. The strategies are then combined to define a coloring f:[κ]^{<ω}→λ, and homogeneity of an infinite H gives the shift-invariance equation (1). Claim 3.1 shows by induction that every finite interval in H is good, with the n=3 case drawn in Figure 1 and the general case stated as similar; the key step is that the shift-invariance equation supplies exactly the missing label-matching condition for the copied dashed-arrow move. The infinite play in Figure 2 then forces player II to win against each Σ_{α_i α_{i+1}}, contradicting that these are winning strategies for player I. No step reuses Theorem 1.1 as an input, no fitted parameter is renamed as a prediction, and no load-bearing conclusion is imported from a self-citation. The citations to Shelah and Eklof–Shelah are for the theorem's provenance, not for the proof; the cited Herden work is background. The only external ingredient, Gale–Stewart determinacy of closed games, is a standard ZFC theorem independent of the target result. The sketched general induction in Claim 3.1 is a brevity issue rather than circularity: the stated induction hypothesis and shift-invariance condition propagate to arbitrary intervals by the same diagram chase. Hence there is no circularity.
Assumptions & free parameters
assumptions (2)
- standard math Gale-Stewart theorem: every closed game of length ω is determined
- standard math Cardinals are ordinals, so 0 is an element of λ for nonzero λ
Cite this review
Pith. "Pith review of A game-theoretic proof of Shelah's theorem on labeled trees." pith.science (2026). https://pith.science/paper/NRW4R4TJ
@misc{pith2026190802442,
author = {Pith},
title = {Pith review of: A game-theoretic proof of Shelah's theorem on labeled trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/NRW4R4TJ}},
note = {Machine review of arXiv:1908.02442}
}
abstract
We give a new proof of a theorem of Shelah which states that for every family of labeled trees, if the cardinality $\kappa$ of the family is much larger (in the sense of large cardinals) than the cardinality $\lambda$ of the set of labels, more precisely if the partition relation $\kappa \to (\omega)^{\mathord{<}\omega}_\lambda$ holds, then there is a homomorphism from one labeled tree in the family to another. Our proof uses a characterization of such homomorphisms in terms of games.
Figures
Reference graph
Works this paper leans on
-
[1]
Paul C. Eklof and Saharon Shelah. Absolutely rigid systems and ab solutely indecomposable groups. In Abelian groups and modules , pages 257–268. Springer, 1999
work page 1999
-
[2]
Daniel Herden. Upper cardinal bounds for absolute structure s. In Groups and Model Theory: In Honor of R¨ udiger G¨ obel’s 70th Birthday, May 30–June 3, 2011, Conference Center “Die Wolfsburg,” M¨ ulheim an Der Ruhr, Germany , volume 576, page 137. American Mathematical Soc., 2012
work page 2011
-
[3]
Alexander S. Kechris and Yiannis N. Moschovakis. Notes on the th eory of scales. In Cabal Seminar 76–77 , pages 1–53. Springer, 1978
work page 1978
-
[4]
Yiannis N. Moschovakis. Descriptive set theory . Number 155. American Mathematical Soc., 2009
work page 2009
-
[5]
Better quasi-orders for uncountable cardina ls
Saharon Shelah. Better quasi-orders for uncountable cardina ls. Israel Journal of Mathematics , 42(3):177– 226, 1982
work page 1982
-
[6]
Jack H. Silver. A large cardinal in the constructible universe. Fund. Math, 69:93–100, 1970. Department of Mathematics, Miami University, Oxford, Ohio 45056, USA E-mail address : twilson@miamioh.edu 5
work page 1970
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.