Misere combinatorial games.

Comparison modulo a set

We study when comparison of ambient forms modulo A is decided by the maintenance–proviso test (Promain.Test). A set is Promain when the test entirely characterises comparison. We split this into the two respective directions, since each can be meaningful on its own:

• Promain.Necessary, when comparison implies the test; and
• Promain.Sufficient, when the test implies comparison.

Strikingly, sufficiency needs only that A is Form.Hereditary. Necessity, however, is the more complicated of the two: it holds when A is Downlinking, a property guaranteed for dicotically closed sets containing a root, and in particular for every Universe.

Note that we are providing sufficient conditions for Promain.Necessary and Promain.Sufficient; it remains unclear what structure can be inferred about a set A that has either of these two properties.

The main result of this section is Promain.ofDicoticOfNonempty, which states that every nonempty, hereditary, dicotically closed set is promain.

References

• [A. N. Siegel, On the general dead-ending universe of partizan games (Section 5 on pp. 207–222)][siegel:GeneralDeadendingUniverse:2025]

The maintenance–proviso test

def MisereGames.Form.Promain.Test {G : Type (u + 1)} [Form G] (A : G → Prop) (g h : G) : Prop

The maintenance–proviso test for g and h modulo A, simply requiring both the maintenance and the proviso to be satisfied.

Equations

• One or more equations did not get rendered due to their size.

def MisereGames.Form.Promain {G : Type (u + 1)} [Form G] (IsAmbient A : G → Prop) : Prop

A set A is promain (within the ambient IsAmbient) when comparison of ambient forms modulo A is decided entirely by the maintenance–proviso test (i.e. by Test).

Equations

• MisereGames.Form.Promain IsAmbient A = ∀ ⦃g h : G⦄, IsAmbient g → IsAmbient h → (g ≥m A h ↔ MisereGames.Form.Promain.Test A g h)

def MisereGames.Form.Promain.Necessary {G : Type (u + 1)} [Form G] (IsAmbient A : G → Prop) : Prop

The necessary/'forward' direction of Promain, for when comparison forces the test.

Equations

• MisereGames.Form.Promain.Necessary IsAmbient A = ∀ ⦃g h : G⦄, IsAmbient g → IsAmbient h → g ≥m A h → MisereGames.Form.Promain.Test A g h

def MisereGames.Form.Promain.Sufficient {G : Type (u + 1)} [Form G] (IsAmbient A : G → Prop) : Prop

The sufficient/'backward' direction of Promain, for when the test forces comparison.

Equations

• MisereGames.Form.Promain.Sufficient IsAmbient A = ∀ ⦃g h : G⦄, IsAmbient g → IsAmbient h → MisereGames.Form.Promain.Test A g h → g ≥m A h

theorem MisereGames.Form.Promain.necessary {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} (hp : Promain IsAmbient A) : Necessary IsAmbient A

theorem MisereGames.Form.Promain.sufficient {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} (hp : Promain IsAmbient A) : Sufficient IsAmbient A

theorem MisereGames.Form.Promain.mk {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} (hn : Necessary IsAmbient A) (hs : Sufficient IsAmbient A) : Promain IsAmbient A

theorem MisereGames.Form.Promain.iff_necessary_and_sufficient {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} : Promain IsAmbient A ↔ Necessary IsAmbient A ∧ Sufficient IsAmbient A

Separating and downlinking sets

class MisereGames.Form.Separating {G : Type (u + 1)} [Form G] (IsAmbient A : G → Prop) : Prop

A set A is separating (within the ambient IsAmbient) when incomparable ambient forms are separated from both sides. This is essentially [Siegel, Lemma 5.8][siegel:GeneralDeadendingUniverse:2025] extracted into a property.

• separating_pair_of_not_misereGE {g h : G} : IsAmbient g → IsAmbient h → ¬g ≥m A h → AreLeftSeparating A g h ∧ AreRightSeparating A g h

  If g ≱ h modulo A, then g and h are both Left- and Right-separating.

class MisereGames.Form.Downlinking {G : Type (u + 1)} [Form G] (IsAmbient A : G → Prop) extends MisereGames.Form.Hereditary IsAmbient : Prop

A set A is downlinking (within the ambient IsAmbient) when we can conclude two ambient forms are downlinked in the following way: if no Left option of g is better than h, and g is better than no Right option of h, then g is downlinked to h. This is essentially an extraction of [Siegel, Lemma 5.10][siegel:GeneralDeadendingUniverse:2025]

This is currently the crux of proving a set is Promain.Necessary (see Promain.Necessary.of_downlinking).

• has_option {g g' : G} (h1 : IsAmbient g) (h2 : IsOption g' g) : IsAmbient g'
• downlinked_of_not_exists_moves_misereGE {g h : G} : IsAmbient g → IsAmbient h → (¬∃ gl ∈ moves Player.left g, gl ≥m A h) → (¬∃ hr ∈ moves Player.right h, g ≥m A hr) → Downlinked A g h

Currently, the auxiliary separating and downlinking forms used in our proofs are all grown dicotically from rooted adjoints with a fixed root, so they live in any dicotically closed A containing a root.

theorem MisereGames.Form.rootedAdjoint_mem_of_isAmbient {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} (h_root : A r) (h_sub : A ≤ IsAmbient) {g : G} (hg : IsAmbient g) : A (rootedAdjoint r g)

The rooted adjoint of an ambient form lies in any dicotically closed A containing the root r.

theorem MisereGames.Form.Downlinked.of_separating {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} (h_root : A r) (h_isRoot : Misere.Adjoint.IsRoot IsAmbient r) (h_sub : A ≤ IsAmbient) {g h : G} (hg : IsAmbient g) (hh : IsAmbient h) (h_left_sep : ∀ (gl : ↑(moves Player.left g)), AreLeftSeparating A (↑gl) h) (h_right_sep : ∀ (hr : ↑(moves Player.right h)), AreRightSeparating A g ↑hr) : Downlinked A g h

If every Left option of g is separated from h, and every Right option of h from g, then g is downlinked to h.

theorem MisereGames.Form.Separating.pair_of_not_misereGE {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} (h_root : A r) (h_isRoot : Misere.Adjoint.IsRoot IsAmbient r) (h_sub : A ≤ IsAmbient) {g h : G} (hg : IsAmbient g) (hh : IsAmbient h) (h_not_ge : ¬g ≥m A h) : AreLeftSeparating A g h ∧ AreRightSeparating A g h

If g ≱ h modulo A, then g and h are both Left- and Right-separating.

theorem MisereGames.Form.Separating.ofDicotic {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} (h_root : A r) (h_isRoot : Misere.Adjoint.IsRoot IsAmbient r) (h_sub : A ≤ IsAmbient) : Separating IsAmbient A

A dicotically closed A lying in the ambient space and containing a root r (see Form.Misere.Adjoint.IsRoot) is Separating (no further closure properties required!).

theorem MisereGames.Form.Separating.ofDicoticOfNonempty {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] [Hereditary A] (h_ne : ∃ (g : G), A g) (h_sub : A ≤ IsAmbient) : Separating IsAmbient A

A nonempty, hereditary, dicotically closed A lying in the ambient space is Separating. Note that this is strictly weaker than ofDicotic; it is mainly included for convenience.

theorem MisereGames.Form.Downlinking.ofDicoticSeparating {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} [Separating IsAmbient A] (h_root : A r) (h_isRoot : Misere.Adjoint.IsRoot IsAmbient r) (h_sub : A ≤ IsAmbient) : Downlinking IsAmbient A

A separating, dicotically closed A in the ambient space with a root is downlinking (Separating supplies what the downlink construction needs).

theorem MisereGames.Form.Downlinking.ofDicotic {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} (h_root : A r) (h_isRoot : Misere.Adjoint.IsRoot IsAmbient r) (h_sub : A ≤ IsAmbient) : Downlinking IsAmbient A

A dicotically closed A lying in the ambient space and containing a root r (see Form.Misere.Adjoint.IsRoot) is Downlinking (no further closure properties required!). Taking r = 0 recovers the usual case where A contains 0.

theorem MisereGames.Form.Downlinking.ofDicoticOfNonempty {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] [Hereditary A] (h_ne : ∃ (g : G), A g) (h_sub : A ≤ IsAmbient) : Downlinking IsAmbient A

A nonempty, hereditary, dicotically closed A lying in the ambient space is Downlinking. The zero-like form it must contain (Form.exists_isZeroLike) serves as the required root.

Necessity

theorem MisereGames.Form.not_downlinked_left_option_of_misereGE {G : Type (u + 1)} [Form G] {A : G → Prop} {g h hl : G} (hge : g ≥m A h) (hhl : hl ∈ moves Player.left h) : ¬Downlinked A g hl

Comparison forbids downlinking to options: if g ≥m A h, then g is not downlinked to any Left option of h.

theorem MisereGames.Form.not_downlinked_right_option_of_misereGE {G : Type (u + 1)} [Form G] {A : G → Prop} {g h gr : G} (hge : g ≥m A h) (hgr : gr ∈ moves Player.right g) : ¬Downlinked A gr h

Comparison forbids downlinking to options: if g ≥m A h, then no Right option of g is downlinked to h.

theorem MisereGames.Form.Promain.Necessary.of_downlinking {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Downlinking IsAmbient A] : Necessary IsAmbient A

If A is downlinking, then comparison forces the maintenance–proviso test; i.e. Test is necessary for comparison.

theorem MisereGames.Form.Promain.Necessary.ofDicotic {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] {r : G} (h_root : A r) (h_isRoot : Misere.Adjoint.IsRoot IsAmbient r) (h_sub : A ≤ IsAmbient) : Necessary IsAmbient A

A concrete sufficient condition for necessity: a dicotically closed set in the ambient space containing a root.

theorem MisereGames.Form.Promain.Necessary.ofDicoticOfNonempty {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] [Hereditary A] (h_ne : ∃ (g : G), A g) (h_sub : A ≤ IsAmbient) : Necessary IsAmbient A

A nonempty, hereditary, dicotically closed set in the ambient space has the necessity direction.

Sufficiency

theorem MisereGames.Form.Promain.Sufficient.of_hereditary {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Hereditary A] : Sufficient IsAmbient A

If A is hereditary, then the maintenance–proviso test (Test) is sufficient for comparison.

Comparison

theorem MisereGames.Form.Promain.of_downlinking_of_hereditary {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Downlinking IsAmbient A] [Hereditary A] : Promain IsAmbient A

If A is downlinking and hereditary, comparison modulo A is characterised by the maintenance–proviso test.

theorem MisereGames.Form.Promain.ofDicoticOfNonempty {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [ClosedUnderDicotic IsAmbient A] [Hereditary A] (h_ne : ∃ (g : G), A g) (h_sub : A ≤ IsAmbient) : Promain IsAmbient A

A nonempty, hereditary, dicotically closed set in the ambient space is promain.

instance MisereGames.Form.instSeparatingUniverse {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [Universe IsAmbient A] : Separating IsAmbient A

Every universe is separating.

instance MisereGames.Form.instDownlinkingUniverse {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [Universe IsAmbient A] : Downlinking IsAmbient A

Every universe is downlinking.

theorem MisereGames.Form.Promain.of_universe {G : Type (u + 1)} [Form G] {IsAmbient A : G → Prop} [Ambient IsAmbient] [Universe IsAmbient A] : Promain IsAmbient A

Comparison modulo a universe is characterised by the maintenance–proviso test (Test).

Maintenance under refinement

theorem MisereGames.Form.Maintenance.of_subset {G : Type (u + 1)} [Form G] {A B : G → Prop} (h_subset : ∀ (g : G), B g → A g) {g h : G} {p : Player} (h_maintenance : Maintenance A g h p) : Maintenance B g h p

If B is a subset of A, then any pair of games passing the A-maintenance necessarily also passes the B-maintenance.