AFTD Auto-Formalizing Theoretical Domains

finite_function_collision_head_pair_injective

theoremverified

Given an injective tail-head encoding and a map whose fibers have a fixed tail, encoding each nonrepresentative by its tail and the unordered pair of its head with its representative head is injective.

Statement

theorem finite_function_collision_head_pair_injective
    (α β γ δ : Type) [DecidableEq δ] (f : α → β) (r : β → α)
    (tail : α → γ) (head : α → δ)
    (hr : ∀ x, f (r (f x)) = f x)
    (htail : ∀ x y, f x = f y → tail x = tail y)
    (hkey : Function.Injective (fun x => (tail x, head x))) :
    Set.InjOn (fun x => (tail x, s(head x, head (r (f x)))))
      {x | r (f x) ≠ x}
Source
Collision counting for the small-overlap route to OP-110.
Verified
04 Nov 2026
Axioms
Quot.soundpropext
Used by 6

The proof, explained

To show injectivity on the set of nonrepresentatives, assume two nonrepresentatives x and y have the same encoding. Comparing their encodings shows that their tails match and their unordered pairs of heads are equal, which leads to two cases for how the heads pair up. If the head of x matches the head of y, injectivity of the tail-head map immediately implies x = y. If instead the head of x matches the representative head of y, then x must equal the representative r (f y), forcing r (f x) = x and contradicting the assumption that x is a nonrepresentative.

  1. Assuming two nonrepresentatives x and y have identical encodings, their tails are equal and their unordered pairs of heads are equal.

    Let x and y be elements in the set {z | r(f(z)) ≠ z} of nonrepresentatives, and suppose their encodings (tail x, s(head x, head (r (f x)))) and (tail y, s(head y, head (r (f y)))) are equal. Decomposing the equality of pairs into components yields tail x = tail y and s(head x, head (r (f x))) = s(head y, head (r (f y))).

    lines 9–11

    uses Prod.mk.injEq

      intro x hx y hy hxy
      simp only [Prod.mk.injEq] at hxy
      obtain ⟨htail_eq, hpair_eq⟩ := hxy
  2. The equality of the head pairs splits into two cases: either head x = head y or head x = head (r (f y)).

    Two unordered pairs {a, b} and {c, d} in the symmetric square are equal if and only if either (a = c and b = d) or (a = d and b = c). Unfolding this equivalence on the head pairs yields two possibilities: either head x = head y (and head (r (f x)) = head (r (f y))), or head x = head (r (f y)) (and head (r (f x)) = head y).

    lines 12–13

    uses Sym2.eq, Sym2.rel_iff

      simp only [Sym2.eq, Sym2.rel_iff] at hpair_eq
      rcases hpair_eq with ⟨hhead1, -⟩ | ⟨hhead1, -⟩
  3. If head x = head y, then x = y.

    Combining tail x = tail y with head x = head y gives (tail x, head x) = (tail y, head y). By the injectivity of the map z ↦ (tail z, head z), we conclude x = y.

    lines 14–15

    uses Prod.ext

      · have : (tail x, head x) = (tail y, head y) := Prod.ext htail_eq hhead1
        exact hkey this
  4. The alternative case head x = head (r (f y)) leads to a contradiction.

    Because r (f y) is the representative of the fiber containing y, we have f (r (f y)) = f y, so the fiber-tail hypothesis htail implies tail (r (f y)) = tail y = tail x. Together with head x = head (r (f y)), this means (tail x, head x) = (tail (r (f y)), head (r (f y))), so injectivity gives x = r (f y). Applying f to both sides yields f x = f (r (f y)) = f y, from which it follows that r (f x) = r (f y) = x. This contradicts the assumption that x is a nonrepresentative (r (f x) ≠ x), which eliminates this case and completes the proof.

    lines 16–22

    uses Prod.ext

      · have htail_rfy : tail (r (f y)) = tail y := htail (r (f y)) y (hr y)
        have hkey_x_rfy : (tail x, head x) = (tail (r (f y)), head (r (f y))) :=
          Prod.ext (htail_eq.trans htail_rfy.symm) hhead1
        have hx_eq_rfy : x = r (f y) := hkey hkey_x_rfy
        have hfx_eq : f x = f y := by rw [hx_eq_rfy, hr y]
        have hrfx_eq_x : r (f x) = x := by rw [hfx_eq, ← hx_eq_rfy]
        exact (hx hrfx_eq_x).elim
Prod.mk.injEq
Two pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Sym2.eq
Two unordered pairs s(a, b) and s(c, d) in the symmetric square are equal if and only if (a, b) and (c, d) are related by the symmetric relation.
Sym2.rel_iff
Two pairs (a, b) and (c, d) are related in the symmetric square if and only if (a = c ∧ b = d) ∨ (a = d ∧ b = c).
Prod.ext
If two pairs have equal first components and equal second components, then the pairs are equal.

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

theorem finite_function_collision_head_pair_injective    (α β γ δ : Type) [DecidableEq δ] (f : α → β) (r : β → α)    (tail : α → γ) (head : α → δ)    (hr : ∀ x, f (r (f x)) = f x)    (htail : ∀ x y, f x = f y → tail x = tail y)    (hkey : Function.Injective (fun x => (tail x, head x))) :    Set.InjOn (fun x => (tail x, s(head x, head (r (f x)))))      {x | r (f x) ≠ x} := by  intro x hx y hy hxy  simp only [Prod.mk.injEq] at hxy  obtain ⟨htail_eq, hpair_eq⟩ := hxy  simp only [Sym2.eq, Sym2.rel_iff] at hpair_eq  rcases hpair_eq with ⟨hhead1, -⟩ | ⟨hhead1, -⟩  · have : (tail x, head x) = (tail y, head y) := Prod.ext htail_eq hhead1    exact hkey this  · have htail_rfy : tail (r (f y)) = tail y := htail (r (f y)) y (hr y)    have hkey_x_rfy : (tail x, head x) = (tail (r (f y)), head (r (f y))) :=      Prod.ext (htail_eq.trans htail_rfy.symm) hhead1    have hx_eq_rfy : x = r (f y) := hkey hkey_x_rfy    have hfx_eq : f x = f y := by rw [hx_eq_rfy, hr y]    have hrfx_eq_x : r (f x) = x := by rw [hfx_eq, ← hx_eq_rfy]    exact (hx hrfx_eq_x).elim
See it in the graphDiscuss this resultChallenge it