op_1370_no_private_reduction
For at least three nonempty, uncomplemented, mutually strongly incomparable families, the conjectured bound follows if it holds with a two-unit deficit whenever each ground element occurs in at least two families and is absent in at least two families.
Statement
theorem op_1370_no_private_reduction (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hunc : ∀ i, is_uncomplemented (𝒜 i)) (hinc : strongly_incomparable 𝒜) (hcore : (∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) → (∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) → (∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 2)) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1- Source
- Reduction from OP-1370 to op_1370_no_private_stability, using the private-element theorem and its complement-dual.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
The proof, explained
The theorem reduces the conjectured bound ∑ i, |𝒜 i| ≤ 2^(n-1) - 1 to the core case where every ground element occurs in at least two families and is absent from at least two families. If both conditions hold, the assumed core deficit bound gives ∑ i, |𝒜 i| ≤ 2^(n-1) - 2, which immediately implies the result. Otherwise, some element either occurs in at most one family (in which case it is absent from all other families, so op_1370_private_element_bound applies) or is absent from at most one family (in which case it belongs to all sets in all other families, so op_1370_private_absence_bound applies).
The bound ∑ i, |𝒜 i| ≤ 2^(n-1) - 1 holds whenever every element occurs in at least two families and is absent from at least two families.
We enable classical reasoning and split into cases based on whether every element appears in at least two distinct families (hp) and whether every element is absent from at least two distinct families (hn). In the case where both conditions hold, the core hypothesis hcore directly provides ∑ i, |𝒜 i| ≤ 2^(n-1) - 2. Linear integer arithmetic (omega) then yields the desired bound ≤ 2^(n-1) - 1.
classical by_cases hp : ∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T) · by_cases hn : ∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T) · have h := hcore hp hn omega
The bound holds when some element is absent from at most one family, provided that element is missing from at least one set in some family.
When the two-absence condition fails, not_forall.mp provides an element x that is not absent in two distinct families. In the subcase where x ∉ S for some set S in family i, x cannot be absent from any set T in any other family j ≠ i (otherwise x would be absent in two families i and j). Thus every set in every other family contains x, which satisfies the hypothesis of op_1370_private_absence_bound and establishes the bound.
uses
not_forall.mp,op_1370_private_absence_bound· obtain ⟨x, hx⟩ := not_forall.mp hn by_cases hex : ∃ i : Fin t, ∃ S ∈ 𝒜 i, x ∉ S · obtain ⟨i, S, hS, hxs⟩ := hex apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT by_contra hxt exact hx ⟨i, j, hji.symm, ⟨S, hS, hxs⟩, ⟨T, hT, hxt⟩⟩
The bound holds when some element is absent from at most one family and is contained in every set of every family.
In the complementary subcase where x is missing from no set in any family, every set in every family contains x. Choosing family index i = 0 (valid because 3 ≤ t), every set in every other family j ≠ 0 contains x. Applying op_1370_private_absence_bound gives the bound.
uses
op_1370_private_absence_bound· let i : Fin t := ⟨0, by omega⟩ apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT by_contra hxt exact hex ⟨j, T, hT, hxt⟩
The bound holds when some element belongs to at most one family, provided that element appears in at least one set in some family.
When the two-occurrence condition fails, not_forall.mp provides an element x that does not occur in two distinct families. In the subcase where x ∈ S for some set S in family i, x cannot belong to any set T in any other family j ≠ i (otherwise x would belong to two families i and j). Thus no set in any other family contains x, satisfying the hypothesis of op_1370_private_element_bound and establishing the bound.
uses
not_forall.mp,op_1370_private_element_bound· obtain ⟨x, hx⟩ := not_forall.mp hp by_cases hex : ∃ i : Fin t, ∃ S ∈ 𝒜 i, x ∈ S · obtain ⟨i, S, hS, hxs⟩ := hex apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT hxt exact hx ⟨i, j, hji.symm, ⟨S, hS, hxs⟩, ⟨T, hT, hxt⟩⟩
The bound holds when some element belongs to at most one family and appears in no set of any family, completing the proof.
In the remaining subcase where x belongs to no set in any family, we again choose family index i = 0 (valid since 3 ≤ t). Since x appears nowhere, no set in any other family j ≠ 0 contains x, so op_1370_private_element_bound applies directly to close the final branch.
uses
op_1370_private_element_bound· let i : Fin t := ⟨0, by omega⟩ apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT hxt exact hex ⟨j, T, hT, hxt⟩
not_forall.mp- If a predicate does not hold for all elements of a type, then there exists an element for which it fails.
op_1370_private_absence_bound- For at least 3 strongly incomparable, nonempty families with family i uncomplemented, if every set in every other family contains element x, then the total size of all families is at most 2^(n-1) - 1.
op_1370_private_element_bound- For at least 3 strongly incomparable, nonempty families with family i uncomplemented, if no set in any other family contains element x, then the total size of all families is at most 2^(n-1) - 1.
- In Steps 3 and 5, when an element is absent from (respectively present in) no set in any family, the index i = ⟨0, ...⟩ is arbitrarily chosen using the hypothesis 3 ≤ t to satisfy the interface of the private bound theorems.
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_no_private_reduction (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hunc : ∀ i, is_uncomplemented (𝒜 i)) (hinc : strongly_incomparable 𝒜) (hcore : (∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) → (∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) → (∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 2)) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1 := by classical by_cases hp : ∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T) · by_cases hn : ∀ x, ∃ i j : Fin t, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T) · have h := hcore hp hn omega · obtain ⟨x, hx⟩ := not_forall.mp hn by_cases hex : ∃ i : Fin t, ∃ S ∈ 𝒜 i, x ∉ S · obtain ⟨i, S, hS, hxs⟩ := hex apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT by_contra hxt exact hx ⟨i, j, hji.symm, ⟨S, hS, hxs⟩, ⟨T, hT, hxt⟩⟩ · let i : Fin t := ⟨0, by omega⟩ apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT by_contra hxt exact hex ⟨j, T, hT, hxt⟩ · obtain ⟨x, hx⟩ := not_forall.mp hp by_cases hex : ∃ i : Fin t, ∃ S ∈ 𝒜 i, x ∈ S · obtain ⟨i, S, hS, hxs⟩ := hex apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT hxt exact hx ⟨i, j, hji.symm, ⟨S, hS, hxs⟩, ⟨T, hT, hxt⟩⟩ · let i : Fin t := ⟨0, by omega⟩ apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i) intro j hji T hT hxt exact hex ⟨j, T, hT, hxt⟩