op_1370_incomparable_two_sets_card_bound
On an n-element ground set with n at least three, let A and B be incomparable subsets, and let F be an uncomplemented family every member of which is incomparable to both A and B. Then twice the cardinality of F plus six is at most 2 to the power n.
Statement
lemma op_1370_incomparable_two_sets_card_bound
(n : ℕ) (hn : 3 ≤ n) (A B : Finset (Fin n))
(hab : ¬ A ⊆ B) (hba : ¬ B ⊆ A)
(F : Finset (Finset (Fin n))) (hu : is_uncomplemented F)
(hFA : ∀ S ∈ F, ¬ S ⊆ A) (hAF : ∀ S ∈ F, ¬ A ⊆ S)
(hFB : ∀ S ∈ F, ¬ S ⊆ B) (hBF : ∀ S ∈ F, ¬ B ⊆ S) :
2 * F.card + 6 ≤ 2 ^ n- Source
- Counting lemma for OP-1370 and arXiv:2611.12199, Conjecture 4.3.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- Used by 1
- op_1370_three_two_singletonsFor n at least three, if three mutually strongly incomparable families of subsets of an n-element set have their first two families…
The proof, explained
The proof establishes the bound by identifying six specific subsets that cannot belong to the uncomplemented family F nor to its family of complements G: since A and B are incomparable, there exist x ∈ A \ B and y ∈ B \ A with x ≠ y, and incomparability of F with A and B prevents ∅, the full set, {x}, {y}, {x}ᶜ, and {y}ᶜ from belonging to F. Since F is uncomplemented, F and G = {Sᶜ | S ∈ F} are disjoint families of size |F|, and both are disjoint from the 6-element family formed by these six sets; bounding the size of this disjoint union by the total number of subsets 2^n yields 2|F| + 6 ≤ 2^n.
The family of complements G = {sᶜ | s ∈ F} is disjoint from F and has the same cardinality as F.
We define G as the image of F under set complementation. Since F is uncomplemented (no set and its complement can both belong to F), F and G are disjoint. Because complementation is an injective operation on sets, G has the same cardinality as F.
uses
Finset.disjoint_left,Finset.mem_image.mp,Finset.card_image_of_injective,compl_injectiveclassical let G : Finset (Finset (Fin n)) := F.image compl have hdis : Disjoint F G := by rw [Finset.disjoint_left] intro s hs hsg obtain ⟨t, ht, he⟩ := Finset.mem_image.mp hsg subst s exact hu t ht hs have hG : G.card = F.card := Finset.card_image_of_injective _ compl_injective
The six sets ∅, the full set, {x}, {y}, {x}ᶜ, and {y}ᶜ are pairwise distinct.
Since x ≠ y, the singletons {x} and {y} are distinct, and so are their complements {x}ᶜ and {y}ᶜ. Furthermore, since n ≥ 3, the sets fall into distinct cardinality classes: |∅| = 0, |{x}| = |{y}| = 1, |{x}ᶜ| = |{y}ᶜ| = n - 1 ≥ 2, and |univ| = n ≥ 3. Sets with different cardinalities cannot be equal, proving that all six sets are pairwise distinct.
uses
Finset.card_compl,congrArghave hneq1 : ({x} : Finset (Fin n)) ≠ ({y} : Finset (Fin n)) := by simpa using hxy have hneq2 : ({x} : Finset (Fin n))ᶜ ≠ ({y} : Finset (Fin n))ᶜ := by simpa using hneq1 have hlarge : 2 ≤ n - 1 := by omega have hcc (z : Fin n) : (({z} : Finset (Fin n))ᶜ).card = n - 1 := by rw [Finset.card_compl]; simp have hc0 (z : Fin n) : ({z} : Finset (Fin n))ᶜ ≠ ∅ := by intro h have := congrArg Finset.card h simp [hcc] at this omega have hc1 (z : Fin n) : ({z} : Finset (Fin n))ᶜ ≠ univ := by intro h have hmem : z ∈ ({z} : Finset (Fin n))ᶜ := by rw [h]; simp simpa using hmem have hcs (z w : Fin n) : ({z} : Finset (Fin n))ᶜ ≠ {w} := by intro h have := congrArg Finset.card h simp [hcc] at this omega have hEU : (∅ : Finset (Fin n)) ≠ univ := by intro h have := congrArg Finset.card h simp at this omega have hUS (z : Fin n) : (univ : Finset (Fin n)) ≠ {z} := by intro h have := congrArg Finset.card h simp at this omega
The family B = {∅, univ, {x}, {y}, {x}ᶜ, {y}ᶜ} has cardinality 6.
Having established that the six candidate sets are pairwise distinct, inserting them one by one produces no duplicates, so the resulting family B has cardinality 6.
uses
Finset.card_insert_eq_ite,Ne.symmlet B : Finset (Finset (Fin n)) := {∅, univ, {x}, {y}, ({x} : Finset (Fin n))ᶜ, ({y} : Finset (Fin n))ᶜ} have hb : B.card = 6 := by simp [B, Finset.card_insert_eq_ite, hEU, hUS, hneq1, hneq2, hc0, hc1, hcs, Ne.symm hneq1, Ne.symm hneq2, Ne.symm (hc0 x), Ne.symm (hc0 y), Ne.symm (hc1 x), Ne.symm (hc1 y), Ne.symm (hcs x x), Ne.symm (hcs x y), Ne.symm (hcs y x), Ne.symm (hcs y y), hn]
The family B is disjoint from both F and G, and therefore disjoint from F ∪ G.
By assumption, none of the six sets in B belong to F, so B is disjoint from F. If any s ∈ B belonged to G, its complement sᶜ would belong to F. But the complement of each element of B is itself in B (since (∅)ᶜ = univ, ({x})ᶜ = {x}ᶜ, and so on), which would place sᶜ in B ∩ F = ∅, a contradiction. Thus B is disjoint from G, and consequently disjoint from F ∪ G.
uses
Finset.disjoint_left,mem_insert,mem_singleton,mem_image.mp,compl_compl,disjoint_union_right.mprhave hBF : Disjoint B F := by rw [Finset.disjoint_left] intro s hs hsF simp only [B, mem_insert, mem_singleton] at hs rcases hs with rfl | rfl | rfl | rfl | rfl | rfl <;> contradiction have hBG : Disjoint B G := by rw [Finset.disjoint_left] intro s hs hsG obtain ⟨t, ht, hts⟩ := mem_image.mp hsG have htc : t = sᶜ := by rw [← hts, compl_compl] subst t simp only [B, mem_insert, mem_singleton] at hs rcases hs with rfl | rfl | rfl | rfl | rfl | rfl <;> simp_all have hd : Disjoint B (F ∪ G) := disjoint_union_right.mpr ⟨hBF, hBG⟩
2 * |F| + 6 ≤ 2^n.
The families B, F, and G are pairwise disjoint, so the cardinality of their union B ∪ F ∪ G is |B| + |F| + |G| = 6 + 2|F|. This union is a family of subsets of an n-element set, which has 2^n total subsets, giving 2|F| + 6 ≤ 2^n.
uses
Finset.card_le_univ,Finset.card_union_of_disjoint,Finset.card_univ,Finset.powerset_univ,Finset.card_powersethave hcard := Finset.card_le_univ (B ∪ (F ∪ G)) rw [Finset.card_union_of_disjoint hd, Finset.card_union_of_disjoint hdis, hb, hG] at hcard have huniv : Fintype.card (Finset (Fin n)) = 2 ^ n := by rw [← Finset.card_univ, ← Finset.powerset_univ, Finset.card_powerset] simp rw [huniv] at hcard omega
There exist distinct elements x ∈ A \ B and y ∈ B \ A.
Since A is not a subset of B, there exists an element x ∈ A with x ∉ B. Similarly, since B is not a subset of A, there exists an element y ∈ B with y ∉ A. If x = y, then y ∈ A, which contradicts y ∉ A; thus x ≠ y.
uses
Finset.not_subset.mpclassical obtain ⟨x, hxA, hxB⟩ := Finset.not_subset.mp hab obtain ⟨y, hyB, hyA⟩ := Finset.not_subset.mp hba have hxy : x ≠ y := by intro h; subst y; exact hxB hyB
The six sets ∅, univ, {x}, {y}, {x}ᶜ, and {y}ᶜ do not belong to F, and therefore 2 * |F| + 6 ≤ 2^n.
We apply the missing-six lemma with x and y. To satisfy its hypotheses, none of the six sets can belong to F: ∅ ∉ F because ∅ ⊆ A, which would contradict that every member of F is incomparable to A; univ ∉ F because A ⊆ univ, which would contradict that no member of F contains A; {x} ∉ F because {x} ⊆ A (since x ∈ A); {y} ∉ F because {y} ⊆ B (since y ∈ B); {x}ᶜ ∉ F because x ∉ B implies B ⊆ {x}ᶜ, contradicting that no member of F contains B; and {y}ᶜ ∉ F because y ∉ A implies A ⊆ {y}ᶜ, contradicting that no member of F contains A. This establishes all conditions and yields the bound 2|F| + 6 ≤ 2^n.
uses
op_1370_pair_count_missing_six,empty_subset,subset_univ,singleton_subset_iff.mpr,mem_compl,mem_singletonapply op_1370_pair_count_missing_six n hn F hu x y hxy · intro h; exact hFA ∅ h (empty_subset A) · intro h; exact hAF univ h (subset_univ A) · intro h; exact hFA {x} h (singleton_subset_iff.mpr hxA) · intro h; exact hFB {y} h (singleton_subset_iff.mpr hyB) · intro h; apply hBF _ h; intro z hz; simp only [mem_compl, mem_singleton]; intro hzx; subst z; exact hxB hz · intro h; apply hAF _ h; intro z hz; simp only [mem_compl, mem_singleton]; intro hzy; subst z; exact hyA hz
compl_compl- The complement of the complement of a set is the set itself.
compl_injective- Set complementation is an injective function.
congrArg- Equal inputs to a function yield equal outputs.
disjoint_union_right.mpr- If a set is disjoint from two sets, it is disjoint from their union.
empty_subset- The empty set is a subset of any set.
Finset.card_compl- The cardinality of the complement of a subset is the cardinality of the ambient finite set minus the cardinality of the subset.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Finset.card_insert_eq_ite- The cardinality of inserting an element into a finite set is unchanged if the element is already present, and increases by one otherwise.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the universal set.
Finset.card_powerset- The cardinality of the powerset of a finite set of size k is 2^k.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_univ- The cardinality of the universal set on a finite type equals the cardinality of the type.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first set belongs to the second.
Finset.mem_image.mp- If an element belongs to the image of a set under a function, there exists an element in the set mapped to it.
Finset.not_subset.mp- If a finite set is not a subset of another, there is an element in the first set that is not in the second.
Finset.powerset_univ- The powerset of the universal set of a finite type is the universal set of all subsets.
mem_compl- An element belongs to the complement of a set if and only if it is not in the set.
mem_image.mp- If an element belongs to the image of a set under a function, there exists an element in the set mapped to it.
mem_insert- An element belongs to an insert if and only if it equals the inserted element or belongs to the base set.
mem_singleton- An element belongs to a singleton set if and only if it is equal to the singleton's element.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
op_1370_pair_count_missing_six- For an uncomplemented family F on an n-element set with n ≥ 3, if F omits the empty set, the full set, two distinct singletons, and their complements, then 2|F| + 6 ≤ 2^n.
singleton_subset_iff.mpr- If an element belongs to a set, then its singleton is a subset of that set.
subset_univ- Every subset of a finite type is a subset of the universal set.
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.
open Finsetset_option maxHeartbeats 800000lemma op_1370_pair_count_missing_six (n : ℕ) (hn : 3 ≤ n) (F : Finset (Finset (Fin n))) (hu : is_uncomplemented F) (x y : Fin n) (hxy : x ≠ y) (h0 : (∅ : Finset (Fin n)) ∉ F) (h1 : (univ : Finset (Fin n)) ∉ F) (hx : ({x} : Finset (Fin n)) ∉ F) (hy : ({y} : Finset (Fin n)) ∉ F) (hxc : ({x} : Finset (Fin n))ᶜ ∉ F) (hyc : ({y} : Finset (Fin n))ᶜ ∉ F) : 2 * F.card + 6 ≤ 2 ^ n := by classical let G : Finset (Finset (Fin n)) := F.image compl have hdis : Disjoint F G := by rw [Finset.disjoint_left] intro s hs hsg obtain ⟨t, ht, he⟩ := Finset.mem_image.mp hsg subst s exact hu t ht hs have hG : G.card = F.card := Finset.card_image_of_injective _ compl_injective have hneq1 : ({x} : Finset (Fin n)) ≠ ({y} : Finset (Fin n)) := by simpa using hxy have hneq2 : ({x} : Finset (Fin n))ᶜ ≠ ({y} : Finset (Fin n))ᶜ := by simpa using hneq1 have hlarge : 2 ≤ n - 1 := by omega have hcc (z : Fin n) : (({z} : Finset (Fin n))ᶜ).card = n - 1 := by rw [Finset.card_compl]; simp have hc0 (z : Fin n) : ({z} : Finset (Fin n))ᶜ ≠ ∅ := by intro h have := congrArg Finset.card h simp [hcc] at this omega have hc1 (z : Fin n) : ({z} : Finset (Fin n))ᶜ ≠ univ := by intro h have hmem : z ∈ ({z} : Finset (Fin n))ᶜ := by rw [h]; simp simpa using hmem have hcs (z w : Fin n) : ({z} : Finset (Fin n))ᶜ ≠ {w} := by intro h have := congrArg Finset.card h simp [hcc] at this omega have hEU : (∅ : Finset (Fin n)) ≠ univ := by intro h have := congrArg Finset.card h simp at this omega have hUS (z : Fin n) : (univ : Finset (Fin n)) ≠ {z} := by intro h have := congrArg Finset.card h simp at this omega let B : Finset (Finset (Fin n)) := {∅, univ, {x}, {y}, ({x} : Finset (Fin n))ᶜ, ({y} : Finset (Fin n))ᶜ} have hb : B.card = 6 := by simp [B, Finset.card_insert_eq_ite, hEU, hUS, hneq1, hneq2, hc0, hc1, hcs, Ne.symm hneq1, Ne.symm hneq2, Ne.symm (hc0 x), Ne.symm (hc0 y), Ne.symm (hc1 x), Ne.symm (hc1 y), Ne.symm (hcs x x), Ne.symm (hcs x y), Ne.symm (hcs y x), Ne.symm (hcs y y), hn] have hBF : Disjoint B F := by rw [Finset.disjoint_left] intro s hs hsF simp only [B, mem_insert, mem_singleton] at hs rcases hs with rfl | rfl | rfl | rfl | rfl | rfl <;> contradiction have hBG : Disjoint B G := by rw [Finset.disjoint_left] intro s hs hsG obtain ⟨t, ht, hts⟩ := mem_image.mp hsG have htc : t = sᶜ := by rw [← hts, compl_compl] subst t simp only [B, mem_insert, mem_singleton] at hs rcases hs with rfl | rfl | rfl | rfl | rfl | rfl <;> simp_all have hd : Disjoint B (F ∪ G) := disjoint_union_right.mpr ⟨hBF, hBG⟩ have hcard := Finset.card_le_univ (B ∪ (F ∪ G)) rw [Finset.card_union_of_disjoint hd, Finset.card_union_of_disjoint hdis, hb, hG] at hcard have huniv : Fintype.card (Finset (Fin n)) = 2 ^ n := by rw [← Finset.card_univ, ← Finset.powerset_univ, Finset.card_powerset] simp rw [huniv] at hcard omegalemma op_1370_incomparable_two_sets_card_bound (n : ℕ) (hn : 3 ≤ n) (A B : Finset (Fin n)) (hab : ¬ A ⊆ B) (hba : ¬ B ⊆ A) (F : Finset (Finset (Fin n))) (hu : is_uncomplemented F) (hFA : ∀ S ∈ F, ¬ S ⊆ A) (hAF : ∀ S ∈ F, ¬ A ⊆ S) (hFB : ∀ S ∈ F, ¬ S ⊆ B) (hBF : ∀ S ∈ F, ¬ B ⊆ S) : 2 * F.card + 6 ≤ 2 ^ n := by classical obtain ⟨x, hxA, hxB⟩ := Finset.not_subset.mp hab obtain ⟨y, hyB, hyA⟩ := Finset.not_subset.mp hba have hxy : x ≠ y := by intro h; subst y; exact hxB hyB apply op_1370_pair_count_missing_six n hn F hu x y hxy · intro h; exact hFA ∅ h (empty_subset A) · intro h; exact hAF univ h (subset_univ A) · intro h; exact hFA {x} h (singleton_subset_iff.mpr hxA) · intro h; exact hFB {y} h (singleton_subset_iff.mpr hyB) · intro h; apply hBF _ h; intro z hz; simp only [mem_compl, mem_singleton]; intro hzx; subst z; exact hxB hz · intro h; apply hAF _ h; intro z hz; simp only [mem_compl, mem_singleton]; intro hzy; subst z; exact hyA hz