projected_sets_card_le_of_zero_lift
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.
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.
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')
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.
uses
Finset.mem_inter.mp,Finset.mem_image.mp,Finset.mem_filter.mpr,add_right_cancelhave 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)
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)|.
uses
Finset.image_image,Function.comp_def,Finset.card_image_of_injective,neg_injectivehave 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
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.
uses
Finset.card_le_card,Finset.card_le_univ,Finset.card_union_add_card_interhave 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
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|.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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