AFTD Auto-Formalizing Theoretical Domains

spider_blocked_none_one_inward_one_outward

theoremverified

For the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.

Statement

theorem spider_blocked_none_one_inward_one_outward (r : ℕ) (hr : 1 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    spider_gamma (r + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)] = r
Source
step towards spider_eventual_parity_two_three
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 18

The proof, explained

The theorem is proved by strong induction on the leg length r ≥ 1, generalizing over the non-free leg end φ. When r < 2, the assumption 1 ≤ r forces r = 1, which is solved by the base-case lemma spider_blocked_none_one_inward_one_outward_base. For r ≥ 2, the game value is expressed as the mex of raw move options, which simplifies via the induction hypothesis on legs of length r' < r to an options list whose mex evaluates directly to r.

  1. It suffices to prove the theorem for r assuming it holds for all strictly smaller leg lengths m < r and all non-free endpoints φ.

    We proceed by strong induction on r using Nat.strong_induction_on, generalizing over the endpoint φ so that the induction hypothesis applies to any non-free endpoint at smaller leg lengths.

    line 4

    uses Nat.strong_induction_on

      induction' r using Nat.strong_induction_on with r ih generalizing φ
  2. We split the proof into two cases: r ≥ 2 and r < 2.

    By le_or_gt applied to 2 and r, either 2 ≤ r or r < 2. The inductive reduction requires leg length at least 2, while r < 2 isolates the base case.

    line 5

    uses le_or_gt

      rcases le_or_gt 2 r with hr2 | hr2
  3. For r ≥ 2, the game value γ(r + 3, none, [(1, inward), (1, outward), (r, φ)]) equals r.

    We rewrite the game value as the mex of raw options via spider_blocked_none_one_inward_one_outward_raw_opts_eq. By spider_blocked_none_one_inward_one_outward_opts_eq, this raw mex equals the mex of the simplified options list, provided the induction hypothesis holds for all r' < r (which we supply from ih). Finally, spider_none_one_inward_one_outward_opts_mex evaluates this mex to r.

    lines 6–10

    uses spider_blocked_none_one_inward_one_outward_raw_opts_eq, spider_blocked_none_one_inward_one_outward_opts_eq, spider_none_one_inward_one_outward_opts_mex

      · rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq r hr2 φ hφ]
        rw [spider_blocked_none_one_inward_one_outward_opts_eq r hr2 φ hφ]
        · exact spider_none_one_inward_one_outward_opts_mex r hr2 φ hφ
        · intro r' hr' hr'1 φ' hφ'
          exact ih r' hr' hr'1 φ' hφ'
  4. For r < 2, the game value γ(r + 3, none, [(1, inward), (1, outward), (r, φ)]) equals r.

    From the hypotheses 1 ≤ r and r < 2, linear integer arithmetic determines that r = 1. Substituting r = 1 reduces the goal to γ(4, none, [(1, inward), (1, outward), (1, φ)]) = 1, which holds by the base-case lemma spider_blocked_none_one_inward_one_outward_base.

    lines 11–13

    uses spider_blocked_none_one_inward_one_outward_base

      · have hr1 : r = 1 := by omega
        subst hr1
        exact spider_blocked_none_one_inward_one_outward_base φ hφ
Nat.strong_induction_on
Principle of strong induction on natural numbers: to prove a property holds for all n, it suffices to prove it for n assuming it holds for all m < n.
le_or_gt
In any linearly ordered type, for any two elements a and b, either a ≤ b or b < a.
spider_blocked_none_one_inward_one_outward_raw_opts_eq
For r ≥ 2 and φ ≠ free, the game value of the configuration is the minimal excluded value (mex) of its raw move options.
spider_blocked_none_one_inward_one_outward_opts_eq
Assuming the theorem holds for all leg lengths r' < r, the mex of the raw options equals the mex of the simplified options list.
spider_none_one_inward_one_outward_opts_mex
For r ≥ 2 and φ ≠ free, the minimal excluded value (mex) of the simplified options list evaluates to r.
spider_blocked_none_one_inward_one_outward_base
Base case r = 1: the game value γ(4, none, [(1, inward), (1, outward), (1, φ)]) equals 1 for any non-free leg end φ.

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

/-- Blocked family of the configuration (n;{1^in,1^out}) (the paper's κ₁): the value at level r is r, for both far ends. -/theorem spider_blocked_none_one_inward_one_outward (r : ℕ) (hr : 1 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    spider_gamma (r + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)] = r := by  induction' r using Nat.strong_induction_on with r ih generalizing φ  rcases le_or_gt 2 r with hr2 | hr2  · rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq r hr2 φ hφ]    rw [spider_blocked_none_one_inward_one_outward_opts_eq r hr2 φ hφ]    · exact spider_none_one_inward_one_outward_opts_mex r hr2 φ hφ    · intro r' hr' hr'1 φ' hφ'      exact ih r' hr' hr'1 φ' hφ'  · have hr1 : r = 1 := by omega    subst hr1    exact spider_blocked_none_one_inward_one_outward_base φ hφ
See it in the graphDiscuss this resultChallenge it