AFTD Auto-Formalizing Theoretical Domains

finset_has_no_unique_sums_exists_rep_ne

theoremverified

If A has no unique sums and a, b ∈ A, then the sum a + b has a second representation c + d with c, d ∈ A all four of c, d distinct from a and b.

Statement

theorem finset_has_no_unique_sums_exists_rep_ne {G : Type*} [AddCancelCommMonoid G] [DecidableEq G]
    {A : Finset G} (hA : finset_has_no_unique_sums A) {a b : G} (ha : a ∈ A) (hb : b ∈ A) :
    ∃ c ∈ A, ∃ d ∈ A, a + b = c + d ∧ c ≠ a ∧ c ≠ b ∧ d ≠ a ∧ d ≠ b
Source
step towards nus_min_card_ge_c_log_sq
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • finset_has_no_unique_sumsA has no unique sums (is NUS): |A| ≥ 2 and every sum a + b with a, b ∈ A has at least two representations as an unordered pair from A.
  • finset_unordered_sum_rep_countr_{A,2}(s): the number of unordered pairs {a, b} (a = b allowed) of elements of A with a + b = s.

The proof, explained

Because $A$ has no unique sums, the element $a + b$ has at least two unordered sum representations as pairs from $A$. Since $\{a, b\}$ is one representation, there must exist another representation $\{u, v\}$ distinct from $\{a, b\}$ with $u, v \in A$ and $u + v = a + b$. By cancellativity of the commutative monoid, if either $u$ or $v$ matched either $a$ or $b$, the remaining elements would also be forced to match, yielding $\{u, v\} = \{a, b\}$ and creating a contradiction. Thus, choosing $c = u$ and $d = v$ provides a representation whose entries avoid both $a$ and $b$.

  1. The finset of unordered pairs from $A$ whose sum is $a + b$ has cardinality strictly greater than 1.

    Because $A$ has no unique sums (`finset_has_no_unique_sums`), the number of representations of $a + b$ as an unordered sum from $A$ is at least 2. Unfolding `finset_unordered_sum_rep_count` and applying linear arithmetic over $\mathbb{N}$ shows that this cardinality is strictly greater than 1.

    lines 5–9

      classical
      have h2 := hA.2 a ha b hb
      unfold finset_unordered_sum_rep_count at h2
      have h1 : 1 < (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = a + b)).card := by
        omega
  2. There exists an unordered pair $z \in A.\text{sym2}$ summing to $a + b$ such that $z \ne s(a, b)$.

    Since the finset of pairs summing to $a + b$ contains at least two elements, `Finset.exists_mem_ne` guarantees there is an element $z$ in this set distinct from the pair $s(a, b)$.

    line 10

    uses Finset.exists_mem_ne

      obtain ⟨z, hz, hz0⟩ := Finset.exists_mem_ne h1 (Sym2.mk a b)
  3. The pair $z$ has the form $s(u, v)$ with $u, v \in A$ and $u + v = a + b$.

    By induction on the quotient type `Sym2` via `Sym2.ind`, the pair $z$ can be written as $s(u, v)$. Unfolding membership in the filtered finset using `Finset.mem_filter` and evaluating the sum with `Sym2.lift_mk` gives $u + v = a + b$. By `Finset.mk_mem_sym2_iff`, membership in $A.\text{sym2}$ means both $u \in A$ and $v \in A$.

    lines 11–17

    uses Finset.mem_filter, Sym2.ind, Sym2.lift_mk, Finset.mk_mem_sym2_iff

      rw [Finset.mem_filter] at hz
      induction z using Sym2.ind with
      | h u v =>
        simp only [Sym2.lift_mk] at hz
        obtain ⟨hzA, huv⟩ := hz
        rw [Finset.mk_mem_sym2_iff] at hzA
        obtain ⟨hu, hv⟩ := hzA
  4. Choosing $c = u$ and $d = v$ reduces the goal to proving $u \ne a$, $u \ne b$, $v \ne a$, and $v \ne b$.

    We supply $u$ and $v$ as the existential witnesses. Since $u, v \in A$ and $a + b = u + v$, the membership and sum equalities are satisfied, leaving only the four distinctness requirements to prove.

    line 18

        refine ⟨u, hu, v, hv, huv.symm, ?_, ?_, ?_, ?_⟩
  5. $u \ne a$

    Suppose, for contradiction, that $u = a$. Substituting this into $u + v = a + b$ yields $a + v = a + b$, which by left cancellation (`add_left_cancel`) implies $v = b$. This means $s(u, v) = s(a, b)$, contradicting the fact that $z \ne s(a, b)$.

    lines 19–26

    uses add_left_cancel

        · intro h
          apply hz0
          have hv_eq : v = b := by
            rw [h] at huv
            exact add_left_cancel huv
          subst h
          subst hv_eq
          rfl
  6. $u \ne b$

    Suppose, for contradiction, that $u = b$. Rewriting $a + b$ as $b + a$ using commutativity (`add_comm`), we obtain $b + v = b + a$, which implies $v = a$ by left cancellation (`add_left_cancel`). Thus $s(u, v) = s(b, a)$, which equals $s(a, b)$ by symmetry of unordered pairs (`Sym2.eq_swap`), contradicting $z \ne s(a, b)$.

    lines 27–34

    uses add_comm, add_left_cancel, Sym2.eq_swap

        · intro h
          apply hz0
          have hv_eq : v = a := by
            rw [h, add_comm a b] at huv
            exact add_left_cancel huv
          subst h
          subst hv_eq
          exact Sym2.eq_swap
  7. $v \ne a$

    Suppose, for contradiction, that $v = a$. Commuting the sum $a + b$ to $b + a$ (`add_comm`), the equation becomes $u + a = b + a$. By right cancellation (`add_right_cancel`), we get $u = b$. Then $s(u, v) = s(b, a) = s(a, b)$ by `Sym2.eq_swap`, contradicting $z \ne s(a, b)$.

    lines 35–42

    uses add_comm, add_right_cancel, Sym2.eq_swap

        · intro h
          apply hz0
          have hu_eq : u = b := by
            rw [h, add_comm a b] at huv
            exact add_right_cancel huv
          subst h
          subst hu_eq
          exact Sym2.eq_swap
  8. $v \ne b$

    Suppose, for contradiction, that $v = b$. Substituting this into $u + v = a + b$ gives $u + b = a + b$, so right cancellation (`add_right_cancel`) forces $u = a$. Hence $s(u, v) = s(a, b)$, contradicting $z \ne s(a, b)$.

    lines 43–50

    uses add_right_cancel

        · intro h
          apply hz0
          have hu_eq : u = a := by
            rw [h] at huv
            exact add_right_cancel huv
          subst h
          subst hu_eq
          rfl
add_comm
Addition in a commutative magma satisfies $a + b = b + a$.
add_left_cancel
In an additive structure with left cancellation, $a + b = a + c$ implies $b = c$.
add_right_cancel
In an additive structure with right cancellation, $a + b = c + b$ implies $a = c$.
Finset.exists_mem_ne
In any finite set with cardinality strictly greater than 1, there exists an element distinct from any specified element.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filtering predicate.
Finset.mk_mem_sym2_iff
An unordered pair $s(a, b)$ belongs to the symmetric square of a finset $s$ if and only if both $a \in s$ and $b \in s$.
Sym2.eq_swap
The unordered pair $s(a, b)$ is equal to $s(b, a)$.
Sym2.ind
To prove a property for all elements of $\text{Sym2}(\alpha)$, it suffices to prove it for pairs of the form $s(x, y)$.
Sym2.lift_mk
Evaluating the lift of a symmetric function to $\text{Sym2}$ on an unordered pair $s(a, b)$ gives the value of the function on $(a, b)$.

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

/-- In a NUS set every sum of two elements has a repair whose two entries avoid both summands. -/theorem finset_has_no_unique_sums_exists_rep_ne {G : Type*} [AddCancelCommMonoid G] [DecidableEq G]    {A : Finset G} (hA : finset_has_no_unique_sums A) {a b : G} (ha : a ∈ A) (hb : b ∈ A) :    ∃ c ∈ A, ∃ d ∈ A, a + b = c + d ∧ c ≠ a ∧ c ≠ b ∧ d ≠ a ∧ d ≠ b := by  classical  have h2 := hA.2 a ha b hb  unfold finset_unordered_sum_rep_count at h2  have h1 : 1 < (A.sym2.filter (fun z => Sym2.lift ⟨fun a b => a + b, fun a b => add_comm a b⟩ z = a + b)).card := by    omega  obtain ⟨z, hz, hz0⟩ := Finset.exists_mem_ne h1 (Sym2.mk a b)  rw [Finset.mem_filter] at hz  induction z using Sym2.ind with  | h u v =>    simp only [Sym2.lift_mk] at hz    obtain ⟨hzA, huv⟩ := hz    rw [Finset.mk_mem_sym2_iff] at hzA    obtain ⟨hu, hv⟩ := hzA    refine ⟨u, hu, v, hv, huv.symm, ?_, ?_, ?_, ?_⟩    · intro h      apply hz0      have hv_eq : v = b := by        rw [h] at huv        exact add_left_cancel huv      subst h      subst hv_eq      rfl    · intro h      apply hz0      have hv_eq : v = a := by        rw [h, add_comm a b] at huv        exact add_left_cancel huv      subst h      subst hv_eq      exact Sym2.eq_swap    · intro h      apply hz0      have hu_eq : u = b := by        rw [h, add_comm a b] at huv        exact add_right_cancel huv      subst h      subst hu_eq      exact Sym2.eq_swap    · intro h      apply hz0      have hu_eq : u = a := by        rw [h] at huv        exact add_right_cancel huv      subst h      subst hu_eq      rfl
See it in the graphDiscuss this resultChallenge it