AFTD Auto-Formalizing Theoretical Domains

wild_normalized_array_vertex_witness_card

theoremverified

Let A be a symmetric idempotent row-injective array on Fin n. For any fixed vertex a, exactly3*(n-1) ORDERED pairs (x,y), x!=y, have a in {x,y,A(x,y)}. These split into the two endpoint roles and the output role. This is an incidence identity, not a partition or seal-avoidance theorem.

Statement

theorem wild_normalized_array_vertex_witness_card
    (n : ℕ) (A : Fin n → Fin n → Fin n)
    (hid : ∀ a, A a a = a)
    (hsym : ∀ a b, A a b = A b a)
    (hinj : ∀ a, Function.Injective (A a))
    (a : Fin n) :
    (univ.filter fun p : Fin n × Fin n =>
      p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card =
      3 * (n-1)
Source
IN-359 / OP-306 helper for the uniform weighted-moment route. The associated threefold triple system is standard: Compatible factorizations and three-fold triple systems (2006), construction in the proof of Theorem4.1, https://citeseerx.ist.psu.edu/document?doi=58cc9f2b7c3862f0964a05e0ac1529b9c9de8e5e&repid=rep1&type=pdf (bibliographic record https://repo.uum.edu.my/id/eprint/3494/). The graph motivation is https://arxiv.org/html/2610.22142v1, Section3.3 and the open conjecture in Section6. Incidence square sums and three-element inclusion-exclusion are ordinary finite counting. No novelty, wild-number bound, sharpness case, or research advance is claimed. Exact finite audit8955 is diagnostic, not a hypothesis.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof counts the ordered pairs (x, y) with x ≠ y such that a ∈ {x, y, A(x,y)} by partitioning them into three sets according to the role of vertex a: first endpoint (a = x), second endpoint (a = y), and array output (a = A(x,y)). Using idempotency, symmetry, and row injectivity, the auxiliary lemma hout shows that off-diagonal entries never match their row or column indices, ensuring that the three sets are mutually disjoint. Each of the three sets is then shown to be in bijection with the deleted universe Fin n \ {a} (with the output set relying on the fact that injective maps on finite sets are surjective), so each set has size n - 1. Summing the cardinalities of the three disjoint sets yields 3 * (n - 1).

  1. For any distinct x ≠ y, the array entry A(x,y) differs from both x and y.

    We activate classical reasoning and prove the auxiliary fact hout: if x ≠ y, then A(x,y) ≠ x and A(x,y) ≠ y. If A(x,y) = x, then since A(x,x) = x by idempotency (hid), row injectivity of A(x, ·) forces y = x, a contradiction. Similarly, if A(x,y) = y, symmetry (hsym) gives A(y,x) = y = A(y,y), and row injectivity of A(y, ·) forces x = y, another contradiction.

    lines 13–21

      classical
      have hout (x y : Fin n) (hxy : x ≠ y) : A x y ≠ x ∧ A x y ≠ y := by
        constructor
        · intro h
          have heq : A x y = A x x := h.trans (hid x).symm
          exact hxy ((hinj x) heq).symm
        · intro h
          have heq : A y x = A y y := (hsym y x).trans (h.trans (hid y).symm)
          exact hxy ((hinj y) heq)
  2. Define the three sub-collections X, Y, and Z according to the role of vertex a.

    We partition the candidate witness pairs into three sets: X consists of off-diagonal pairs (x,y) where a is the first coordinate (a = x), Y consists of off-diagonal pairs where a is the second coordinate (a = y), and Z consists of off-diagonal pairs where a is the array value (a = A(x,y)).

    lines 22–24

      let X : Finset (Fin n × Fin n) := univ.filter fun p => p.1 ≠ p.2 ∧ a = p.1
      let Y : Finset (Fin n × Fin n) := univ.filter fun p => p.1 ≠ p.2 ∧ a = p.2
      let Z : Finset (Fin n × Fin n) := univ.filter fun p => p.1 ≠ p.2 ∧ a = A p.1 p.2
  3. The set X has cardinality n - 1.

    We establish a bijection between X and the deleted universe univ.erase a via the second projection (x,y) ↦ y. For any (x,y) ∈ X, x = a and x ≠ y, so y ≠ a. The map is injective because the first coordinate is fixed to a, and surjective because for every y ≠ a, the pair (a,y) lies in X. The cardinality of univ.erase a is n - 1.

    lines 25–38

    uses card_bij, mem_univ, Prod.ext, Ne.symm

      have hX : X.card = n-1 := by
        have h : X.card = (univ.erase a).card := by
          apply card_bij (fun p _ => p.2)
          · intro p hp
            have hp := (mem_filter.mp hp).2
            exact mem_erase.mpr ⟨fun h => hp.1 (hp.2.symm.trans h.symm), mem_univ _⟩
          · intro p hp q hq he
            have hp := (mem_filter.mp hp).2
            have hq := (mem_filter.mp hq).2
            exact Prod.ext (hp.2.symm.trans hq.2) he
          · intro y hy
            refine ⟨(a,y), ?_, rfl⟩
            exact mem_filter.mpr ⟨mem_univ _, Ne.symm (mem_erase.mp hy).1, rfl⟩
        simpa using h
  4. The set Y has cardinality n - 1.

    Symmetrically, the first projection (x,y) ↦ x gives a bijection between Y and univ.erase a. For any (x,y) ∈ Y, y = a and x ≠ y, so x ≠ a. The map is injective because the second coordinate is fixed to a, and surjective because for any x ≠ a, the pair (x,a) lies in Y. Hence |Y| = n - 1.

    lines 39–52

    uses card_bij, mem_univ, Prod.ext

      have hY : Y.card = n-1 := by
        have h : Y.card = (univ.erase a).card := by
          apply card_bij (fun p _ => p.1)
          · intro p hp
            have hp := (mem_filter.mp hp).2
            exact mem_erase.mpr ⟨fun h => hp.1 (h.trans hp.2), mem_univ _⟩
          · intro p hp q hq he
            have hp := (mem_filter.mp hp).2
            have hq := (mem_filter.mp hq).2
            exact Prod.ext he (hp.2.symm.trans hq.2)
          · intro x hx
            refine ⟨(x,a), ?_, rfl⟩
            exact mem_filter.mpr ⟨mem_univ _, (mem_erase.mp hx).1, rfl⟩
        simpa using h
  5. The set Z has cardinality n - 1.

    We construct a bijection between Z and univ.erase a via the first projection (x,y) ↦ x. For any (x,y) ∈ Z, we have a = A(x,y) with x ≠ y; by hout, A(x,y) ≠ x, so x ≠ a. The map is injective because if (x,y) and (x,y') both produce a, injectivity of A(x, ·) forces y = y'. For surjectivity, given x ≠ a, injectivity of A(x, ·) on the finite domain Fin n implies surjectivity (Finite.surjective_of_injective), giving some y with A(x,y) = a; moreover x ≠ y because otherwise a = A(x,x) = x by idempotency, contradicting x ≠ a. Thus (x,y) ∈ Z maps to x.

    lines 53–74

    uses card_bij, mem_univ, Prod.ext, congrArg, Finite.surjective_of_injective

      have hZ : Z.card = n-1 := by
        have h : Z.card = (univ.erase a).card := by
          apply card_bij (fun p _ => p.1)
          · intro p hp
            have hp := (mem_filter.mp hp).2
            exact mem_erase.mpr ⟨fun h => (hout p.1 p.2 hp.1).1 (hp.2.symm.trans h.symm),
              mem_univ _⟩
          · intro p hp q hq he
            have hp := (mem_filter.mp hp).2
            have hq := (mem_filter.mp hq).2
            apply Prod.ext he
            apply hinj p.1
            exact hp.2.symm.trans (hq.2.trans (congrArg (fun x => A x q.2) he.symm))
          · intro x hx
            obtain ⟨y, hy⟩ := (Finite.surjective_of_injective (hinj x)) a
            have hxy : x ≠ y := by
              intro h
              subst y
              rw [hid] at hy
              exact (mem_erase.mp hx).1 hy
            exact ⟨(x,y), mem_filter.mpr ⟨mem_univ _, hxy, hy.symm⟩, rfl⟩
        simpa using h
  6. The sets X, Y, and Z are pairwise disjoint.

    We verify all three intersections are empty. If a pair were in X ∩ Y, then p.1 = a = p.2, contradicting p.1 ≠ p.2. If a pair were in X ∩ Z, then p.1 = a = A(p.1, p.2), contradicting hout. If a pair were in Y ∩ Z, then p.2 = a = A(p.1, p.2), again contradicting hout.

    lines 75–92

      have hXY : Disjoint X Y := by
        apply disjoint_left.mpr
        intro p hp hq
        have hp := (mem_filter.mp hp).2
        have hq := (mem_filter.mp hq).2
        exact hp.1 (hp.2.symm.trans hq.2)
      have hXZ : Disjoint X Z := by
        apply disjoint_left.mpr
        intro p hp hq
        have hp := (mem_filter.mp hp).2
        have hq := (mem_filter.mp hq).2
        exact (hout p.1 p.2 hp.1).1 (hq.2.symm.trans hp.2)
      have hYZ : Disjoint Y Z := by
        apply disjoint_left.mpr
        intro p hp hq
        have hp := (mem_filter.mp hp).2
        have hq := (mem_filter.mp hq).2
        exact (hout p.1 p.2 hp.1).2 (hq.2.symm.trans hp.2)
  7. The set of witness pairs is the union X ∪ Y ∪ Z.

    An off-diagonal pair p has a ∈ {p.1, p.2, A(p.1, p.2)} if and only if a = p.1, a = p.2, or a = A(p.1, p.2). By set extensionality and propositional logic, the filter definition matches the union X ∪ Y ∪ Z.

    lines 93–98

    uses mem_filter, mem_univ, true_and, mem_union, mem_insert, mem_singleton

      have heq : (univ.filter fun p : Fin n × Fin n =>
          p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))) = X ∪ Y ∪ Z := by
        ext p
        simp only [X, Y, Z, mem_filter, mem_univ, true_and, mem_union,
          mem_insert, mem_singleton]
        tauto
  8. The total number of witness pairs is 3 * (n - 1).

    Rewriting with the set equality and using disjointness of the sets via card_union_of_disjoint, the cardinality of X ∪ Y ∪ Z is |X| + |Y| + |Z| = (n - 1) + (n - 1) + (n - 1). Linear arithmetic (omega) simplifies this sum to 3 * (n - 1).

    lines 99–101

    uses card_union_of_disjoint

      rw [heq, card_union_of_disjoint (disjoint_union_left.mpr ⟨hXZ,hYZ⟩),
        card_union_of_disjoint hXY, hX, hY, hZ]
      omega
card_bij
If a map between two finite sets is well-defined, injective, and surjective, then the two sets have the same cardinality.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
congrArg
Applying a function to equal arguments produces equal results: if a = b, then f(a) = f(b).
Finite.surjective_of_injective
An injective self-map on a finite type is surjective (the pigeonhole principle).
mem_filter
An element belongs to the filter of a finite set by a predicate if and only if it belongs to the set and satisfies the predicate.
mem_insert
An element belongs to the set insert b s if and only if it equals b or belongs to s.
mem_singleton
An element belongs to the singleton set {a} if and only if it is equal to a.
mem_union
An element belongs to the union of two sets if and only if it belongs to at least one of them.
mem_univ
Every element of a finite type belongs to its universal set.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Prod.ext
Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
true_and
The conjunction True ∧ p is equivalent to p.

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

open Finsetset_option maxHeartbeats 4000000theorem wild_normalized_array_vertex_witness_card    (n : ℕ) (A : Fin n → Fin n → Fin n)    (hid : ∀ a, A a a = a)    (hsym : ∀ a b, A a b = A b a)    (hinj : ∀ a, Function.Injective (A a))    (a : Fin n) :    (univ.filter fun p : Fin n × Fin n =>      p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card =      3 * (n-1) := by  classical  have hout (x y : Fin n) (hxy : x ≠ y) : A x y ≠ x ∧ A x y ≠ y := by    constructor    · intro h      have heq : A x y = A x x := h.trans (hid x).symm      exact hxy ((hinj x) heq).symm    · intro h      have heq : A y x = A y y := (hsym y x).trans (h.trans (hid y).symm)      exact hxy ((hinj y) heq)  let X : Finset (Fin n × Fin n) := univ.filter fun p => p.1 ≠ p.2 ∧ a = p.1  let Y : Finset (Fin n × Fin n) := univ.filter fun p => p.1 ≠ p.2 ∧ a = p.2  let Z : Finset (Fin n × Fin n) := univ.filter fun p => p.1 ≠ p.2 ∧ a = A p.1 p.2  have hX : X.card = n-1 := by    have h : X.card = (univ.erase a).card := by      apply card_bij (fun p _ => p.2)      · intro p hp        have hp := (mem_filter.mp hp).2        exact mem_erase.mpr ⟨fun h => hp.1 (hp.2.symm.trans h.symm), mem_univ _⟩      · intro p hp q hq he        have hp := (mem_filter.mp hp).2        have hq := (mem_filter.mp hq).2        exact Prod.ext (hp.2.symm.trans hq.2) he      · intro y hy        refine ⟨(a,y), ?_, rfl⟩        exact mem_filter.mpr ⟨mem_univ _, Ne.symm (mem_erase.mp hy).1, rfl⟩    simpa using h  have hY : Y.card = n-1 := by    have h : Y.card = (univ.erase a).card := by      apply card_bij (fun p _ => p.1)      · intro p hp        have hp := (mem_filter.mp hp).2        exact mem_erase.mpr ⟨fun h => hp.1 (h.trans hp.2), mem_univ _⟩      · intro p hp q hq he        have hp := (mem_filter.mp hp).2        have hq := (mem_filter.mp hq).2        exact Prod.ext he (hp.2.symm.trans hq.2)      · intro x hx        refine ⟨(x,a), ?_, rfl⟩        exact mem_filter.mpr ⟨mem_univ _, (mem_erase.mp hx).1, rfl⟩    simpa using h  have hZ : Z.card = n-1 := by    have h : Z.card = (univ.erase a).card := by      apply card_bij (fun p _ => p.1)      · intro p hp        have hp := (mem_filter.mp hp).2        exact mem_erase.mpr ⟨fun h => (hout p.1 p.2 hp.1).1 (hp.2.symm.trans h.symm),          mem_univ _⟩      · intro p hp q hq he        have hp := (mem_filter.mp hp).2        have hq := (mem_filter.mp hq).2        apply Prod.ext he        apply hinj p.1        exact hp.2.symm.trans (hq.2.trans (congrArg (fun x => A x q.2) he.symm))      · intro x hx        obtain ⟨y, hy⟩ := (Finite.surjective_of_injective (hinj x)) a        have hxy : x ≠ y := by          intro h          subst y          rw [hid] at hy          exact (mem_erase.mp hx).1 hy        exact ⟨(x,y), mem_filter.mpr ⟨mem_univ _, hxy, hy.symm⟩, rfl⟩    simpa using h  have hXY : Disjoint X Y := by    apply disjoint_left.mpr    intro p hp hq    have hp := (mem_filter.mp hp).2    have hq := (mem_filter.mp hq).2    exact hp.1 (hp.2.symm.trans hq.2)  have hXZ : Disjoint X Z := by    apply disjoint_left.mpr    intro p hp hq    have hp := (mem_filter.mp hp).2    have hq := (mem_filter.mp hq).2    exact (hout p.1 p.2 hp.1).1 (hq.2.symm.trans hp.2)  have hYZ : Disjoint Y Z := by    apply disjoint_left.mpr    intro p hp hq    have hp := (mem_filter.mp hp).2    have hq := (mem_filter.mp hq).2    exact (hout p.1 p.2 hp.1).2 (hq.2.symm.trans hp.2)  have heq : (univ.filter fun p : Fin n × Fin n =>      p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))) = X ∪ Y ∪ Z := by    ext p    simp only [X, Y, Z, mem_filter, mem_univ, true_and, mem_union,      mem_insert, mem_singleton]    tauto  rw [heq, card_union_of_disjoint (disjoint_union_left.mpr ⟨hXZ,hYZ⟩),    card_union_of_disjoint hXY, hX, hY, hZ]  omega
See it in the graphDiscuss this resultChallenge it