AFTD Auto-Formalizing Theoretical Domains

mem_subsequence_sums

theoremverified

Given a natural number n, an additive commutative monoid G with decidable equality, a multiset S over G, and an element g of G, g belongs to the finite set subsequence_sums n S if and only if there exists a submultiset U ≤ S with card U = n and sum U = g.

Statement

theorem mem_subsequence_sums {n : ℕ} {G : Type*} [AddCommMonoid G] [DecidableEq G] (S : Multiset G) (g : G) :
    g ∈ subsequence_sums n S ↔ ∃ U ≤ S, U.card = n ∧ U.sum = g
Source
arXiv:2610.35819 Section 8
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • subsequence_sumsFor a natural number n and a multiset S of elements of an additive commutative monoid G with decidable equality, subsequence_sums n S is…
Used by 2

Read back from the Lean

For a natural number $n$, an additive commutative monoid $G$ with decidable equality, a multiset $S$ of elements of $G$, and an element $g \in G$, $g \in \text{subsequence\_sums}(n, S)$ if and only if there exists a multiset $U$ such that $U \le S$ (i.e., $U$ is a submultiset of $S$), the cardinality of $U$ is $n$ ($U.\text{card} = n$), and the sum of the elements of $U$ is $g$ ($U.\text{sum} = g$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof unfolds the definition of `subsequence_sums n S` as the finite set of sums of submultisets of $S$ with cardinality $n$. It rewrites membership in the finite set and multiset image into the existence of a multiset in the filtered powerset with sum $g$. Finally, it unpacks the powerset and filter conditions into $U \le S$ with $\operatorname{card}(U) = n$, completing the equivalence by regrouping conjunctions.

  1. Membership of $g$ in `subsequence_sums n S` is equivalent to the existence of a multiset in the filtered powerset of $S$ whose sum is $g$.

    Unfolding the definition of `subsequence_sums` reveals that it is constructed by taking the powerset of $S$, filtering for submultisets of cardinality $n$, mapping the multiset sum over them, and converting the resulting multiset to a `Finset`. Rewriting with `Multiset.mem_toFinset` converts membership in the finite set to membership in the multiset image, and `Multiset.mem_map` turns this into the existence of an element $a$ in the filtered powerset such that $\operatorname{sum}(a) = g$.

    lines 4–5

    uses Multiset.mem_toFinset, Multiset.mem_map

      unfold subsequence_sums
      rw [Multiset.mem_toFinset, Multiset.mem_map]
  2. Membership of $a$ in the filtered powerset of $S$ is equivalent to $a ≤ S$ and $\operatorname{card}(a) = n$.

    Simplifying with `Multiset.mem_filter` and `Multiset.mem_powerset` unpacks the condition: an element $a$ belongs to `Multiset.filter (·.card = n) S.powerset` if and only if $a \in S.\text{powerset}$ and $\operatorname{card}(a) = n$, where $a \in S.\text{powerset}$ is equivalent to $a \le S$. The existential statement becomes $\exists a, (a \le S \land \operatorname{card}(a) = n) \land \operatorname{sum}(a) = g$.

    line 6

    uses Multiset.mem_filter, Multiset.mem_powerset

      simp only [Multiset.mem_filter, Multiset.mem_powerset]
  3. The existential statement is equivalent to $\exists U \le S, \operatorname{card}(U) = n \land \operatorname{sum}(U) = g$.

    The goal is closed by showing that the two existential statements are logically equivalent: unpacking the conjunction $(a \le S \land \operatorname{card}(a) = n) \land \operatorname{sum}(a) = g$ into its three conjuncts and regrouping them as $a \le S \land (\operatorname{card}(a) = n \land \operatorname{sum}(a) = g)$ gives the desired bi-implication.

    lines 7–8

      exact ⟨fun ⟨U, ⟨hU, hc⟩, hs⟩ => ⟨U, hU, hc, hs⟩,
        fun ⟨U, hU, hc, hs⟩ => ⟨U, ⟨hU, hc⟩, hs⟩⟩
Multiset.mem_toFinset
An element belongs to the finite set `s.toFinset` if and only if it belongs to the multiset `s`.
Multiset.mem_map
An element `b` belongs to the multiset image `Multiset.map f s` if and only if there exists an element `a ∈ s` such that `f a = b`.
Multiset.mem_filter
An element belongs to `Multiset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Multiset.mem_powerset
A multiset `s` belongs to the powerset of `t` if and only if `s` is a submultiset of `t` (`s ≤ t`).

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

/-- Membership in subsequence_sums n S is equivalent to the existence of a length-n submultiset with sum g. -/theorem mem_subsequence_sums {n : ℕ} {G : Type*} [AddCommMonoid G] [DecidableEq G] (S : Multiset G) (g : G) :    g ∈ subsequence_sums n S ↔ ∃ U ≤ S, U.card = n ∧ U.sum = g := by  unfold subsequence_sums  rw [Multiset.mem_toFinset, Multiset.mem_map]  simp only [Multiset.mem_filter, Multiset.mem_powerset]  exact ⟨fun ⟨U, ⟨hU, hc⟩, hs⟩ => ⟨U, hU, hc, hs⟩,    fun ⟨U, hU, hc, hs⟩ => ⟨U, ⟨hU, hc⟩, hs⟩⟩
See it in the graphDiscuss this resultChallenge it