AFTD Auto-Formalizing Theoretical Domains

op869_bounded_fuel_mono

theoremverified

Increasing the number of remaining moves preserves a winning position in the bounded online coloring adversary game.

Statement

theorem op869_bounded_fuel_mono {n : ℕ} (k t K D : ℕ) (fuel fuel' i : ℕ) (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ) (hle : fuel ≤ fuel') (h : op869_bounded_adversary_forces k t K D fuel i P C) : op869_bounded_adversary_forces k t K D fuel' i P C
Source
A monotonicity step in the finite online coloring game for arXiv:2610.41516, Section 2.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • op869_bounded_adversary_forcesThe bounded t-fold adversary game is the t-fold game where, after each move, every vertex has post-degree at most D.
  • op869_graph_from_predecessorsThe simple graph on the ordered vertices Fin n whose edge from an earlier vertex a to a later vertex b exists exactly when a is in the…
  • op869_predecessor_postdegreeThe post-degree of a vertex in an ordered predecessor presentation is the number of later vertices that list it as a predecessor.

The proof, explained

The theorem is proved by induction on fuel, generalizing over all other game parameters. The base case fuel = 0 is vacuous because the adversary cannot force a win with zero fuel by definition. In the inductive step with fuel + 1, the target fuel fuel' must also be non-zero (fuel' = fuel'' + 1 with fuel ≤ fuel''). The adversary chooses the same predecessor set S as in the original strategy; against any valid coloring chosen by the painter, either the adversary wins immediately by reaching K colors, or the induction hypothesis applies to the continuation game since fuel ≤ fuel''.

  1. The claim holds vacuously when the initial fuel is zero.

    We induct on fuel, generalizing over fuel', i, P, and C. When fuel = 0, the definition of op869_bounded_adversary_forces evaluates directly to False. The hypothesis h is therefore contradictory, closing the base case.

    lines 2–3

      induction fuel generalizing fuel' i P C with
      | zero => simp [op869_bounded_adversary_forces] at h
  2. In the inductive step, the target fuel fuel' must be strictly positive.

    In the step for fuel + 1, we consider the cases of fuel'. If fuel' = 0, the inequality fuel + 1 ≤ fuel' becomes fuel + 1 ≤ 0, which is impossible for natural numbers; linear arithmetic (omega) closes this branch.

    lines 4–6

      | succ fuel ih =>
        cases fuel' with
        | zero => omega
  3. When the vertex index is within bounds (i < n), the adversary can reuse the winning predecessor set S.

    Writing fuel' as fuel'' + 1, we case split on whether i < n. When i < n, rewriting with dif_pos unfolds the definition of op869_bounded_adversary_forces in both the hypothesis h and the goal. The hypothesis h yields a predecessor set S that satisfies the index condition, preserves k-colorability, and satisfies the post-degree bound D. We use this same S as the witness for fuel' + 1.

    lines 7–11

    uses dif_pos

        | succ fuel' =>
          by_cases hi : i < n
          · simp only [op869_bounded_adversary_forces, dif_pos hi] at h ⊢
            obtain ⟨S, hS, hcolor, hdegree, hnext⟩ := h
            refine ⟨S, hS, hcolor, hdegree, ?_⟩
  4. For any valid coloring response, the adversary either wins immediately or wins by the induction hypothesis.

    For any valid set c of t colors disjoint from the colors of S, the hypothesis provides two possibilities: either the total number of colors used reaches the threshold K, or the position remains winning at vertex i + 1 with fuel moves remaining. In the former case, the adversary wins immediately via Or.inl. In the latter case, since fuel + 1 ≤ fuel'' + 1 implies fuel ≤ fuel'' by linear arithmetic (omega), the induction hypothesis applies to show that the continuation is also winning with fuel'' moves, giving the second disjunct via Or.inr.

    lines 12–15

    uses Or.inl, Or.inr

            intro c hc hvalid
            rcases hnext c hc hvalid with hw | hrec
            · exact Or.inl hw
            · exact Or.inr (ih fuel' (i+1) _ _ (by omega) hrec)
  5. The case where the vertex index is out of bounds (i ≥ n) is contradictory.

    When i ≥ n, the definition of op869_bounded_adversary_forces evaluates to False in the else-branch of the conditional. Simplifying the hypothesis h with ¬(i < n) produces False, closing this branch.

    line 16

          · simp [op869_bounded_adversary_forces, hi] at h
dif_pos
If a proposition c holds, then the dependent conditional if c then t else e evaluates to the then-branch t.
Or.inl
Given a proof of A, constructs a proof of the disjunction A ∨ B.
Or.inr
Given a proof of B, constructs a proof of the disjunction A ∨ B.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem op869_bounded_fuel_mono {n : ℕ} (k t K D : ℕ) (fuel fuel' i : ℕ) (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ) (hle : fuel ≤ fuel') (h : op869_bounded_adversary_forces k t K D fuel i P C) : op869_bounded_adversary_forces k t K D fuel' i P C := by  induction fuel generalizing fuel' i P C with  | zero => simp [op869_bounded_adversary_forces] at h  | succ fuel ih =>    cases fuel' with    | zero => omega    | succ fuel' =>      by_cases hi : i < n      · simp only [op869_bounded_adversary_forces, dif_pos hi] at h ⊢        obtain ⟨S, hS, hcolor, hdegree, hnext⟩ := h        refine ⟨S, hS, hcolor, hdegree, ?_⟩        intro c hc hvalid        rcases hnext c hc hvalid with hw | hrec        · exact Or.inl hw        · exact Or.inr (ih fuel' (i+1) _ _ (by omega) hrec)      · simp [op869_bounded_adversary_forces, hi] at h
See it in the graphDiscuss this resultChallenge it