AFTD Auto-Formalizing Theoretical Domains

wild_normalized_array_pair_witness_card

theoremverified

Let A be a symmetric idempotent row-injective array on Fin n. For any two distinct vertices a,b, exactly six ORDERED pairs (x,y), x!=y, have both a and b in the witness support {x,y,A(x,y)}. Opposite orientations are counted separately; this is pair multiplicity three for the unordered witness multiset. Outputs lie in the full Fin n universe.

Statement

theorem wild_normalized_array_pair_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 b : Fin n) (hab : a ≠ b) :
    (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)) ∧
        b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card = 6
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 proceeds by explicitly characterizing the set of all ordered pairs (x, y) with x ≠ y whose support {x, y, A(x, y)} contains both a and b, and then computing its cardinality. Because each row map A(x, -) is an injective endofunction on the finite set Fin n, it is surjective, yielding unique elements u and v such that A(a, u) = b and A(b, v) = a. Idempotence, symmetry, and row-injectivity guarantee that u and v are distinct from each other and from a and b, and a case analysis demonstrates that (x, y) must be one of exactly six pairs: (a, b), (b, a), (a, u), (u, a), (b, v), or (v, b). Finally, because all six pairs are distinct, the cardinality of this set is 6.

  1. There exist vertices u and v such that A(a, u) = b and A(b, v) = a.

    Because `Fin n` is a finite set and each row function `A(x, -)` is assumed injective (`hinj`), every row function is also surjective by `Finite.surjective_of_injective`. Applying surjectivity of `A(a, -)` to `b` yields a witness `u` with `A(a, u) = b`, and applying surjectivity of `A(b, -)` to `a` yields a witness `v` with `A(b, v) = a`.

    lines 13–15

    uses Finite.surjective_of_injective

      classical
      obtain ⟨u, hu⟩ := (Finite.surjective_of_injective (hinj a)) b
      obtain ⟨v, hv⟩ := (Finite.surjective_of_injective (hinj b)) a
  2. The witnesses u and v are distinct from both a and b, and satisfy A(u, a) = b and A(v, b) = a.

    If `u = a`, then by idempotence (`hid`), `b = A(a, u) = A(a, a) = a`, contradicting `a ≠ b`; thus `u ≠ a`. If `u = b`, then symmetry and idempotence give `A(b, a) = A(a, b) = A(a, u) = b = A(b, b)`, so injectivity of `A(b, -)` forces `a = b`, again a contradiction; thus `u ≠ b`. Interchanging the roles of `a` and `b` gives `v ≠ b` and `v ≠ a`. Finally, symmetry of `A` (`hsym`) implies `A(u, a) = A(a, u) = b` and `A(v, b) = A(b, v) = a`.

    lines 16–37

      have hua : u ≠ a := by
        intro h
        subst u
        rw [hid] at hu
        exact hab hu
      have hub : u ≠ b := by
        intro h
        subst u
        have h : A b a = A b b := by rw [← hsym, hu, hid]
        exact hab ((hinj b) h)
      have hvb : v ≠ b := by
        intro h
        subst v
        rw [hid] at hv
        exact hab hv.symm
      have hva : v ≠ a := by
        intro h
        subst v
        have h : A a b = A a a := by rw [hsym, hv, hid]
        exact hab ((hinj a) h).symm
      have hua' : A u a = b := by rw [hsym, hu]
      have hvb' : A v b = a := by rw [hsym, hv]
  3. The set of pairs (x, y) with x ≠ y whose witness support {x, y, A(x, y)} contains both a and b is precisely {(a, b), (b, a), (a, u), (u, a), (b, v), (v, b)}.

    By set extensionality, we establish both set inclusions. In the forward direction, assume `x ≠ y` and `{a, b} ⊆ {x, y, A(x, y)}`. We case split on which element of the support equals `a` and which equals `b`: if `a = x`, then `b ≠ x` (since `a ≠ b`), so either `b = y` yielding `(a, b)`, or `b = A(a, y)` which by injectivity of `A(a, -)` forces `y = u`, giving `(a, u)`. If `a = y`, symmetrically we obtain `(b, a)` or `(u, a)`. If `a = A(x, y)`, then either `b = x`, which by injectivity of `A(b, -)` forces `y = v` giving `(b, v)`; or `b = y`, giving `(v, b)`; while `b = A(x, y)` implies `a = b`, ruled out by `False.elim`. In the reverse direction, each of the six candidate pairs is checked directly: each pair has distinct components and contains both `a` and `b` in its witness support via the established identities for `u` and `v`.

    lines 38–80

    uses mem_filter, mem_univ, true_and, mem_insert, mem_singleton, False.elim, Prod.mk.injEq, Ne.symm

      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)) ∧
            b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))) =
          {(a,b),(b,a),(a,u),(u,a),(b,v),(v,b)} := by
        ext p
        rcases p with ⟨x,y⟩
        simp only [mem_filter, mem_univ, true_and]
        constructor
        · rintro ⟨hxy, ha, hb⟩
          simp only [mem_insert, mem_singleton] at ha hb
          rcases ha with hax | hay | haA
          · subst x
            rcases hb with hba | hby | hbA
            · exact False.elim (hab hba.symm)
            · subst y
              simp
            · have hy : y = u := (hinj a) (hbA.symm.trans hu.symm)
              subst y
              simp
          · subst y
            rcases hb with hbx | hba | hbA
            · subst x
              simp
            · exact False.elim (hab hba.symm)
            · have hx : x = u := (hinj a) ((hsym a x).trans (hbA.symm.trans hu.symm))
              subst x
              simp
          · rcases hb with hbx | hby | hbA
            · subst x
              have hy : y = v := (hinj b) (haA.symm.trans hv.symm)
              subst y
              simp
            · subst y
              have hx : x = v := (hinj b) ((hsym b x).trans (haA.symm.trans hv.symm))
              subst x
              simp
            · exact False.elim (hab (haA.trans hbA.symm))
        · intro hp
          simp only [mem_insert, mem_singleton, Prod.mk.injEq] at hp
          rcases hp with h | h | h | h | h | h
          all_goals rcases h with ⟨rfl,rfl⟩
          all_goals simp [hab, Ne.symm hab, hua, hub, hva, hvb,
            Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb, hu, hv, hua', hvb']
  4. The cardinality of the set of witness pairs is 6.

    Rewriting the set of witness pairs with the explicit six-element set equality `heq`, we compute its cardinality. The pairwise distinctness of `a, b, u, v` ensures that all six pairs are distinct from one another. Repeated application of `card_insert_of_notMem` strips each element while adding 1 to the count, giving 6.

    lines 81–83

    uses card_insert_of_notMem, Prod.mk.injEq, Ne.symm

      rw [heq]
      simp [card_insert_of_notMem, Prod.mk.injEq, hab, Ne.symm hab,
        hua, hub, hva, hvb, Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb]
Finite.surjective_of_injective
An injective function from a finite type to itself is surjective.
mem_filter
An element belongs to the filtered sub-finset if and only if it belongs to the base set and satisfies the predicate.
mem_univ
Every element of a finite type belongs to its universal finset.
true_and
The conjunction of True with any proposition p simplifies to p.
mem_insert
An element belongs to the insertion `insert b s` if and only if it equals `b` or belongs to `s`.
mem_singleton
An element belongs to a singleton `{a}` if and only if it equals `a`.
False.elim
From a contradiction (False), any conclusion can be deduced (principle of explosion).
Prod.mk.injEq
Two ordered pairs are equal if and only if their respective first and second components are equal.
Ne.symm
Inequality is symmetric: if `a ≠ b`, then `b ≠ a`.
card_insert_of_notMem
Inserting an element not already present into a finite set increases its cardinality by 1.

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_pair_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 b : Fin n) (hab : a ≠ b) :    (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)) ∧        b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card = 6 := by  classical  obtain ⟨u, hu⟩ := (Finite.surjective_of_injective (hinj a)) b  obtain ⟨v, hv⟩ := (Finite.surjective_of_injective (hinj b)) a  have hua : u ≠ a := by    intro h    subst u    rw [hid] at hu    exact hab hu  have hub : u ≠ b := by    intro h    subst u    have h : A b a = A b b := by rw [← hsym, hu, hid]    exact hab ((hinj b) h)  have hvb : v ≠ b := by    intro h    subst v    rw [hid] at hv    exact hab hv.symm  have hva : v ≠ a := by    intro h    subst v    have h : A a b = A a a := by rw [hsym, hv, hid]    exact hab ((hinj a) h).symm  have hua' : A u a = b := by rw [hsym, hu]  have hvb' : A v b = a := by rw [hsym, hv]  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)) ∧        b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))) =      {(a,b),(b,a),(a,u),(u,a),(b,v),(v,b)} := by    ext p    rcases p with ⟨x,y⟩    simp only [mem_filter, mem_univ, true_and]    constructor    · rintro ⟨hxy, ha, hb⟩      simp only [mem_insert, mem_singleton] at ha hb      rcases ha with hax | hay | haA      · subst x        rcases hb with hba | hby | hbA        · exact False.elim (hab hba.symm)        · subst y          simp        · have hy : y = u := (hinj a) (hbA.symm.trans hu.symm)          subst y          simp      · subst y        rcases hb with hbx | hba | hbA        · subst x          simp        · exact False.elim (hab hba.symm)        · have hx : x = u := (hinj a) ((hsym a x).trans (hbA.symm.trans hu.symm))          subst x          simp      · rcases hb with hbx | hby | hbA        · subst x          have hy : y = v := (hinj b) (haA.symm.trans hv.symm)          subst y          simp        · subst y          have hx : x = v := (hinj b) ((hsym b x).trans (haA.symm.trans hv.symm))          subst x          simp        · exact False.elim (hab (haA.trans hbA.symm))    · intro hp      simp only [mem_insert, mem_singleton, Prod.mk.injEq] at hp      rcases hp with h | h | h | h | h | h      all_goals rcases h with ⟨rfl,rfl⟩      all_goals simp [hab, Ne.symm hab, hua, hub, hva, hvb,        Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb, hu, hv, hua', hvb']  rw [heq]  simp [card_insert_of_notMem, Prod.mk.injEq, hab, Ne.symm hab,    hua, hub, hva, hvb, Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb]
See it in the graphDiscuss this resultChallenge it