op1370_two_set_complement_block_bound
Let n be at least three and let indexed families of subsets of Fin n be mutually strongly incomparable. Suppose there is a coordinate x such that for every nonempty family, some set {x,y} occurs in a different family and its complement occurs in a different family; these two other families may coincide. Then the total size of all families is at most 2^(n-1)-2.
Statement
theorem op1370_two_set_complement_block_bound (n t : ℕ) (hn : 3 ≤ n)
(𝒜 : Fin t → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
(x : Fin n)
(hblock : ∀ i : Fin t, (𝒜 i).Nonempty → ∃ j k : Fin t, j ≠ i ∧ k ≠ i ∧
∃ y : Fin n, ({x, y} : Finset (Fin n)) ∈ 𝒜 j ∧ ({x, y} : Finset (Fin n))ᶜ ∈ 𝒜 k) :
∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 2- Related work
- A conditional two-set deficit toward Conjecture 4.3 of arXiv:2611.12199, without uncomplementedness or nonemptiness assumptions.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- strongly_incomparableAn indexed family of finset families
𝒜 : ι → Finset (Finset α)is strongly incomparable if for alli j : ιwithi ≠ j, for all… - op1370_zero_fiber_countFor n at least three, if a family of subsets of Fin n omits the empty set, {x}, its complement, and the full set, and no x-erased fiber…
- strongly_incomparableAn indexed family of finset families
Read back from the Lean
Let $n, t$ be natural numbers with $n \ge 3$. Let $\mathcal{A} : \mathrm{Fin}(t) \to \mathrm{Finset}(\mathrm{Finset}(\mathrm{Fin}(n)))$ be a family of $t$ collections of subsets of $\mathrm{Fin}(n)$. Assume $\mathcal{A}$ is strongly incomparable (for all distinct $i, j \in \mathrm{Fin}(t)$, no set in $\mathcal{A}(i)$ is a subset of any set in $\mathcal{A}(j)$). Let $x \in \mathrm{Fin}(n)$ be fixed. Assume that for every $i \in \mathrm{Fin}(t)$, if $\mathcal{A}(i)$ is nonempty, then there exist indices $j, k \in \mathrm{Fin}(t)$ with $j \ne i$ and $k \ne i$, and an element $y \in \mathrm{Fin}(n)$, such that $\{x, y\} \in \mathcal{A}(j)$ and $\{x, y\}^c \in \mathcal{A}(k)$ (where the complement is with respect to $\mathrm{Fin}(n)$). Then the total number of sets $\sum_{i \in \mathrm{Fin}(t)} |\mathcal{A}(i)|$ is at most $2^{n - 1} - 2$.
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
The proof combines all families into their union U = ⋃ i, 𝒜 i, which has size ∑ i, #(𝒜 i) because strong incomparability forces distinct families to be disjoint. By leveraging the blocking pairs {x, y} ∈ 𝒜 j and {x, y}ᶜ ∈ 𝒜 k (with j, k ≠ i), strong incomparability prevents U from containing ∅, {x}, univ.erase x, or univ, and also prevents any set S ∉ U from having both S and S ∪ {x} in U. This zero fiber overlap allows the counting lemma op1370_zero_fiber_count to directly supply the upper bound 2^(n-1) - 2.
Let U be the union of all families 𝒜 i for i : Fin t.
We define U := univ.biUnion 𝒜 as the collection of all subsets of Fin n appearing in any family 𝒜 i.
open Finset in classical let U := univ.biUnion 𝒜
Distinct families 𝒜 i and 𝒜 j (with i ≠ j) are mutually disjoint.
If some set S were in both 𝒜 i and 𝒜 j for i ≠ j, then S ⊆ S would contradict the strong incomparability assumption between distinct families.
uses
disjoint_left,Subset.reflhave 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)
The cardinality of U is the sum of the cardinalities of the families 𝒜 i.
Since the families are pairwise disjoint, the size of their union equals the sum of their individual sizes.
uses
card_biUnionhave hsum : U.card = ∑ i, (𝒜 i).card := by dsimp [U] rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)]
The empty set ∅ does not belong to U.
If ∅ ∈ U, then ∅ ∈ 𝒜 i for some i. By the blocking hypothesis, there is an index j ≠ i and an element y such that {x, y} ∈ 𝒜 j. But ∅ ⊆ {x, y}, contradicting strong incomparability between 𝒜 i and 𝒜 j.
uses
mem_biUnion,empty_subsethave hempty : (∅ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨∅, hi⟩ exact hinc i j hji.symm ∅ hi {x, y} hw (empty_subset _)
The universal set univ does not belong to U.
If univ ∈ U, then univ ∈ 𝒜 i for some i. The blocking hypothesis gives j ≠ i and y such that {x, y} ∈ 𝒜 j. But {x, y} ⊆ univ, contradicting strong incomparability between 𝒜 j and 𝒜 i.
uses
mem_biUnion,subset_univhave huniv : (univ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ, hi⟩ exact hinc j i hji {x, y} hw univ hi (subset_univ _)
The singleton {x} does not belong to U.
If {x} ∈ U, then {x} ∈ 𝒜 i for some i. The blocking hypothesis gives j ≠ i and y with {x, y} ∈ 𝒜 j. But {x} ⊆ {x, y}, contradicting strong incomparability between 𝒜 i and 𝒜 j.
uses
mem_biUnionhave hx : ({x} : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨{x}, hi⟩ have hsub : ({x} : Finset (Fin n)) ⊆ {x, y} := by simp exact hinc i j hji.symm {x} hi {x, y} hw hsub
The co-singleton univ.erase x does not belong to U.
If univ.erase x ∈ U, it belongs to 𝒜 i for some i. By the blocking hypothesis, there is k ≠ i and y such that {x, y}ᶜ ∈ 𝒜 k. Since x ∉ {x, y}ᶜ, every element of {x, y}ᶜ is in univ.erase x, so {x, y}ᶜ ⊆ univ.erase x. This contradicts strong incomparability between 𝒜 k and 𝒜 i.
uses
mem_biUnion,mem_erase,mem_univ,mem_complhave hV : (univ.erase x : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ.erase x, hi⟩ have hsub : ({x, y} : Finset (Fin n))ᶜ ⊆ univ.erase x := by intro z hz rw [mem_erase] refine ⟨?_, mem_univ _⟩ intro hzx subst z exact (mem_compl.mp hz) (by simp) exact hinc k i hki ({x,y} : Finset (Fin n))ᶜ hc (univ.erase x) hi hsub
For any set S ∈ U not containing x, the augmented set S ∪ {x} does not belong to U.
Suppose S ∈ U (with x ∉ S) and S ∪ {x} ∈ U. If S and S ∪ {x} were in different families 𝒜 i and 𝒜 i', then S ⊆ S ∪ {x} would contradict strong incomparability; hence both belong to the same family 𝒜 i. By the blocking hypothesis on 𝒜 i, there exist j, k ≠ i and y such that {x, y} ∈ 𝒜 j and {x, y}ᶜ ∈ 𝒜 k. If y were in S, then {x, y} ⊆ S ∪ {x}, contradicting strong incomparability between 𝒜 j and 𝒜 i. Hence y ∉ S. But since neither x nor y is in S, we have S ⊆ {x, y}ᶜ, contradicting strong incomparability between 𝒜 i and 𝒜 k.
uses
mem_biUnion,subset_insert,mem_insert,mem_singleton,mem_insert_self,mem_insert_of_mem,mem_compl,not_orhave hno : ∀ S ∈ U, x ∉ S → insert x S ∉ U := by intro S hS hxS hSx obtain ⟨i, _, hSi⟩ := mem_biUnion.mp hS obtain ⟨i', _, hSxi⟩ := mem_biUnion.mp hSx have heq : i = i' := by by_contra hne exact hinc i i' hne S hSi (insert x S) hSxi (subset_insert x S) subst i' obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨S, hSi⟩ have hy : y ∉ S := by intro hyS have hsub : ({x,y} : Finset (Fin n)) ⊆ insert x S := by intro z hz simp only [mem_insert, mem_singleton] at hz rcases hz with rfl | rfl · exact mem_insert_self _ _ · exact mem_insert_of_mem hyS exact hinc j i hji {x,y} hw (insert x S) hSxi hsub have hsub : S ⊆ ({x,y} : Finset (Fin n))ᶜ := by intro z hz rw [mem_compl] simp only [mem_insert, mem_singleton, not_or] exact ⟨fun hzx => hxS (hzx ▸ hz), fun hzy => hy (hzy ▸ hz)⟩ exact hinc i k hki.symm S hSi ({x,y} : Finset (Fin n))ᶜ hc hsub
The fiber overlap at coordinate x has cardinality 0.
Any element in the intersection of {S ∈ U | x ∉ S} and {T \ {x} | T ∈ U, x ∈ T} would be a set S ∈ U with x ∉ S such that S ∪ {x} = T ∈ U. But the previous step showed no such pair can exist in U. Therefore, the intersection is empty and its cardinality is 0.
uses
card_eq_zero,eq_empty_iff_forall_notMem,mem_inter,mem_filter,mem_image,insert_erasehave hover : ((U.filter (fun S => x ∉ S)) ∩ ((U.filter (fun S => x ∈ S)).image (fun S => S.erase x))).card = 0 := by apply card_eq_zero.mpr rw [eq_empty_iff_forall_notMem] intro S hS obtain ⟨hP, hQ⟩ := mem_inter.mp hS have hSU : S ∈ U := (mem_filter.mp hP).1 have hxS : x ∉ S := (mem_filter.mp hP).2 obtain ⟨T, hT, hTS⟩ := mem_image.mp hQ have hTU : T ∈ U := (mem_filter.mp hT).1 have hxT : x ∈ T := (mem_filter.mp hT).2 have hTeq : T = insert x S := by have he := insert_erase hxT rw [hTS] at he exact he.symm exact hno S hSU hxS (hTeq ▸ hTU)
The total size ∑ i, #(𝒜 i) is at most 2^(n-1) - 2.
Applying the lemma op1370_zero_fiber_count to U and x with the facts that ∅, {x}, univ.erase x, univ ∉ U and that the fiber overlap is 0 yields #U ≤ 2^(n-1) - 2. Substituting #U = ∑ i, #(𝒜 i) completes the proof.
uses
op1370_zero_fiber_counthave h := op1370_zero_fiber_count n hn U x hempty hx hV huniv hover rwa [hsum] at h
disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Subset.refl- Every set is a subset of itself.
card_biUnion- The cardinality of a pairwise disjoint union of finite sets is the sum of their cardinalities.
mem_biUnion- An element belongs to a union of families if and only if it belongs to at least one family in the collection.
empty_subset- The empty set is a subset of every set.
subset_univ- Every set in a finite universe is a subset of the universal set.
mem_erase- An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
mem_univ- Every element belongs to the universal set.
mem_compl- An element belongs to the complement of s if and only if it does not belong to s.
subset_insert- Any set s is a subset of insert a s.
mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
mem_insert_self- An element a belongs to insert a s.
mem_insert_of_mem- If an element belongs to s, then it belongs to insert b s.
not_or- The negation of a disjunction is the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
eq_empty_iff_forall_notMem- A set is empty if and only if it contains no elements.
mem_inter- An element belongs to the intersection of two sets if and only if it belongs to both.
mem_filter- An element belongs to filter p s if and only if it belongs to s and satisfies predicate p.
mem_image- An element belongs to image f s if and only if it is the image of some element in s.
insert_erase- Reinserting an element into a set from which it was removed recovers the set, provided the element was originally in the set.
op1370_zero_fiber_count- For n ≥ 3, any family of subsets of Fin n that omits ∅, {x}, univ.erase x, and univ, and has zero fiber overlap at coordinate x, has size at most 2^(n-1) - 2.
- The final bound relies on the helper lemma op1370_zero_fiber_count from the same knowledge base, which bounds the size of any family of subsets of Fin n (for n ≥ 3) that omits ∅, {x}, Finset.univ.erase x, and Finset.univ, and has zero overlap between fibers above and below coordinate 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_two_set_complement_block_bound (n t : ℕ) (hn : 3 ≤ n) (𝒜 : Fin t → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜) (x : Fin n) (hblock : ∀ i : Fin t, (𝒜 i).Nonempty → ∃ j k : Fin t, j ≠ i ∧ k ≠ i ∧ ∃ y : Fin n, ({x, y} : Finset (Fin n)) ∈ 𝒜 j ∧ ({x, y} : Finset (Fin n))ᶜ ∈ 𝒜 k) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 2 := 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 hempty : (∅ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨∅, hi⟩ exact hinc i j hji.symm ∅ hi {x, y} hw (empty_subset _) have huniv : (univ : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ, hi⟩ exact hinc j i hji {x, y} hw univ hi (subset_univ _) have hx : ({x} : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨{x}, hi⟩ have hsub : ({x} : Finset (Fin n)) ⊆ {x, y} := by simp exact hinc i j hji.symm {x} hi {x, y} hw hsub have hV : (univ.erase x : Finset (Fin n)) ∉ U := by intro h obtain ⟨i, _, hi⟩ := mem_biUnion.mp h obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ.erase x, hi⟩ have hsub : ({x, y} : Finset (Fin n))ᶜ ⊆ univ.erase x := by intro z hz rw [mem_erase] refine ⟨?_, mem_univ _⟩ intro hzx subst z exact (mem_compl.mp hz) (by simp) exact hinc k i hki ({x,y} : Finset (Fin n))ᶜ hc (univ.erase x) hi hsub have hno : ∀ S ∈ U, x ∉ S → insert x S ∉ U := by intro S hS hxS hSx obtain ⟨i, _, hSi⟩ := mem_biUnion.mp hS obtain ⟨i', _, hSxi⟩ := mem_biUnion.mp hSx have heq : i = i' := by by_contra hne exact hinc i i' hne S hSi (insert x S) hSxi (subset_insert x S) subst i' obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨S, hSi⟩ have hy : y ∉ S := by intro hyS have hsub : ({x,y} : Finset (Fin n)) ⊆ insert x S := by intro z hz simp only [mem_insert, mem_singleton] at hz rcases hz with rfl | rfl · exact mem_insert_self _ _ · exact mem_insert_of_mem hyS exact hinc j i hji {x,y} hw (insert x S) hSxi hsub have hsub : S ⊆ ({x,y} : Finset (Fin n))ᶜ := by intro z hz rw [mem_compl] simp only [mem_insert, mem_singleton, not_or] exact ⟨fun hzx => hxS (hzx ▸ hz), fun hzy => hy (hzy ▸ hz)⟩ exact hinc i k hki.symm S hSi ({x,y} : Finset (Fin n))ᶜ hc hsub have hover : ((U.filter (fun S => x ∉ S)) ∩ ((U.filter (fun S => x ∈ S)).image (fun S => S.erase x))).card = 0 := by apply card_eq_zero.mpr rw [eq_empty_iff_forall_notMem] intro S hS obtain ⟨hP, hQ⟩ := mem_inter.mp hS have hSU : S ∈ U := (mem_filter.mp hP).1 have hxS : x ∉ S := (mem_filter.mp hP).2 obtain ⟨T, hT, hTS⟩ := mem_image.mp hQ have hTU : T ∈ U := (mem_filter.mp hT).1 have hxT : x ∈ T := (mem_filter.mp hT).2 have hTeq : T = insert x S := by have he := insert_erase hxT rw [hTS] at he exact he.symm exact hno S hSU hxS (hTeq ▸ hTU) have h := op1370_zero_fiber_count n hn U x hempty hx hV huniv hover rwa [hsum] at h