op_1370_private_absence_bound
At least three nonempty mutually strongly incomparable families have total size at most 2^(n-1)-1 if an element occurs in every set outside one designated uncomplemented family.
Statement
theorem op_1370_private_absence_bound (n t : β) (ht : 3 β€ t) (π : Fin t β Finset (Finset (Fin n))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (π i)) (hx : β j, j β i β β S β π j, x β S) : β j, (π j).card β€ 2 ^ (n - 1) - 1- Source
- Complement-dual corollary of op_1370_private_element_bound, for OP-1370.
- 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β¦
- Used by 1
- op_1370_no_private_reductionFor at least three nonempty, uncomplemented, mutually strongly incomparable families, the conjectured bound follows if it holds with aβ¦
The proof, explained
The result is proved by a duality argument via set complementation, reducing the problem to the companion theorem op_1370_private_element_bound. Replacing each family π j with the family β¬ j of its member complements preserves nonemptiness, strong incomparability, and the uncomplemented property of the i-th family, while turning the condition that x belongs to every set (for j β i) into the condition that x is absent from every set. Applying op_1370_private_element_bound to β¬ yields β j, |β¬ j| β€ 2^(n-1) - 1, and since set complementation is a bijection, each |β¬ j| equals |π j|, concluding the proof.
Define the complementary families β¬ j = {SαΆ | S β π j} for each j.
Under classical logic, we define a new collection of families β¬ by taking the elementwise complement of every set in each original family π j.
classical let β¬ : Fin t β Finset (Finset (Fin n)) := fun j => (π j).image compl
Each complementary family β¬ j is nonempty.
For any index j, since π j is nonempty, it contains some set S. The complement SαΆ is therefore in β¬ j, proving β¬ j is nonempty.
uses
mem_image.mprhave hne' : β j, (β¬ j).Nonempty := by intro j obtain β¨S, hSβ© := hne j exact β¨SαΆ, mem_image.mpr β¨S, hS, rflβ©β©
The collection β¬ is strongly incomparable.
Suppose for distinct indices j β k that some S β β¬ j is a subset of T β β¬ k. Writing S = AαΆ and T = BαΆ for A β π j and B β π k, the inclusion AαΆ β BαΆ is equivalent to B β A. But this contradicts the strong incomparability of the original collection π, since k β j.
uses
mem_image.mphave hinc' : strongly_incomparable β¬ := by intro j k hjk S hS T hT hST obtain β¨A, hA, rflβ© := mem_image.mp hS obtain β¨B, hB, rflβ© := mem_image.mp hT have hBA : B β A := by simpa using hST exact hinc k j hjk.symm B hB A hA hBA
The designated family β¬ i is uncomplemented.
Suppose β¬ i contains both a set S and its complement SαΆ. Writing S = AαΆ and SαΆ = BαΆ for A, B β π i, taking complements gives B = AαΆ. Thus both A and AαΆ belong to π i, which contradicts the hypothesis that π i is uncomplemented.
uses
mem_image.mp,congrArghave hunc' : is_uncomplemented (β¬ i) := by intro S hS hSc obtain β¨A, hA, rflβ© := mem_image.mp hS obtain β¨B, hB, heβ© := mem_image.mp hSc have hBA : B = AαΆ := by have h := congrArg compl he simpa using h subst B exact hunc A hA hB
For every index j β i, the element x is absent from every set in β¬ j.
Any set S β β¬ j is of the form AαΆ for some A β π j. Since x β A by hypothesis, we have x β AαΆ = S.
uses
mem_image.mphave hx' : β j, j β i β β S β β¬ j, x β S := by intro j hj S hS obtain β¨A, hA, rflβ© := mem_image.mp hS simpa using hx j hj A hA
The sum of the sizes of the families in β¬ is at most 2^(n-1) - 1.
We apply the dual theorem op_1370_private_element_bound to β¬. All conditions are met: t β₯ 3, each β¬ j is nonempty, β¬ is strongly incomparable, β¬ i is uncomplemented, and x is absent from every set in β¬ j for j β i.
uses
op_1370_private_element_boundhave h := op_1370_private_element_bound n t ht β¬ hne' hinc' i x hunc' hx'The sum of the sizes of the original families satisfies β j, |π j| β€ 2^(n-1) - 1.
Because complementation on subsets of Fin n is injective, each family β¬ j has the exact same size as π j. Rewriting the cardinality bound on β¬ yields the desired inequality for π.
uses
card_image_of_injective,compl_injectivehave hc : β j, (β¬ j).card = (π j).card := fun j => card_image_of_injective _ compl_injective simp only [hc] at h exact h
mem_image.mpr- An element belongs to the image of a finite set under a function if it is the image of some element in the set.
mem_image.mp- If an element belongs to the image of a finite set under a function, then it is the image of some element in that set.
congrArg- Equal arguments to a function yield equal results: if aβ = aβ, then f(aβ) = f(aβ).
op_1370_private_element_bound- For at least three nonempty mutually strongly incomparable families of subsets of an n-element set, if one family is uncomplemented and some element x is absent from every set in every other family, the sum of the family sizes is at most 2^(n-1) - 1.
card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
compl_injective- The complementation map on a Boolean algebra is injective.
- In lines 15, 23, and 29, the `simpa` tactic simplifies expressions involving double complements and the order-reversing property of set complements ($AαΆ β BαΆ \iff B β A$).
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 800000theorem op_1370_private_absence_bound (n t : β) (ht : 3 β€ t) (π : Fin t β Finset (Finset (Fin n))) (hne : β i, (π i).Nonempty) (hinc : strongly_incomparable π) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (π i)) (hx : β j, j β i β β S β π j, x β S) : β j, (π j).card β€ 2 ^ (n - 1) - 1 := by classical let β¬ : Fin t β Finset (Finset (Fin n)) := fun j => (π j).image compl have hne' : β j, (β¬ j).Nonempty := by intro j obtain β¨S, hSβ© := hne j exact β¨SαΆ, mem_image.mpr β¨S, hS, rflβ©β© have hinc' : strongly_incomparable β¬ := by intro j k hjk S hS T hT hST obtain β¨A, hA, rflβ© := mem_image.mp hS obtain β¨B, hB, rflβ© := mem_image.mp hT have hBA : B β A := by simpa using hST exact hinc k j hjk.symm B hB A hA hBA have hunc' : is_uncomplemented (β¬ i) := by intro S hS hSc obtain β¨A, hA, rflβ© := mem_image.mp hS obtain β¨B, hB, heβ© := mem_image.mp hSc have hBA : B = AαΆ := by have h := congrArg compl he simpa using h subst B exact hunc A hA hB have hx' : β j, j β i β β S β β¬ j, x β S := by intro j hj S hS obtain β¨A, hA, rflβ© := mem_image.mp hS simpa using hx j hj A hA have h := op_1370_private_element_bound n t ht β¬ hne' hinc' i x hunc' hx' have hc : β j, (β¬ j).card = (π j).card := fun j => card_image_of_injective _ compl_injective simp only [hc] at h exact h