op_1370_four_elements_bound
Any at least three nonempty uncomplemented mutually strongly incomparable families on a four-element ground set have total size at most seven.
Statement
theorem op_1370_four_elements_bound (t : β) (ht : 3 β€ t) (π : Fin t β Finset (Finset (Fin 4))) (hne : β i, (π i).Nonempty) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 7- Related work
- arXiv:2611.12199, Conjecture 4.3, specialized to a four-element ground set.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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β¦
Read back from the Lean
For any natural number $t \ge 3$ and any family $\mathcal{A} = (\mathcal{A}_i)_{i \in \{0, \dots, t-1\}}$ of finite sets of subsets of $\{0, 1, 2, 3\}$, if: 1. each $\mathcal{A}_i$ is nonempty; 2. each $\mathcal{A}_i$ is uncomplemented (for every $A \in \mathcal{A}_i$, its complement $A^c$ in $\{0, 1, 2, 3\}$ is not in $\mathcal{A}_i$); and 3. $\mathcal{A}$ is strongly incomparable (for all distinct indices $i \ne j$, no set $A \in \mathcal{A}_i$ is a subset of any set $B \in \mathcal{A}_j$), then the sum of the cardinalities of all the $\mathcal{A}_i$, $\sum_{i=0}^{t-1} |\mathcal{A}_i|$, is at most $7$.
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 classifies the sets in the families by their cardinality. Strong incomparability and nonemptiness rule out the empty set and the entire ground set, so every set has size 1, 2, or 3. If any family contains a singleton, that element cannot belong to any set in any other family, and an existing private-element bound limits the total size to at most 2^(4 - 1) - 1 = 7. If no singletons exist but some family contains a 3-element set, taking set complements dualizes the system into an equivalent collection containing a singleton, yielding the same bound of 7. Finally, if all sets have size 2, strong incomparability forces the families to be pairwise disjoint subsets of the (4 choose 2) = 6 possible pairs, so their total size is at most 6.
For each index i, there exists a distinct index j β i.
The index set has size t β₯ 3. Removing i from the full set of t indices leaves t - 1 β₯ 2 elements, which is strictly greater than 1. By the pigeonhole principle on finite sets, there exist at least two distinct elements in the remainder, so we can pick one, j, which is distinct from i.
uses
Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_univ,Fintype.card_fin,Finset.one_lt_card.mp,Finset.mem_erase.mpclassical have hother : β i : Fin t, β j : Fin t, j β i := by intro i have hcard : 1 < (Finset.univ.erase i).card := by rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] omega obtain β¨j, hj, k, hk, hjkβ© := Finset.one_lt_card.mp hcard exact β¨j, (Finset.mem_erase.mp hj).1β©
No family π i contains the empty set.
Suppose for contradiction that β β π i. Since t β₯ 3, there is another index j β i, and because π j is nonempty, it contains some set B. Then β β B, which violates strong incomparability between π i and π j.
uses
Ne.symm,Finset.empty_subsethave hempty : β i, (β : Finset (Fin 4)) β π i := by intro i hi obtain β¨j, hjiβ© := hother i obtain β¨B, hBβ© := hne j exact hinc i j (Ne.symm hji) β hi B hB (Finset.empty_subset B)
No family π i contains the whole ground set.
Suppose for contradiction that the entire ground set belongs to π i. Choosing another index j β i and any set B β π j, we have B β univ, which contradicts strong incomparability from π j to π i.
uses
Finset.subset_univhave huniv : β i, (Finset.univ : Finset (Fin 4)) β π i := by intro i hi obtain β¨j, hjiβ© := hother i obtain β¨B, hBβ© := hne j exact hinc j i hji B hB Finset.univ hi (Finset.subset_univ B)
Every set in every family π i has cardinality 1, 2, or 3.
Let S β π i. Its cardinality cannot be 0, because S = β was ruled out. It is at most 4 since the ground set has 4 elements. Nor can it be 4, because any 4-element subset of a 4-element set is the entire universal set, which was also ruled out. Hence |S| β {1, 2, 3}.
uses
Finset.card_eq_zero,Finset.card_le_univ,Finset.eq_univ_of_cardhave hcard3 : β i (S : Finset (Fin 4)) (hS : S β π i), S.card = 1 β¨ S.card = 2 β¨ S.card = 3 := by intro i S hS have h0 : S.card β 0 := by intro h rw [Finset.card_eq_zero] at h rw [h] at hS exact hempty i hS have hle : S.card β€ 4 := by have := Finset.card_le_univ S simpa using this have h4 : S.card β 4 := by intro h have hS4 : S.card = Fintype.card (Fin 4) := by simpa using h have hSu : S = Finset.univ := Finset.eq_univ_of_card S hS4 rw [hSu] at hS exact huniv i hS omega
If some family contains a 1-element set, the sum of cardinalities across all families is at most 7.
Suppose some π i contains a singleton S = {x}. For any j β i and any T β π j, we cannot have x β T, because that would imply {x} β T, violating strong incomparability. Thus x is a private element for π i. Applying the lemma op_1370_private_element_bound gives β_j |π j| β€ 2^(4 - 1) - 1 = 7.
uses
Finset.card_eq_one.mp,Ne.symm,Finset.singleton_subset_iff.mpr,op_1370_private_element_boundby_cases hSingle : β i : Fin t, β S β π i, S.card = 1 Β· obtain β¨i, S, hS, hScard1β© := hSingle obtain β¨x, hxeqβ© := Finset.card_eq_one.mp hScard1 have hx : β j, j β i β β T β π j, x β T := by intro j hji T hT hxT exact hinc i j (Ne.symm hji) S hS T hT (by rw [hxeq]; exact Finset.singleton_subset_iff.mpr hxT) have hb := op_1370_private_element_bound 4 t ht π hne hinc i x (hunc i) hx norm_num at hb exact hb
In the case where no singletons exist but some family contains a 3-element set, the complemented families β¬ i = {SαΆ : S β π i} are nonempty, equicardinal to π i, uncomplemented, and strongly incomparable.
Define β¬ i as the image of π i under set complementation. Nonemptiness follows from nonemptiness of π i. Since complementation on subsets of a finite set is injective, each |β¬ i| = |π i|. Uncomplementedness of β¬ i follows because a complementary pair in β¬ i would pull back to a complementary pair in π i. Finally, β¬ is strongly incomparable: if SαΆ β TαΆ for S β π i and T β π j with i β j, taking complements reverses the inclusion to T β S, which contradicts strong incomparability of π.
uses
Finset.mem_image.mpr,Finset.card_image_of_injOn,congrArg,Finset.mem_image.mp,Ne.symm,Finset.compl_subset_compl.mpΒ· by_cases hThree : β i : Fin t, β S β π i, S.card = 3 Β· obtain β¨i0, S0, hS0, hS0cardβ© := hThree let β¬ : Fin t β Finset (Finset (Fin 4)) := fun i => (π i).image compl have hBne : β i, (β¬ i).Nonempty := by intro i obtain β¨S, hSβ© := hne i exact β¨SαΆ, Finset.mem_image.mpr β¨S, hS, rflβ©β© have hBcard : β i, (β¬ i).card = (π i).card := by intro i apply Finset.card_image_of_injOn intro a _ b _ hab have := congrArg compl hab simpa using this have hBunc : β i, is_uncomplemented (β¬ i) := by intro i A hA hAc obtain β¨B, hB, rflβ© := Finset.mem_image.mp hA obtain β¨C, hC, hCeqβ© := Finset.mem_image.mp hAc have hCB : C = BαΆ := by have := congrArg compl hCeq simpa using this rw [hCB] at hC exact hunc i B hB hC have hBinc : strongly_incomparable β¬ := by intro i j hij A hA B' hB' obtain β¨S, hS, rflβ© := Finset.mem_image.mp hA obtain β¨T, hT, rflβ© := Finset.mem_image.mp hB' intro hsub exact hinc j i (Ne.symm hij) T hT S hS (Finset.compl_subset_compl.mp hsub)
In the 3-element set case, the total cardinality across all families is at most 7.
The complement SβαΆ of the 3-element set Sβ β π iβ has cardinality 4 - 3 = 1, so SβαΆ = {x} is a singleton in β¬ iβ. By strong incomparability of β¬, x belongs to no set of β¬ j for any j β iβ, making x a private element for β¬ iβ. Applying op_1370_private_element_bound to β¬ yields β_j |β¬ j| β€ 2^(4 - 1) - 1 = 7. Since |β¬ j| = |π j| for each j, the same bound holds for the original families.
uses
Finset.card_compl,Fintype.card_fin,Finset.card_eq_one.mp,Finset.mem_image.mpr,Ne.symm,Finset.singleton_subset_iff.mpr,op_1370_private_element_bound,Finset.sum_congrhave hScard : S0αΆ.card = 1 := by rw [Finset.card_compl, Fintype.card_fin] omega obtain β¨x, hxeqβ© := Finset.card_eq_one.mp hScard have hmem : ({(x)} : Finset (Fin 4)) β β¬ i0 := by exact Finset.mem_image.mpr β¨S0, hS0, hxeqβ© have hx : β j, j β i0 β β T β β¬ j, x β T := by intro j hji T hT hxT exact hBinc i0 j (Ne.symm hji) {(x)} hmem T hT (Finset.singleton_subset_iff.mpr hxT) have hb := op_1370_private_element_bound 4 t ht β¬ hBne hBinc i0 x (hBunc i0) hx norm_num at hb have hsum : β j, (β¬ j).card = β j, (π j).card := by apply Finset.sum_congr rfl intro j _ exact hBcard j rw [hsum] at hb exact hb
When neither 1-element sets nor 3-element sets exist, every set in every family has size exactly 2.
Every set has size 1, 2, or 3. Since the existence of singletons and 3-element sets has been ruled out by the preceding case analyses, every set must have size 2.
Β· have hall2 : β i (S : Finset (Fin 4)) (hS : S β π i), S.card = 2 := by intro i S hS have h := hcard3 i S hS rcases h with h | h | h Β· exact absurd β¨i, S, hS, hβ© hSingle Β· exact h Β· exact absurd β¨i, S, hS, hβ© hThree
When all sets have size 2, the families are pairwise disjoint subsets of the 2-subsets of a 4-element set, so their total cardinality is at most 6 β€ 7.
If two distinct families π i and π j shared a set S, then S β S would violate strong incomparability; thus the families are mutually disjoint. The cardinality of their union therefore equals the sum of their individual sizes. Since every element in the union has size 2, the union is a subset of the collection of all 2-element subsets of a 4-element set, which has size (4 choose 2) = 6. Hence β_i |π i| β€ 6 β€ 7.
uses
Finset.disjoint_left,Finset.Subset.refl,Finset.card_biUnion,Finset.mem_powersetCard,Finset.mem_biUnion.mp,Finset.subset_univ,Finset.card_powersetCard,Finset.card_univ,Fintype.card_fin,Finset.card_le_cardhave hdisj : β i j : Fin t, i β j β Disjoint (π i) (π j) := by intro i j hij rw [Finset.disjoint_left] intro S hi hj exact hinc i j hij S hi S hj (Finset.Subset.refl S) have hsumEq : (Finset.univ.biUnion π).card = β i, (π i).card := by rw [Finset.card_biUnion (fun i _ j _ hij => hdisj i j hij)] have hsub : Finset.univ.biUnion π β Finset.univ.powersetCard 2 := by intro S hS rw [Finset.mem_powersetCard] obtain β¨i, _, hiSβ© := Finset.mem_biUnion.mp hS exact β¨Finset.subset_univ S, hall2 i S hiSβ© have hcard6 : (Finset.univ.powersetCard 2 : Finset (Finset (Fin 4))).card = 6 := by rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] decide have hle := Finset.card_le_card hsub rw [hcard6] at hle rw [hsumEq] at hle omega
Finset.card_erase_of_mem- Removing an element a from a finite set s (where a β s) decreases the cardinality of s by 1.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ of that type.
Finset.card_univ- The cardinality of the universal set Finset.univ of a finite type equals the number of elements in that type.
Fintype.card_fin- The standard finite type Fin n has cardinality n.
Finset.one_lt_card.mp- If a finite set has cardinality strictly greater than 1, then it contains at least two distinct elements.
Finset.mem_erase.mp- If an element belongs to s with a removed, then it is not equal to a and belongs to s.
Ne.symm- Inequality is symmetric: if a β b, then b β a.
Finset.empty_subset- The empty set is a subset of every finite set.
Finset.subset_univ- Every finite set is a subset of the universal set of its element type.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is the empty set.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the total cardinality of that type.
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals that of the entire type is the universal set.
Finset.card_eq_one.mp- If a finite set has cardinality 1, then it is a singleton {a} for some element a.
Finset.singleton_subset_iff.mpr- An element belongs to a set if and only if the corresponding singleton is a subset of that set.
op_1370_private_element_bound- For at least three nonempty strongly incomparable families on an n-element ground set, if one uncomplemented family contains a private element that belongs to no set in any other family, then the total cardinality across all families is at most 2^(n-1) - 1.
Finset.mem_image.mpr- If an element is the image of some element of s under f, then it belongs to the image f(s).
Finset.card_image_of_injOn- If a function f is injective on a finite set s, then the image f(s) has the same cardinality as s.
congrArg- Applying a function to equal arguments produces equal results.
Finset.mem_image.mp- If an element belongs to the image f(s), then it is of the form f(a) for some a β s.
Finset.compl_subset_compl.mp- If the complement of A is a subset of the complement of B, then B is a subset of A.
Finset.card_compl- The cardinality of the complement of a subset is the ambient ground set cardinality minus the subset's cardinality.
Finset.sum_congr- Sums of two functions over the same finite set are equal if their values agree at each element.
Finset.disjoint_left- Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.Subset.refl- Every set is a subset of itself.
Finset.card_biUnion- The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
Finset.mem_powersetCard- A set belongs to the collection of n-element subsets of s if and only if it is a subset of s and has cardinality n.
Finset.mem_biUnion.mp- An element belongs to a union of sets indexed by a finite set if and only if it belongs to one of the component sets.
Finset.card_powersetCard- The number of k-element subsets of a set of size n is n choose k.
Finset.card_le_card- If a finite set s is a subset of a finite set t, then |s| β€ |t|.
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 op_1370_four_elements_bound (t : β) (ht : 3 β€ t) (π : Fin t β Finset (Finset (Fin 4))) (hne : β i, (π i).Nonempty) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 7 := by classical have hother : β i : Fin t, β j : Fin t, j β i := by intro i have hcard : 1 < (Finset.univ.erase i).card := by rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] omega obtain β¨j, hj, k, hk, hjkβ© := Finset.one_lt_card.mp hcard exact β¨j, (Finset.mem_erase.mp hj).1β© have hempty : β i, (β : Finset (Fin 4)) β π i := by intro i hi obtain β¨j, hjiβ© := hother i obtain β¨B, hBβ© := hne j exact hinc i j (Ne.symm hji) β hi B hB (Finset.empty_subset B) have huniv : β i, (Finset.univ : Finset (Fin 4)) β π i := by intro i hi obtain β¨j, hjiβ© := hother i obtain β¨B, hBβ© := hne j exact hinc j i hji B hB Finset.univ hi (Finset.subset_univ B) have hcard3 : β i (S : Finset (Fin 4)) (hS : S β π i), S.card = 1 β¨ S.card = 2 β¨ S.card = 3 := by intro i S hS have h0 : S.card β 0 := by intro h rw [Finset.card_eq_zero] at h rw [h] at hS exact hempty i hS have hle : S.card β€ 4 := by have := Finset.card_le_univ S simpa using this have h4 : S.card β 4 := by intro h have hS4 : S.card = Fintype.card (Fin 4) := by simpa using h have hSu : S = Finset.univ := Finset.eq_univ_of_card S hS4 rw [hSu] at hS exact huniv i hS omega by_cases hSingle : β i : Fin t, β S β π i, S.card = 1 Β· obtain β¨i, S, hS, hScard1β© := hSingle obtain β¨x, hxeqβ© := Finset.card_eq_one.mp hScard1 have hx : β j, j β i β β T β π j, x β T := by intro j hji T hT hxT exact hinc i j (Ne.symm hji) S hS T hT (by rw [hxeq]; exact Finset.singleton_subset_iff.mpr hxT) have hb := op_1370_private_element_bound 4 t ht π hne hinc i x (hunc i) hx norm_num at hb exact hb Β· by_cases hThree : β i : Fin t, β S β π i, S.card = 3 Β· obtain β¨i0, S0, hS0, hS0cardβ© := hThree let β¬ : Fin t β Finset (Finset (Fin 4)) := fun i => (π i).image compl have hBne : β i, (β¬ i).Nonempty := by intro i obtain β¨S, hSβ© := hne i exact β¨SαΆ, Finset.mem_image.mpr β¨S, hS, rflβ©β© have hBcard : β i, (β¬ i).card = (π i).card := by intro i apply Finset.card_image_of_injOn intro a _ b _ hab have := congrArg compl hab simpa using this have hBunc : β i, is_uncomplemented (β¬ i) := by intro i A hA hAc obtain β¨B, hB, rflβ© := Finset.mem_image.mp hA obtain β¨C, hC, hCeqβ© := Finset.mem_image.mp hAc have hCB : C = BαΆ := by have := congrArg compl hCeq simpa using this rw [hCB] at hC exact hunc i B hB hC have hBinc : strongly_incomparable β¬ := by intro i j hij A hA B' hB' obtain β¨S, hS, rflβ© := Finset.mem_image.mp hA obtain β¨T, hT, rflβ© := Finset.mem_image.mp hB' intro hsub exact hinc j i (Ne.symm hij) T hT S hS (Finset.compl_subset_compl.mp hsub) have hScard : S0αΆ.card = 1 := by rw [Finset.card_compl, Fintype.card_fin] omega obtain β¨x, hxeqβ© := Finset.card_eq_one.mp hScard have hmem : ({(x)} : Finset (Fin 4)) β β¬ i0 := by exact Finset.mem_image.mpr β¨S0, hS0, hxeqβ© have hx : β j, j β i0 β β T β β¬ j, x β T := by intro j hji T hT hxT exact hBinc i0 j (Ne.symm hji) {(x)} hmem T hT (Finset.singleton_subset_iff.mpr hxT) have hb := op_1370_private_element_bound 4 t ht β¬ hBne hBinc i0 x (hBunc i0) hx norm_num at hb have hsum : β j, (β¬ j).card = β j, (π j).card := by apply Finset.sum_congr rfl intro j _ exact hBcard j rw [hsum] at hb exact hb Β· have hall2 : β i (S : Finset (Fin 4)) (hS : S β π i), S.card = 2 := by intro i S hS have h := hcard3 i S hS rcases h with h | h | h Β· exact absurd β¨i, S, hS, hβ© hSingle Β· exact h Β· exact absurd β¨i, S, hS, hβ© hThree have hdisj : β i j : Fin t, i β j β Disjoint (π i) (π j) := by intro i j hij rw [Finset.disjoint_left] intro S hi hj exact hinc i j hij S hi S hj (Finset.Subset.refl S) have hsumEq : (Finset.univ.biUnion π).card = β i, (π i).card := by rw [Finset.card_biUnion (fun i _ j _ hij => hdisj i j hij)] have hsub : Finset.univ.biUnion π β Finset.univ.powersetCard 2 := by intro S hS rw [Finset.mem_powersetCard] obtain β¨i, _, hiSβ© := Finset.mem_biUnion.mp hS exact β¨Finset.subset_univ S, hall2 i S hiSβ© have hcard6 : (Finset.univ.powersetCard 2 : Finset (Finset (Fin 4))).card = 6 := by rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] decide have hle := Finset.card_le_card hsub rw [hcard6] at hle rw [hsumEq] at hle omega