wild_valid_replacement_from_three
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.
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$.
classical by_contra hnoneEvery 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.
uses
Or.inl,Ne.symmhave 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⟩
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$.
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)))
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$.
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)))
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.
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)
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`).
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$.
- The pigeonhole principle for three candidates and two failure modes is resolved by enumerating all cases and applying propositional tautology checking (`tauto`), rather than using a general cardinality lemma.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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