How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Terminal reachability and residual positions
Statement
Assume ZFC. In a tree with terminal taboos, let be the set of positions from which has a strategy forcing a terminal taboo for the other player; infinite play is not a success. Then . For nonterminal , membership in is equivalent to some child belonging to when moves at , and to every child belonging to when the opponent moves. Winning reachability strategies can be fixed simultaneously for all positions in .
Facts & Assumptions
Taboo labels, legal strategies, and fixed-history games retain their original parity; see Game trees with terminal taboos.
Assume The Axiom of Choice.
Transfinite recursion includes recursion on the natural-number well-order with access to the preceding history.
Proof
Given: A set tree with a partition of its terminal nodes and a player ; write for the other player.
All strategies in all fixed-history subgames are subsets of a fixed set of position/move pairs. A1 selects legal default moves at all nonterminal positions, and a winning reachability strategy for each , from its nonempty set of such strategies. A terminal position belongs to exactly when its label is taboo for : the already finished play is the only maximal play.
At a nonterminal -position , the first move of chooses a child ; restricting the strategy beyond that move proves . Conversely if a child exists, choose that move and then follow , with defaults elsewhere. Every consistent maximal play then reaches a taboo. Thus the some-child equivalence holds.
At a nonterminal -position , the opponent may choose any child; restricting after each such choice shows every child belongs to . Conversely, if every child belongs to , after the opponent's first move to use the already selected . Each consistent play follows one fixed winning continuation and thus terminates at a taboo. This proves the every-child equivalence, without requiring a uniform time bound.
If , follow the two respective winning strategies from the fixed history . At each nonterminal stage the parity determines one prescribed legal move. Recursion F2, stopping at a terminal node if one occurs, yields a unique maximal play; if no terminal is reached, the union of its prefixes is an infinite branch. This play is consistent with both strategies, so each strategy forces it to terminate at a taboo for its opponent. A terminal cannot have both labels by F1. Hence the intersection is empty, and all assertions follow. QED.
Depends on
Used by
Dependency tree · two levels
9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Lemma 1, corrected local reachability argument (standard reference, not scraped)
- paragraph preceding Lemma 2.1.2, printed p64 (independent residual-game comparison) (standard reference, not scraped)