op1370_sparse_fiber_count
For n at least three, if a family of subsets of Fin n omits the empty set, the singleton {x}, its complement, and the whole ground set, and at most one x-erased fiber has both orientations present, then the family has at most 2^(n-1)-1 members.
Statement
lemma op1370_sparse_fiber_count (n : ℕ) (hn : 3 ≤ n) (U : Finset (Finset (Fin n))) (x : Fin n) (h0 : (∅ : Finset (Fin n)) ∉ U) (h1 : ({x} : Finset (Fin n)) ∉ U) (h2 : (Finset.univ.erase x : Finset (Fin n)) ∉ U) (h3 : (Finset.univ : Finset (Fin n)) ∉ U) (hover : ((U.filter (fun s => x ∉ s)) ∩ ((U.filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : U.card ≤ 2 ^ (n - 1) - 1
- Source
- Coordinate-fiber counting helper for OP-1370, arXiv:2611.12199 Conjecture 4.3.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op1370_sparse_double_fiber_boundLet n and t be at least three. For nonempty, uncomplemented, mutually strongly incomparable indexed families of subsets of Fin n, suppose…
The proof, explained
We partition the family U into subsets omitting x (denoted P) and subsets containing x (denoted Q0). Erasing x from each set in Q0 yields a collection Q of the same size, so |U| = |P| + |Q|. Because U omits the empty set, the singleton {x}, the full set, and its complement V, every member of P ∪ Q is a non-empty proper subset of V, giving |P ∪ Q| ≤ 2^(n-1) - 2. By inclusion-exclusion, |U| = |P ∪ Q| + |P ∩ Q|, and since |P ∩ Q| ≤ 1 by hypothesis, we conclude |U| ≤ 2^(n-1) - 1.
Define V as the ground set without x, and partition U into the subfamily P of sets omitting x and the subfamily Q0 of sets containing x, projecting Q0 to Q by removing x.
We fix the ambient sub-universe V = Fin n \ {x}. We partition the family U into sets not containing x (denoted P) and sets containing x (denoted Q0). We also define Q as the collection obtained by erasing x from each member of Q0. Both P and Q thus consist of subsets of V.
open Finset in classical 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)
Every set in P ∪ Q is a non-empty, proper subset of V, so P ∪ Q ⊆ 𝒫(V) \ {∅, V}.
Take any S ∈ P ∪ Q. If S ∈ P, then x ∉ S by definition; if S ∈ Q, then S = T \ {x} for some T ∈ Q0, so again x ∉ S. Because S ⊆ Fin n and x ∉ S, we have S ⊆ V. Next, S cannot be empty: S ∈ P with S = ∅ would mean ∅ ∈ U, contradicting hypothesis h0; S ∈ Q with S = ∅ means T \ {x} = ∅, which via insert_erase implies T = {x} ∈ U, contradicting hypothesis h1. Similarly, S cannot be V: S ∈ P with S = V implies V ∈ U, contradicting hypothesis h2; S ∈ Q with S = V means T \ {x} = V, which via insert_erase implies T = Fin n ∈ U, contradicting hypothesis h3. Hence S ∈ 𝒫(V) \ {∅, V}.
uses
insert_erasehave hpq : P ∪ Q ⊆ V.powerset \ {∅, V} := by intro S hS have hxS : x ∉ S := by rcases mem_union.mp hS with hS | hS · exact (mem_filter.mp hS).2 · obtain ⟨T, hT, rfl⟩ := mem_image.mp hS simp have hsub : S ⊆ V := by intro y hy simp only [V, mem_erase, mem_univ, and_true] exact fun h => hxS (h ▸ hy) have hn0 : S ≠ ∅ := by intro h subst S rcases mem_union.mp hS with hp | hq · exact h0 (mem_filter.mp hp).1 · obtain ⟨T, hT, heq⟩ := mem_image.mp hq have hTx : x ∈ T := (mem_filter.mp hT).2 have hTeq : T = {x} := by have hi := insert_erase hTx rw [heq] at hi simpa using hi.symm exact h1 (hTeq ▸ (mem_filter.mp hT).1) have hnV : S ≠ V := by intro h subst S rcases mem_union.mp hS with hp | hq · exact h2 (mem_filter.mp hp).1 · obtain ⟨T, hT, heq⟩ := mem_image.mp hq have hTx : x ∈ T := (mem_filter.mp hT).2 have hTu : T = univ := by have hi := insert_erase hTx rw [heq] at hi simpa [V] using hi.symm exact h3 (hTu ▸ (mem_filter.mp hT).1) simp only [mem_sdiff, mem_powerset, mem_insert, mem_singleton, not_or] exact ⟨hsub, hn0, hnV⟩
The union P ∪ Q has cardinality at most 2^(n-1) - 2.
Since V = Fin n \ {x}, its cardinality is n - 1. Because n ≥ 3, V is non-empty, which means ∅ and V are distinct elements of 𝒫(V), so |{∅, V}| = 2. By card_sdiff_of_subset and card_powerset, |𝒫(V) \ {∅, V}| = 2^(n-1) - 2. Since P ∪ Q ⊆ 𝒫(V) \ {∅, V}, monotonicity of cardinality (card_le_card) gives |P ∪ Q| ≤ 2^(n-1) - 2.
uses
card_sdiff_of_subset,card_powerset,card_le_cardhave hVcard : V.card = n - 1 := by simp [V] have hVne : V ≠ ∅ := by intro h have hc := congrArg Finset.card h simp [hVcard] at hc omega have hdel : ({∅, V} : Finset (Finset (Fin n))) ⊆ V.powerset := by rw [insert_subset_iff, singleton_subset_iff] exact ⟨mem_powerset.mpr (empty_subset V), mem_powerset.mpr subset_rfl⟩ have hcarddel : ({∅, V} : Finset (Finset (Fin n))).card = 2 := by simp [hVne.symm] have hbound : (P ∪ Q).card ≤ 2 ^ (n - 1) - 2 := by have h := card_le_card hpq rw [card_sdiff_of_subset hdel, hcarddel, card_powerset, hVcard] at h exact h
The projection from Q0 to Q is a bijection, so |Q| = |Q0|.
By card_image_of_injOn, it suffices to check that erasing x is injective on Q0. If two sets a, b ∈ Q0 satisfy a \ {x} = b \ {x}, then since x ∈ a and x ∈ b, reinserting x using insert_erase yields 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
The size of U decomposes as |U| = |P| + |Q0|.
Every set in U either contains x or does not. By card_filter_add_card_filter_not, the cardinality of U is the sum of the cardinalities of the two complementary filtered subfamilies P and Q0.
uses
card_filter_add_card_filter_nothave 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))
|U| ≤ 2^(n-1) - 1.
By inclusion-exclusion (card_union_add_card_inter), |P| + |Q| = |P ∪ Q| + |P ∩ Q|. Since |Q0| = |Q| and |U| = |P| + |Q0|, this becomes |U| = |P ∪ Q| + |P ∩ Q|. Combining the bound |P ∪ Q| ≤ 2^(n-1) - 2 with the fiber-overlap hypothesis |P ∩ Q| ≤ 1 (hover) yields |U| ≤ 2^(n-1) - 1. The fact that 2^(n-1) ≥ 4 (derived via Nat.pow_le_pow_right from n - 1 ≥ 2) ensures natural number subtraction does not underflow, allowing linear arithmetic (omega) to conclude.
uses
card_union_add_card_inter,Nat.pow_le_pow_righthave hPQ := card_union_add_card_inter P Q have hpow : 4 ≤ 2 ^ (n - 1) := by calc 4 = 2 ^ 2 := by norm_num _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by omega) (by omega) change (P ∩ Q).card ≤ 1 at hover omega
insert_erase- For an element a in a finite set s, inserting a into s with a removed yields s.
card_sdiff_of_subset- If s ⊆ t for finite sets s and t, then the cardinality of t \ s is |t| - |s|.
card_powerset- The powerset of a finite set s has cardinality 2^|s|.
card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
card_image_of_injOn- If a function is injective on a finite set s, then its image has the same cardinality as s.
card_filter_add_card_filter_not- The cardinality of a finite set s is the sum of the number of elements satisfying a predicate and the number of elements not satisfying it.
card_union_add_card_inter- For two finite sets s and t, |s ∪ t| + |s ∩ t| = |s| + |t|.
Nat.pow_le_pow_right- If n > 0 and i ≤ j, then n^i ≤ n^j.
- The inequality 4 ≤ 2^(n-1) is established explicitly to prevent underflow in natural number subtraction (2^(n-1) - 2) when calling the arithmetic solver omega, a formal detail with no counterpart in a standard paper 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.
lemma op1370_sparse_fiber_count (n : ℕ) (hn : 3 ≤ n) (U : Finset (Finset (Fin n))) (x : Fin n) (h0 : (∅ : Finset (Fin n)) ∉ U) (h1 : ({x} : Finset (Fin n)) ∉ U) (h2 : (Finset.univ.erase x : Finset (Fin n)) ∉ U) (h3 : (Finset.univ : Finset (Fin n)) ∉ U) (hover : ((U.filter (fun s => x ∉ s)) ∩ ((U.filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : U.card ≤ 2 ^ (n - 1) - 1 := by open Finset in classical 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) have hpq : P ∪ Q ⊆ V.powerset \ {∅, V} := by intro S hS have hxS : x ∉ S := by rcases mem_union.mp hS with hS | hS · exact (mem_filter.mp hS).2 · obtain ⟨T, hT, rfl⟩ := mem_image.mp hS simp have hsub : S ⊆ V := by intro y hy simp only [V, mem_erase, mem_univ, and_true] exact fun h => hxS (h ▸ hy) have hn0 : S ≠ ∅ := by intro h subst S rcases mem_union.mp hS with hp | hq · exact h0 (mem_filter.mp hp).1 · obtain ⟨T, hT, heq⟩ := mem_image.mp hq have hTx : x ∈ T := (mem_filter.mp hT).2 have hTeq : T = {x} := by have hi := insert_erase hTx rw [heq] at hi simpa using hi.symm exact h1 (hTeq ▸ (mem_filter.mp hT).1) have hnV : S ≠ V := by intro h subst S rcases mem_union.mp hS with hp | hq · exact h2 (mem_filter.mp hp).1 · obtain ⟨T, hT, heq⟩ := mem_image.mp hq have hTx : x ∈ T := (mem_filter.mp hT).2 have hTu : T = univ := by have hi := insert_erase hTx rw [heq] at hi simpa [V] using hi.symm exact h3 (hTu ▸ (mem_filter.mp hT).1) simp only [mem_sdiff, mem_powerset, mem_insert, mem_singleton, not_or] exact ⟨hsub, hn0, hnV⟩ have hVcard : V.card = n - 1 := by simp [V] have hVne : V ≠ ∅ := by intro h have hc := congrArg Finset.card h simp [hVcard] at hc omega have hdel : ({∅, V} : Finset (Finset (Fin n))) ⊆ V.powerset := by rw [insert_subset_iff, singleton_subset_iff] exact ⟨mem_powerset.mpr (empty_subset V), mem_powerset.mpr subset_rfl⟩ have hcarddel : ({∅, V} : Finset (Finset (Fin n))).card = 2 := by simp [hVne.symm] have hbound : (P ∪ Q).card ≤ 2 ^ (n - 1) - 2 := by have h := card_le_card hpq rw [card_sdiff_of_subset hdel, hcarddel, card_powerset, hVcard] at h exact h 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 hPQ := card_union_add_card_inter P Q have hpow : 4 ≤ 2 ^ (n - 1) := by calc 4 = 2 ^ 2 := by norm_num _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by omega) (by omega) change (P ∩ Q).card ≤ 1 at hover omega