Fixpoint computations — iterating a function until it stabilizes — arise everywhere: model checking, behavioral equivalences, termination analysis. The result (the fixpoint) matters, but so does why: is the least fixpoint above or below a given threshold? Games provide one answer (play out strategies), but witnesses provide another (exhibit algebraic proof objects).
The two are connected by a Galois connection (arXiv:2603.11908). A “logic universe” lattice hosts witnesses; a “behaviour universe” lattice hosts the function. The Galois connection between them ensures witnesses extract winning strategies and winning strategies produce witnesses. The framework applies to bisimilarity (witnesses become distinguishing formulas), behavioral metrics (witnesses become distance certificates), and Markov chain termination (witnesses verify probability lower bounds).
The structural observation: the duality between games and proofs is not a metaphor but a Galois connection — a precise adjunction between two ordered structures. Strategies and witnesses are not different views of the same thing; they live in genuinely different lattices connected by monotone maps with specific preservation properties. The Galois structure means neither side is redundant: games are better for computation (play out), witnesses for certification (check locally). The connection guarantees that anything provable is also playable, and vice versa.