AFTD Auto-Formalizing Theoretical Domains

projected_sets_card_le_of_zero_lift

theoremverified

For a homomorphism of additive groups, if each pair from X and Y with opposite images sums to zero upstairs, the sum of the two image cardinalities is at most the size of the target plus the number of unique fibers of X.

Statement

theorem projected_sets_card_le_of_zero_lift
    {α β : Type*} [AddGroup α] [AddGroup β] [Fintype β]
    [DecidableEq α] [DecidableEq β]
    (f : α →+ β) (X Y : Finset α)
    (hzero : ∀ x ∈ X, ∀ y ∈ Y, f x + f y = 0 → x + y = 0) :
    (X.image f).card + (Y.image f).card ≤ Fintype.card β +
      ((X.image f).filter (fun g => ∀ x ∈ X, ∀ x' ∈ X,
        f x = g → f x' = g → x = x')).card
Source
Supporting cardinality lemma for OP-259, arXiv:2610.19965 Question 3.1, deep session IN-185; used in the proposed r=n=3 reduction.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof bounds the sum of the image sizes |f(X)| + |f(Y)| using inclusion-exclusion on the sets P = f(X) and Q = -f(Y). The key observation is that whenever an element g lies in P ∩ Q, any two preimages x, x' ∈ X of g satisfy f(x) + f(y) = 0 = f(x') + f(y) for some y ∈ Y, which lifts to x + y = 0 = x' + y and forces x = x'. Therefore, P ∩ Q is contained in the set U of elements with unique fibers in X. Since |P| + |f(Y)| = |P| + |Q| = |P ∪ Q| + |P ∩ Q| ≤ |β| + |U|, the claim follows immediately.

  1. Define P = f(X), Q = -f(Y), and U as the set of elements in P with a unique fiber in X.

    We introduce abbreviations for three finite sets in β: P is the image of X under f, Q is the image of Y under -f, and U is the subset of elements in P whose preimage in X contains at most one element.

    lines 9–12

      let P := X.image f
      let Q := Y.image (fun y => -f y)
      let U := P.filter (fun g => ∀ x ∈ X, ∀ x' ∈ X,
        f x = g → f x' = g → x = x')
  2. The intersection P ∩ Q is contained in U.

    Take any g ∈ P ∩ Q; by definition of Q, g = -f(y) for some y ∈ Y. If two elements x, x' ∈ X map to g, then f(x) + f(y) = g + (-g) = 0 and f(x') + f(y) = 0. By the hypothesis hzero, both x + y = 0 and x' + y = 0 upstairs, so x + y = x' + y. Cancelling y on the right via add_right_cancel yields x = x'. Thus the fiber of g in X is unique, placing g in U.

    lines 13–21

    uses Finset.mem_inter.mp, Finset.mem_image.mp, Finset.mem_filter.mpr, add_right_cancel

      have hi : P ∩ Q ⊆ U := by
        intro g hg
        obtain ⟨hgP, hgQ⟩ := Finset.mem_inter.mp hg
        obtain ⟨y, hy, hgy⟩ := Finset.mem_image.mp hgQ
        refine Finset.mem_filter.mpr ⟨hgP, ?_⟩
        intro x hx x' hx' hxg hxg'
        have hxy : x + y = 0 := hzero x hx y hy (by rw [hxg, ← hgy]; simp)
        have hx'y : x' + y = 0 := hzero x' hx' y hy (by rw [hxg', ← hgy]; simp)
        exact add_right_cancel (hxy.trans hx'y.symm)
  3. The set Q has the same cardinality as f(Y).

    The set Q is the image of f(Y) under the negation map on β. Since negation in an additive group is injective (neg_injective), Finset.card_image_of_injective shows that |Q| = |f(Y)|.

    lines 22–26

    uses Finset.image_image, Function.comp_def, Finset.card_image_of_injective, neg_injective

      have hQ : Q.card = (Y.image f).card := by
        calc
          Q.card = ((Y.image f).image (fun y => -y)).card := by
            simp only [Q, Finset.image_image, Function.comp_def]
          _ = (Y.image f).card := Finset.card_image_of_injective _ neg_injective
  4. The cardinalities satisfy |P ∩ Q| ≤ |U|, |P ∪ Q| ≤ |β|, and |P ∪ Q| + |P ∩ Q| = |P| + |Q|.

    The inclusion P ∩ Q ⊆ U implies |P ∩ Q| ≤ |U| by Finset.card_le_card. Because β is a finite type, the union P ∪ Q has cardinality at most |β| by Finset.card_le_univ. The standard inclusion-exclusion identity |P ∪ Q| + |P ∩ Q| = |P| + |Q| is provided by Finset.card_union_add_card_inter.

    lines 27–29

    uses Finset.card_le_card, Finset.card_le_univ, Finset.card_union_add_card_inter

      have hicard := Finset.card_le_card hi
      have hucard : (P ∪ Q).card ≤ Fintype.card β := Finset.card_le_univ _
      have heq := Finset.card_union_add_card_inter P Q
  5. The desired inequality |f(X)| + |f(Y)| ≤ |β| + |U| holds. automation

    Rewriting the goal in terms of P, |f(Y)|, |β|, and |U|, the result follows by linear integer arithmetic from |P| + |f(Y)| = |P| + |Q| = |P ∪ Q| + |P ∩ Q| ≤ |β| + |U|.

    lines 30–31

      change P.card + (Y.image f).card ≤ Fintype.card β + U.card
      omega
add_right_cancel
In an additive group, right cancellation holds: if a + b = c + b, then a = c.
Finset.mem_inter.mp
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_image.mp
An element belongs to the image of a finite set under a map if and only if it is the image of some element in that set.
Finset.mem_filter.mpr
An element belongs to a filtered finite set if it belongs to the original set and satisfies the filtering predicate.
Finset.image_image
The image of an image of a finite set equals the image under the composite function: g '' (f '' s) = (g ∘ f) '' s.
Function.comp_def
The definition of function composition: (f ∘ g)(x) = f(g(x)).
Finset.card_image_of_injective
An injective function maps any finite set to an image with the same cardinality.
neg_injective
The negation map x ↦ -x in an additive group is injective.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then |s| ≤ |t|.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the cardinality of the type.
Finset.card_union_add_card_inter
The principle of inclusion-exclusion: |s ∪ t| + |s ∩ t| = |s| + |t| for finite sets s and 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

theorem projected_sets_card_le_of_zero_lift    {α β : Type*} [AddGroup α] [AddGroup β] [Fintype β]    [DecidableEq α] [DecidableEq β]    (f : α →+ β) (X Y : Finset α)    (hzero : ∀ x ∈ X, ∀ y ∈ Y, f x + f y = 0 → x + y = 0) :    (X.image f).card + (Y.image f).card ≤ Fintype.card β +      ((X.image f).filter (fun g => ∀ x ∈ X, ∀ x' ∈ X,        f x = g → f x' = g → x = x')).card := by  let P := X.image f  let Q := Y.image (fun y => -f y)  let U := P.filter (fun g => ∀ x ∈ X, ∀ x' ∈ X,    f x = g → f x' = g → x = x')  have hi : P ∩ Q ⊆ U := by    intro g hg    obtain ⟨hgP, hgQ⟩ := Finset.mem_inter.mp hg    obtain ⟨y, hy, hgy⟩ := Finset.mem_image.mp hgQ    refine Finset.mem_filter.mpr ⟨hgP, ?_⟩    intro x hx x' hx' hxg hxg'    have hxy : x + y = 0 := hzero x hx y hy (by rw [hxg, ← hgy]; simp)    have hx'y : x' + y = 0 := hzero x' hx' y hy (by rw [hxg', ← hgy]; simp)    exact add_right_cancel (hxy.trans hx'y.symm)  have hQ : Q.card = (Y.image f).card := by    calc      Q.card = ((Y.image f).image (fun y => -y)).card := by        simp only [Q, Finset.image_image, Function.comp_def]      _ = (Y.image f).card := Finset.card_image_of_injective _ neg_injective  have hicard := Finset.card_le_card hi  have hucard : (P ∪ Q).card ≤ Fintype.card β := Finset.card_le_univ _  have heq := Finset.card_union_add_card_inter P Q  change P.card + (Y.image f).card ≤ Fintype.card β + U.card  omega
See it in the graphDiscuss this resultChallenge it