AFTD Auto-Formalizing Theoretical Domains

nus_exists_inclusion_minimal_subset

theoremverified

Every finite set with no unique sums contains an inclusion-minimal one: there is a subset B of A that has no unique sums and none of whose proper subsets has no unique sums.

Statement

theorem nus_exists_inclusion_minimal_subset {G : Type*} [AddCommMonoid G] [DecidableEq G]
    {A : Finset G} (hA : finset_has_no_unique_sums A) :
    ∃ B : Finset G, B ⊆ A ∧ finset_has_no_unique_sums B ∧
      ∀ C : Finset G, C ⊂ B → ¬ finset_has_no_unique_sums C
Source
step towards nus_min_card_ge_near_quadratic
Verified
25 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_has_no_unique_sums_decidableHaving no unique sums is a decidable property for finite subsets of an additive commutative monoid with decidable equality.
Used by 1

The proof, explained

The proof finds an inclusion-minimal subset by minimizing cardinality. Consider the family of all subsets of A that have no unique sums; this family is nonempty because A belongs to it. Since the family is finite, it contains an element B of minimal cardinality. If B had a proper subset C that also had no unique sums, C would belong to the family and have strictly smaller cardinality than B, contradicting the minimality of |B|.

  1. The collection S of subsets of A having no unique sums is nonempty, as it contains A.

    Enable classical reasoning for decidability. Define S as the sub-collection of the power set of A consisting of sets with no unique sums. Since A ⊆ A and A has no unique sums by hypothesis, A belongs to S.

    lines 6–10

    uses Finset.mem_filter, Finset.mem_powerset_self

      classical
      let S := A.powerset.filter (fun B => finset_has_no_unique_sums B)
      have hS : A ∈ S := by
        rw [Finset.mem_filter]
        exact ⟨Finset.mem_powerset_self A, hA⟩
  2. There exists an element B ∈ S of minimal cardinality, which is a subset of A having no unique sums.

    Because S is a nonempty finite set, there exists an element B ∈ S minimizing the cardinality function. Unpacking membership in S shows that B ⊆ A and B has no unique sums.

    lines 11–14

    uses Finset.exists_min_image, Finset.mem_filter, Finset.mem_powerset

      obtain ⟨B, hB_mem, hB_min⟩ := Finset.exists_min_image S Finset.card ⟨A, hS⟩
      rw [Finset.mem_filter] at hB_mem
      rcases hB_mem with ⟨hBA, hB_nus⟩
      rw [Finset.mem_powerset] at hBA
  3. To show that B is inclusion-minimal, assume for contradiction that some proper subset C ⊂ B has no unique sums; then C must also belong to S.

    Present B as the required witness. To show that no proper subset has no unique sums, suppose C ⊂ B does. Transitivity of inclusion (C ⊂ B ⊆ A) gives C ⊆ A. Since C has no unique sums, it satisfies the membership condition for S, so C ∈ S.

    lines 15–19

    uses Finset.mem_filter, Finset.mem_powerset.mpr

      refine ⟨B, hBA, hB_nus, fun C hCB hC_nus => ?_⟩
      have hCA : C ⊆ A := hCB.1.trans hBA
      have hCS : C ∈ S := by
        rw [Finset.mem_filter]
        exact ⟨Finset.mem_powerset.mpr hCA, hC_nus⟩
  4. Contradiction: B cannot minimize cardinality in S if C ∈ S is strictly smaller than B. automation

    Since C ∈ S and B minimizes cardinality in S, we have |B| ≤ |C|. But C is a strict subset of B, so |C| < |B|. The linear arithmetic tactic `omega` detects that |B| ≤ |C| and |C| < |B| cannot both hold, completing the proof by contradiction.

    lines 20–22

    uses Finset.card_lt_card

      have h_le := hB_min C hCS
      have h_lt := Finset.card_lt_card hCB
      omega
Finset.mem_filter
An element belongs to a filtered sub-finset if and only if it belongs to the original finset and satisfies the filter predicate.
Finset.mem_powerset_self
Every finite set belongs to its own power set.
Finset.exists_min_image
Any nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
Finset.mem_powerset
A finite set belongs to the power set of another if and only if it is a subset of it.
Finset.mem_powerset.mpr
If a finite set is a subset of another, then it belongs to the other's power set.
Finset.card_lt_card
A strict subset of a finite set has strictly smaller cardinality.

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

/-- Every NUS set contains an inclusion-minimal NUS subset (opening line of Section 2 of Hou-Yang). -/theorem nus_exists_inclusion_minimal_subset {G : Type*} [AddCommMonoid G] [DecidableEq G]    {A : Finset G} (hA : finset_has_no_unique_sums A) :    ∃ B : Finset G, B ⊆ A ∧ finset_has_no_unique_sums B ∧      ∀ C : Finset G, C ⊂ B → ¬ finset_has_no_unique_sums C := by  classical  let S := A.powerset.filter (fun B => finset_has_no_unique_sums B)  have hS : A ∈ S := by    rw [Finset.mem_filter]    exact ⟨Finset.mem_powerset_self A, hA⟩  obtain ⟨B, hB_mem, hB_min⟩ := Finset.exists_min_image S Finset.card ⟨A, hS⟩  rw [Finset.mem_filter] at hB_mem  rcases hB_mem with ⟨hBA, hB_nus⟩  rw [Finset.mem_powerset] at hBA  refine ⟨B, hBA, hB_nus, fun C hCB hC_nus => ?_⟩  have hCA : C ⊆ A := hCB.1.trans hBA  have hCS : C ∈ S := by    rw [Finset.mem_filter]    exact ⟨Finset.mem_powerset.mpr hCA, hC_nus⟩  have h_le := hB_min C hCS  have h_lt := Finset.card_lt_card hCB  omega
See it in the graphDiscuss this resultChallenge it