AFTD Auto-Formalizing Theoretical Domains

wild_valid_replacement_from_three

theoremverified

Given a bad pair witness A(x,y)=z, three distinct candidate replacements all different from z cannot all fail the validity inequalities, provided the rows at x and y are injective. This is a local reservoir lemma, not a claim about connectivity.

Statement

theorem wild_valid_replacement_from_three {C : Type*} (A : C → C → C)
    (x y z : C) (hx : Function.Injective (A x)) (hy : Function.Injective (A y))
    (w : Fin 3 → C) (hw : Function.Injective w) (hbad : A x y=z)
    (hout : ∀ i,w i≠z) :
    ∃ i : Fin 3,A x y≠w i ∧ A x (w i)≠y ∧ A y (w i)≠x
Source
IN-342 supporting steps for OP-306, arXiv:2610.22142 Sections3.3.2/6. The target remains prescribed-coloring sharpness; these are local validity and conditioning-family helpers, not a seal-free partition theorem or new wild-number bound. No research advance is claimed.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • wild_valid_triple_exists_in_sixFor any array with injective rows and any six distinct vertices, there are three distinct indices satisfying all three triple-validity…

The proof, explained

The theorem is proved by contradiction via the pigeonhole principle. Since every candidate replacement $w_i$ is distinct from $z = A(x, y)$, failing the validity conditions forces each of the three candidates to satisfy either $A(x, w_i) = y$ or $A(y, w_i) = x$. However, the injectivity of the row maps $A(x, \cdot)$ and $A(y, \cdot)$ alongside the injectivity of $w$ guarantees that each of these two equations can hold for at most one candidate. Having three candidates distributed across two pigeonholes that can each hold at most one element produces an immediate propositional contradiction.

  1. Assume for contradiction that no candidate index satisfies all three validity conditions.

    We enable classical reasoning and assume the negation of the existential conclusion: that for all indices $i \in \{0, 1, 2\}$, candidate $w_i$ fails at least one of the three validity inequalities $A(x, y) \neq w_i$, $A(x, w_i) \neq y$, or $A(y, w_i) \neq x$.

    lines 8–9

      classical
      by_contra hnone
  2. Every candidate $w_i$ must satisfy $A(x, w_i) = y$ or $A(y, w_i) = x$.

    For any $i$, we are given $A(x, y) = z$ and $w_i \neq z$, so by symmetry of inequality, $A(x, y) \neq w_i$ always holds. Therefore, if neither $A(x, w_i) = y$ nor $A(y, w_i) = x$ were true, candidate $w_i$ would satisfy all three validity inequalities, which directly contradicts the assumption that no valid candidate exists.

    lines 10–16

    uses Or.inl, Ne.symm

      have h (i : Fin 3) : A x (w i)=y ∨ A y (w i)=x := by
        by_cases hi : A x (w i)=y
        · exact Or.inl hi
        · right
          by_contra hj
          apply hnone
          exact ⟨i,by rw [hbad]; exact Ne.symm (hout i),hi,hj⟩
  3. At most one index $i$ can satisfy $A(x, w_i) = y$.

    If two distinct indices $i \neq j$ both satisfied $A(x, w_i) = y$ and $A(x, w_j) = y$, transitivity of equality would imply $A(x, w_i) = A(x, w_j)$. By the injectivity of the row map $A(x, \cdot)$, this gives $w_i = w_j$, and by the injectivity of the candidate sequence $w$, this implies $i = j$, contradicting $i \neq j$.

    lines 17–19

      have hX (i j : Fin 3) (hij : i≠j) : ¬ (A x (w i)=y ∧ A x (w j)=y) := by
        rintro ⟨hi,hj⟩
        exact hij (hw (hx (hi.trans hj.symm)))
  4. At most one index $i$ can satisfy $A(y, w_i) = x$.

    Symmetrically, if $i \neq j$ both satisfied $A(y, w_i) = x$ and $A(y, w_j) = x$, injectivity of $A(y, \cdot)$ would imply $w_i = w_j$, and injectivity of $w$ would imply $i = j$, again contradicting $i \neq j$.

    lines 20–22

      have hY (i j : Fin 3) (hij : i≠j) : ¬ (A y (w i)=x ∧ A y (w j)=x) := by
        rintro ⟨hi,hj⟩
        exact hij (hw (hy (hi.trans hj.symm)))
  5. Instantiate these conditions for all three candidates and all pairs of distinct indices.

    We specialize the disjunction to each of the indices $0, 1, 2$, yielding that each candidate must satisfy at least one of the two equations. We also instantiate the exclusivity lemmas for each pair of distinct indices $(0, 1)$, $(0, 2)$, and $(1, 2)$, where the inequality of distinct indices is discharged by decision procedure.

    lines 23–31

      have h0 := h 0
      have h1 := h 1
      have h2 := h 2
      have hX01 := hX 0 1 (by decide)
      have hX02 := hX 0 2 (by decide)
      have hX12 := hX 1 2 (by decide)
      have hY01 := hY 0 1 (by decide)
      have hY02 := hY 0 2 (by decide)
      have hY12 := hY 1 2 (by decide)
  6. A contradiction is reached by propositional logic.

    Each of the 3 candidates must fall into at least one of 2 classes ($A(x, w_i) = y$ or $A(y, w_i) = x$), but no two distinct candidates can belong to the same class. Propositional tautology reasoning (`tauto`) determines that this system of constraints is unsatisfiable, deriving a contradiction (`False`).

    line 32

      tauto
Or.inl
From a proof of $a$, derives the disjunction $a \lor b$.
Ne.symm
Symmetry of inequality: if $a \neq b$, then $b \neq a$.

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

set_option maxHeartbeats 4000000theorem wild_valid_replacement_from_three {C : Type*} (A : C → C → C)    (x y z : C) (hx : Function.Injective (A x)) (hy : Function.Injective (A y))    (w : Fin 3 → C) (hw : Function.Injective w) (hbad : A x y=z)    (hout : ∀ i,w i≠z) :    ∃ i : Fin 3,A x y≠w i ∧ A x (w i)≠y ∧ A y (w i)≠x := by  classical  by_contra hnone  have h (i : Fin 3) : A x (w i)=y ∨ A y (w i)=x := by    by_cases hi : A x (w i)=y    · exact Or.inl hi    · right      by_contra hj      apply hnone      exact ⟨i,by rw [hbad]; exact Ne.symm (hout i),hi,hj⟩  have hX (i j : Fin 3) (hij : i≠j) : ¬ (A x (w i)=y ∧ A x (w j)=y) := by    rintro ⟨hi,hj⟩    exact hij (hw (hx (hi.trans hj.symm)))  have hY (i j : Fin 3) (hij : i≠j) : ¬ (A y (w i)=x ∧ A y (w j)=x) := by    rintro ⟨hi,hj⟩    exact hij (hw (hy (hi.trans hj.symm)))  have h0 := h 0  have h1 := h 1  have h2 := h 2  have hX01 := hX 0 1 (by decide)  have hX02 := hX 0 2 (by decide)  have hX12 := hX 1 2 (by decide)  have hY01 := hY 0 1 (by decide)  have hY02 := hY 0 2 (by decide)  have hY12 := hY 1 2 (by decide)  tauto
See it in the graphDiscuss this resultChallenge it