op1370_coordinate_fiber_defect_identity
For a family U of subsets of Fin n and a coordinate x, the size of U plus the number of missing x-erased fibers equals 2^(n-1) plus the number of doubled x-erased fibers.
Statement
theorem op1370_coordinate_fiber_defect_identity (n : ℕ) (x : Fin n) (U : Finset (Finset (Fin n))) : let V := Finset.univ.erase x; let P := U.filter (fun S => x ∉ S); let Q := (U.filter (fun S => x ∈ S)).image (fun S => S.erase x); U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card
- Source
- Coordinate-fiber counting helper for OP-1370, arXiv:2611.12199 Conjecture 4.3.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We partition the family U into the subfamily P of subsets avoiding x and the subfamily Q₀ of subsets containing x. Erasing x is an injection on Q₀, so its image Q has size |Q₀|, giving |U| = |P| + |Q|. Both P and Q consist of subsets of V = Fin n \ {x}, so by inclusion-exclusion |P ∪ Q| + |P ∩ Q| = |P| + |Q| = |U|. Since |𝒫(V)| = 2^(n-1), the missing fibers count |𝒫(V) \ (P ∪ Q)| equals 2^(n-1) - |P ∪ Q|, from which the identity follows immediately by cancellation.
Define the universe without x as V = Fin n \ {x}, partition U into P = {S ∈ U | x ∉ S} and Q₀ = {S ∈ U | x ∈ S}, set Q = {S \ {x} | S ∈ Q₀}, and restate the theorem in these terms.
We open the Finset namespace, enable classical logic, and introduce the local definitions: V is the universe with x removed, P is the subfamily of sets in U avoiding x, Q₀ is the subfamily containing x, and Q is obtained by erasing x from each set in Q₀. The goal is restated as |U| + |𝒫(V) \ (P ∪ Q)| = 2^(n-1) + |P ∩ Q|.
open Finset in classical dsimp only let V : Finset (Fin n) := univ.erase x let P := U.filter (fun S => x ∉ S) let Q0 := U.filter (fun S => x ∈ S) let Q := Q0.image (fun S => S.erase x) change U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card
P ∪ Q is a collection of subsets of V, so P ∪ Q ⊆ 𝒫(V).
By mem_powerset, it suffices to show that any S ∈ P ∪ Q satisfies S ⊆ V. An element z ∈ S cannot equal x because if S ∈ P then x ∉ S by definition of P, and if S ∈ Q then S was formed by erasing x from some T, so x ∉ S by mem_erase. Thus every element of S belongs to V = Fin n \ {x}.
uses
mem_powerset,mem_erasehave hsub : P ∪ Q ⊆ V.powerset := by intro S hS rw [mem_powerset] intro z hz simp only [V, mem_erase, mem_univ, and_true] intro hzx subst z rcases mem_union.mp hS with hP | hQ · exact (mem_filter.mp hP).2 hz · obtain ⟨T, _, rfl⟩ := mem_image.mp hQ exact (mem_erase.mp hz).1 rfl
|Q| = |Q₀|.
By card_image_of_injOn, the image of Q₀ under erasing x has the same size as Q₀ if the map is injective on Q₀. For any a, b ∈ Q₀ with a \ {x} = b \ {x}, because both a and b contain x, insert_erase allows reconstructing a = (a \ {x}) ∪ {x} = (b \ {x}) ∪ {x} = b.
uses
card_image_of_injOn,insert_erasehave hQcard : Q.card = Q0.card := by apply card_image_of_injOn intro a ha b hb hab have hax : x ∈ a := (mem_filter.mp ha).2 have hbx : x ∈ b := (mem_filter.mp hb).2 change a.erase x = b.erase x at hab calc a = insert x (a.erase x) := (insert_erase hax).symm _ = insert x (b.erase x) := by rw [hab] _ = b := insert_erase hbx
|P| + |Q₀| = |U|.
Filtering U by the condition x ∈ S and its negation partitions U into Q₀ and P. By card_filter_add_card_filter_not and commutativity of addition (Nat.add_comm), their cardinalities sum to |U|.
uses
card_filter_add_card_filter_not,Nat.add_commhave hsplit : P.card + Q0.card = U.card := by simpa [P, Q0, Nat.add_comm] using (card_filter_add_card_filter_not (s := U) (fun s => x ∈ s))
|V| = n - 1 and |𝒫(V)| = 2^(n-1).
Since V is Fin n with one element removed, its cardinality is n - 1. Its powerset 𝒫(V) therefore contains 2^(n-1) subsets.
have hVcard : V.card = n - 1 := by simp [V] have hpow : V.powerset.card = 2 ^ (n - 1) := by simp [hVcard]
|𝒫(V) \ (P ∪ Q)| = 2^(n-1) - |P ∪ Q| and |P ∪ Q| ≤ 2^(n-1).
Because P ∪ Q ⊆ 𝒫(V), card_sdiff_of_subset gives |𝒫(V) \ (P ∪ Q)| = |𝒫(V)| - |P ∪ Q| = 2^(n-1) - |P ∪ Q|, and card_le_card confirms |P ∪ Q| ≤ |𝒫(V)| = 2^(n-1).
uses
card_sdiff_of_subset,card_le_cardhave hdiff := card_sdiff_of_subset hsub rw [hpow] at hdiff have hle := card_le_card hsub rw [hpow] at hle
|U| + |𝒫(V) \ (P ∪ Q)| = 2^(n-1) + |P ∩ Q|.
By the principle of inclusion-exclusion (card_union_add_card_inter), |P ∪ Q| + |P ∩ Q| = |P| + |Q|. Since |U| = |P| + |Q₀| = |P| + |Q|, we have |U| = |P ∪ Q| + |P ∩ Q|. Combining this with |𝒫(V) \ (P ∪ Q)| = 2^(n-1) - |P ∪ Q|, the terms |P ∪ Q| cancel, and omega verifies the resulting linear equality over ℕ.
uses
card_union_add_card_interhave hinclex := card_union_add_card_inter P Q omega
mem_powerset- An element belongs to the powerset of t if and only if it is a subset of t.
mem_erase- An element a belongs to s with b removed if and only if a ≠ b and a ∈ s.
card_image_of_injOn- If a function is injective on a finite set s, then the image of s has the same cardinality as s.
insert_erase- Inserting an element a into s \ {a} reconstructs s whenever a ∈ s.
card_filter_add_card_filter_not- The number of elements of a finite set satisfying a predicate plus the number satisfying its negation equals the cardinality of the set.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
card_sdiff_of_subset- For a subset s ⊆ t of finite sets, |t \ s| = |t| - |s|.
card_le_card- If s ⊆ t for finite sets, then |s| ≤ |t|.
card_union_add_card_inter- For finite sets s and t, |s ∪ t| + |s ∩ t| = |s| + |t| (the principle of inclusion-exclusion).
- Natural number subtraction $a - b$ in Lean truncates to zero when $b > a$. The inequality $|P \cup Q| \le 2^{n-1}$ is explicitly established so that the subtraction in $|\mathcal{P}(V) \setminus (P \cup Q)| = 2^{n-1} - |P \cup Q|$ behaves like standard arithmetic before the linear arithmetic solver (omega) finishes the proof.
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 op1370_coordinate_fiber_defect_identity (n : ℕ) (x : Fin n) (U : Finset (Finset (Fin n))) : let V := Finset.univ.erase x; let P := U.filter (fun S => x ∉ S); let Q := (U.filter (fun S => x ∈ S)).image (fun S => S.erase x); U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card := by open Finset in classical dsimp only let V : Finset (Fin n) := univ.erase x let P := U.filter (fun S => x ∉ S) let Q0 := U.filter (fun S => x ∈ S) let Q := Q0.image (fun S => S.erase x) change U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card have hsub : P ∪ Q ⊆ V.powerset := by intro S hS rw [mem_powerset] intro z hz simp only [V, mem_erase, mem_univ, and_true] intro hzx subst z rcases mem_union.mp hS with hP | hQ · exact (mem_filter.mp hP).2 hz · obtain ⟨T, _, rfl⟩ := mem_image.mp hQ exact (mem_erase.mp hz).1 rfl have hQcard : Q.card = Q0.card := by apply card_image_of_injOn intro a ha b hb hab have hax : x ∈ a := (mem_filter.mp ha).2 have hbx : x ∈ b := (mem_filter.mp hb).2 change a.erase x = b.erase x at hab calc a = insert x (a.erase x) := (insert_erase hax).symm _ = insert x (b.erase x) := by rw [hab] _ = b := insert_erase hbx have hsplit : P.card + Q0.card = U.card := by simpa [P, Q0, Nat.add_comm] using (card_filter_add_card_filter_not (s := U) (fun s => x ∈ s)) have hVcard : V.card = n - 1 := by simp [V] have hpow : V.powerset.card = 2 ^ (n - 1) := by simp [hVcard] have hdiff := card_sdiff_of_subset hsub rw [hpow] at hdiff have hle := card_le_card hsub rw [hpow] at hle have hinclex := card_union_add_card_inter P Q omega