op1370_sparse_double_fiber_bound
Let n and t be at least three. For nonempty, uncomplemented, mutually strongly incomparable indexed families of subsets of Fin n, suppose some ground element has at most one erased fiber whose two orientations both belong to the union. Then the total size is at most 2^(n-1)-1.
Statement
theorem op1370_sparse_double_fiber_bound (n t : ℕ) (hn : 3 ≤ n) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hunc : ∀ i, is_uncomplemented (𝒜 i)) (hinc : strongly_incomparable 𝒜) (x : Fin n) (hover : (((Finset.univ.biUnion 𝒜).filter (fun s => x ∉ s)) ∩ (((Finset.univ.biUnion 𝒜).filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1
- Related work
- A conditional bound for Conjecture 4.3 of arXiv:2611.12199: at most one coordinate fiber is doubled.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- strongly_incomparableAn indexed family of finset families
𝒜 : ι → Finset (Finset α)is strongly incomparable if for alli j : ιwithi ≠ j, for all… - op_1370_private_element_boundLet at least three nonempty set families on an n-element ground set be mutually strongly incomparable. Suppose some element occurs in sets…
- op_1370_private_absence_boundAt least three nonempty mutually strongly incomparable families have total size at most 2^(n-1)-1 if an element occurs in every set…
- op1370_sparse_fiber_countFor 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,…
Read back from the Lean
For all natural numbers $n \ge 3$ and $t \ge 3$, and every family $\mathcal{A}$ of $t$ collections of subsets of $\{0, \dots, n-1\}$ (indexed by $\mathrm{Fin}\ t$), assuming: 1. each collection $\mathcal{A}(i)$ is non-empty; 2. each collection $\mathcal{A}(i)$ is uncomplemented (no set in $\mathcal{A}(i)$ has its complement in $\mathcal{A}(i)$); 3. $\mathcal{A}$ is strongly incomparable (for any $i \ne j$, no set in $\mathcal{A}(i)$ is a subset of any set in $\mathcal{A}(j)$); and given an element $x \in \{0, \dots, n-1\}$ such that: 4. the number of sets $s \subseteq \{0, \dots, n-1\} \setminus \{x\}$ for which both $s \in \bigcup_{i} \mathcal{A}(i)$ and $s \cup \{x\} \in \bigcup_{i} \mathcal{A}(i)$ is at most $1$ (expressed as the intersection of sets in the union not containing $x$ with the image under removing $x$ of sets in the union containing $x$ having cardinality $\le 1$), then the sum of the sizes of the collections, $\sum_{i \in \mathrm{Fin}\ t} |\mathcal{A}(i)|$, is at most $2^{n-1} - 1$.
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
We express the total cardinality ∑_i |𝒜_i| as the cardinality of the union U = ⋃_i 𝒜_i, which is disjoint because strong incomparability prevents any two families from sharing a set. Strong incomparability and the assumption t ≥ 3 also guarantee that neither the empty set nor the universal set belongs to U. We then case-split on whether {x} or its complement belongs to U: if either does, that set isolates x in one family, allowing either op_1370_private_element_bound or op_1370_private_absence_bound to bound the total size by 2^(n-1) - 1. If neither does, U contains none of the four trivial sets, and the sparse fiber counting lemma op1370_sparse_fiber_count bounds |U| by 2^(n-1) - 1 directly.
The total size ∑_i |𝒜_i| equals the cardinality of the union U = ⋃_i 𝒜_i.
We define U as the union of all families 𝒜_i. Any two distinct families 𝒜_i and 𝒜_j (with i ≠ j) must be disjoint, since if they shared a set S, then S ⊆ S would contradict strong incomparability. By card_biUnion, the cardinality of the disjoint union U is the sum of the cardinalities of the individual families.
uses
disjoint_left,Subset.refl,card_biUnionopen Finset in classical let U := univ.biUnion 𝒜 have hdisj : ∀ i j : Fin t, i ≠ j → Disjoint (𝒜 i) (𝒜 j) := by intro i j hij rw [disjoint_left] intro S hSi hSj exact hinc i j hij S hSi S hSj (Subset.refl S) have hsum : U.card = ∑ i, (𝒜 i).card := by dsimp [U] rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)]
For every index i, there exists another index j distinct from i.
Since t ≥ 3, the index set Fin t contains at least three elements. Setting j to 1 if i = 0 and to 0 otherwise gives an index in Fin t distinct from i.
uses
congrArghave hother : ∀ i : Fin t, ∃ j : Fin t, j ≠ i := by intro i let j : Fin t := ⟨if i.val = 0 then 1 else 0, by split <;> omega⟩ have hj : j ≠ i := by intro h have hv := congrArg Fin.val h dsimp [j] at hv split at hv <;> omega exact ⟨j, hj⟩
The empty set does not belong to U.
If the empty set belonged to U, it would belong to some family 𝒜_i. Choosing an index j ≠ i and any set T in 𝒜_j (which exists because 𝒜_j is nonempty), we would have ∅ ⊆ T, contradicting the strong incomparability of 𝒜_i and 𝒜_j.
uses
mem_biUnion.mp,empty_subsethave hempty : (∅ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, hji⟩ := hother i obtain ⟨T, hT⟩ := hne j exact hinc i j hji.symm ∅ hi T hT (empty_subset T)
The universal set does not belong to U.
If the universal set belonged to U, it would belong to some family 𝒜_i. Picking an index j ≠ i and any set T in 𝒜_j, we would have T ⊆ univ, which again contradicts strong incomparability.
uses
mem_biUnion.mp,subset_univhave huniv : (univ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, hji⟩ := hother i obtain ⟨T, hT⟩ := hne j exact hinc j i hji T hT univ hi (subset_univ T)
If the singleton {x} belongs to U, the total size is at most 2^(n-1) - 1.
If {x} ∈ U, then {x} belongs to some family 𝒜_i. For every other index j ≠ i and every set T ∈ 𝒜_j, x cannot belong to T, because otherwise {x} ⊆ T, violating strong incomparability. Hence x is absent from all other families, so op_1370_private_element_bound implies the desired bound.
uses
mem_biUnion.mp,op_1370_private_element_bound,singleton_subset_iff.mprby_cases hs : ({x} : Finset (Fin n)) ∈ U · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hs apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT hxT exact hinc i j hji.symm {x} hi T hT (singleton_subset_iff.mpr hxT)
If {x} ∉ U but univ \ {x} ∈ U, the total size is at most 2^(n-1) - 1.
If univ \ {x} belongs to U, it belongs to some family 𝒜_i. For every other index j ≠ i and every set T ∈ 𝒜_j, we must have x ∈ T; otherwise T would be contained in univ \ {x}, violating strong incomparability. Thus every set in every other family contains x, so op_1370_private_absence_bound implies the desired bound.
uses
mem_biUnion.mp,op_1370_private_absence_bound,mem_erase,mem_univ,and_true· by_cases hv : (univ.erase x : Finset (Fin n)) ∈ U · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hv apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT by_contra hxT have hsub : T ⊆ (univ.erase x : Finset (Fin n)) := by intro y hy simp only [mem_erase, mem_univ, and_true] exact fun hyx => hxT (hyx ▸ hy) exact hinc j i hji T hT (univ.erase x) hi hsub
If neither {x} nor univ \ {x} belongs to U, the total size is at most 2^(n-1) - 1.
In the remaining case, U contains none of ∅, {x}, univ \ {x}, or univ. Combined with the assumption hover that at most one fiber has both orientations in U, lemma op1370_sparse_fiber_count implies that |U| ≤ 2^(n-1) - 1. Since |U| equals the total size ∑_i |𝒜_i|, the claim follows.
uses
op1370_sparse_fiber_count· have h := op1370_sparse_fiber_count n hn U x hempty hs hv huniv hover rwa [hsum] at h
and_true- For any proposition P, the conjunction P ∧ True is equivalent to P.
card_biUnion- The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
congrArg- A function applied to equal arguments yields equal results.
disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
empty_subset- The empty set is a subset of every set.
mem_erase- An element belongs to s.erase b if and only if it is distinct from b and belongs to s.
mem_biUnion.mp- An element belongs to a union of sets if and only if it belongs to at least one set in the family (left-to-right implication).
mem_univ- Every element of a finite type belongs to the universal set of that type.
op_1370_private_absence_bound- If an element is present in every set of all other families in a strongly incomparable collection, and the remaining family is uncomplemented, the total cardinality is at most 2^(n-1) - 1.
op_1370_private_element_bound- If a family in a strongly incomparable collection contains an element absent from all sets of all other families, and is uncomplemented, the total cardinality is at most 2^(n-1) - 1.
op1370_sparse_fiber_count- If a family of subsets contains none of ∅, {x}, univ \ {x}, or univ, and at most one fiber at x has both orientations in the family, then its cardinality is at most 2^(n-1) - 1.
singleton_subset_iff.mpr- An element belongs to a set if the singleton containing that element is a subset of the set (the right-to-left direction).
Subset.refl- Every set is a subset of itself.
subset_univ- Every subset of a finite type is a subset of the universal set.
- Constructing a distinct index j ≠ i in Fin t (lines 15 and 20) relies on integer arithmetic automation (omega) to verify that 0 and 1 are valid indices when t ≥ 3.
- The sparse fiber condition hover is expressed formally as the cardinality of the intersection of sets not containing x with the erased images of sets containing x.
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_sparse_double_fiber_bound (n t : ℕ) (hn : 3 ≤ n) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hunc : ∀ i, is_uncomplemented (𝒜 i)) (hinc : strongly_incomparable 𝒜) (x : Fin n) (hover : (((Finset.univ.biUnion 𝒜).filter (fun s => x ∉ s)) ∩ (((Finset.univ.biUnion 𝒜).filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1 := by open Finset in classical let U := univ.biUnion 𝒜 have hdisj : ∀ i j : Fin t, i ≠ j → Disjoint (𝒜 i) (𝒜 j) := by intro i j hij rw [disjoint_left] intro S hSi hSj exact hinc i j hij S hSi S hSj (Subset.refl S) have hsum : U.card = ∑ i, (𝒜 i).card := by dsimp [U] rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)] have hother : ∀ i : Fin t, ∃ j : Fin t, j ≠ i := by intro i let j : Fin t := ⟨if i.val = 0 then 1 else 0, by split <;> omega⟩ have hj : j ≠ i := by intro h have hv := congrArg Fin.val h dsimp [j] at hv split at hv <;> omega exact ⟨j, hj⟩ have hempty : (∅ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, hji⟩ := hother i obtain ⟨T, hT⟩ := hne j exact hinc i j hji.symm ∅ hi T hT (empty_subset T) have huniv : (univ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, hji⟩ := hother i obtain ⟨T, hT⟩ := hne j exact hinc j i hji T hT univ hi (subset_univ T) by_cases hs : ({x} : Finset (Fin n)) ∈ U · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hs apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT hxT exact hinc i j hji.symm {x} hi T hT (singleton_subset_iff.mpr hxT) · by_cases hv : (univ.erase x : Finset (Fin n)) ∈ U · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hv apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT by_contra hxT have hsub : T ⊆ (univ.erase x : Finset (Fin n)) := by intro y hy simp only [mem_erase, mem_univ, and_true] exact fun hyx => hxT (hyx ▸ hy) exact hinc j i hji T hT (univ.erase x) hi hsub · have h := op1370_sparse_fiber_count n hn U x hempty hs hv huniv hover rwa [hsum] at h