op_1370_balanced_three_families_exclusion
There are no three nonempty mutually strongly incomparable families of subsets of an n-element set, for n at least two, such that the first has 2^(n-2) members and the other two together have 2^(n-2) members. No uncomplementedness assumption is required.
Statement
theorem op_1370_balanced_three_families_exclusion (n : ℕ) (hn : 2 ≤ n)
(𝒜 : Fin 3 → Finset (Finset (Fin n)))
(hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜)
(h0 : (𝒜 0).card = 2 ^ (n - 2))
(h12 : (𝒜 1).card + (𝒜 2).card = 2 ^ (n - 2)) : False- Source
- Balanced-case consequence of the inclusion-hub route for OP-1370, arXiv:2611.12199, Conjecture 4.3; compare https://arxiv.org/abs/1104.3988.
- 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_balanced_cross_incomparable_hubIf two mutually incomparable set families each have one quarter of the Boolean cube, the second family has a member Z such that every…
- strongly_incomparableAn indexed family of finset families
The proof, explained
We combine the families 𝒜₁ and 𝒜₂ into their union G = 𝒜₁ ∪ 𝒜₂. Because 𝒜₁ and 𝒜₂ are strongly incomparable, they are disjoint, giving |G| = 2^(n - 2) with G cross-incomparable to 𝒜₀. Applying the two-family hub theorem (op1370_balanced_cross_incomparable_hub) to 𝒜₀ and G yields a hub element Z ∈ G that shares a common superset in G with every element of G. Finally, since Z must belong to one of 𝒜₁ or 𝒜₂, pairing Z with any member of the other nonempty family produces a common superset in G, which forces an impossible containment between an element of 𝒜₁ and an element of 𝒜₂.
The families 𝒜₁ and 𝒜₂ are disjoint, and their union G = 𝒜₁ ∪ 𝒜₂ has cardinality 2^(n - 2).
We define G = 𝒜₁ ∪ 𝒜₂. If there were any set A in both 𝒜₁ and 𝒜₂, then A ⊆ A would contradict the strong incomparability of the families since 1 ≠ 2. Because 𝒜₁ and 𝒜₂ are disjoint, the cardinality of G is |𝒜₁| + |𝒜₂| = 2^(n - 2).
uses
Finset.disjoint_left,Finset.Subset.refl,Finset.card_union_of_disjointclassical set G := 𝒜 1 ∪ 𝒜 2 with hGdef have hdisj : Disjoint (𝒜 1) (𝒜 2) := by rw [Finset.disjoint_left] intro A hA1 hA2 exact hinc 1 2 (by decide) A hA1 A hA2 (Finset.Subset.refl A) have hGcard : G.card = 2 ^ (n - 2) := by rw [hGdef, Finset.card_union_of_disjoint hdisj, h12]
The families 𝒜₀ and G are cross-incomparable: no set in 𝒜₀ is contained in a set in G, and no set in G is contained in a set in 𝒜₀.
Any element B ∈ G belongs to either 𝒜₁ or 𝒜₂. By the strong incomparability of the indexed family 𝒜 across distinct indices (0 ≠ 1 and 0 ≠ 2), neither A ⊆ B nor B ⊆ A is possible for any A ∈ 𝒜₀.
uses
Finset.mem_unionhave hcross : ∀ A ∈ 𝒜 0, ∀ B ∈ G, ¬ A ⊆ B ∧ ¬ B ⊆ A := by intro A hA B hB rw [hGdef, Finset.mem_union] at hB rcases hB with hB | hB · exact ⟨hinc 0 1 (by decide) A hA B hB, hinc 1 0 (by decide) B hB A hA⟩ · exact ⟨hinc 0 2 (by decide) A hA B hB, hinc 2 0 (by decide) B hB A hA⟩
There exists a hub element Z ∈ G such that every X ∈ G shares a common superset in G with Z.
We apply the two-family balanced cross-incomparable hub theorem (op1370_balanced_cross_incomparable_hub) to 𝒜₀ and G. Both have cardinality 2^(n - 2) and they are cross-incomparable, so there exists Z ∈ G such that for every X ∈ G, some W ∈ G satisfies X ⊆ W and Z ⊆ W.
uses
op1370_balanced_cross_incomparable_hubobtain ⟨Z, hZ, hhub⟩ := op1370_balanced_cross_incomparable_hub n hn (𝒜 0) G hcross h0 hGcardThe case where the hub Z belongs to 𝒜₁ leads to a contradiction.
Suppose Z ∈ 𝒜₁. Since 𝒜₂ is nonempty, choose X ∈ 𝒜₂ ⊆ G. By the hub property, there exists W ∈ G = 𝒜₁ ∪ 𝒜₂ containing both X and Z. If W ∈ 𝒜₁, then X ⊆ W with X ∈ 𝒜₂ contradicts strong incomparability (2 ≠ 1). If W ∈ 𝒜₂, then Z ⊆ W with Z ∈ 𝒜₁ also contradicts strong incomparability (1 ≠ 2).
uses
Finset.mem_union,Or.inrrw [hGdef, Finset.mem_union] at hZ rcases hZ with hZ1 | hZ2 · obtain ⟨X, hX⟩ := hne 2 obtain ⟨W, hW, hXW, hZW⟩ := hhub X (by rw [hGdef, Finset.mem_union]; exact Or.inr hX) rw [hGdef, Finset.mem_union] at hW rcases hW with hW1 | hW2 · exact hinc 2 1 (by decide) X hX W hW1 hXW · exact hinc 1 2 (by decide) Z hZ1 W hW2 hZW
The case where the hub Z belongs to 𝒜₂ also leads to a contradiction, completing the proof.
Suppose instead Z ∈ 𝒜₂. Symmetrically, since 𝒜₁ is nonempty, choose X ∈ 𝒜₁ ⊆ G. The hub property gives W ∈ G = 𝒜₁ ∪ 𝒜₂ containing both X and Z. If W ∈ 𝒜₁, then Z ⊆ W with Z ∈ 𝒜₂ contradicts strong incomparability (2 ≠ 1). If W ∈ 𝒜₂, then X ⊆ W with X ∈ 𝒜₁ contradicts strong incomparability (1 ≠ 2). Since Z must belong to either 𝒜₁ or 𝒜₂, this exhausts all possibilities and establishes False.
uses
Finset.mem_union,Or.inl· obtain ⟨X, hX⟩ := hne 1 obtain ⟨W, hW, hXW, hZW⟩ := hhub X (by rw [hGdef, Finset.mem_union]; exact Or.inl hX) rw [hGdef, Finset.mem_union] at hW rcases hW with hW1 | hW2 · exact hinc 2 1 (by decide) Z hZ2 W hW1 hZW · exact hinc 1 2 (by decide) X hX W hW2 hXW
Finset.disjoint_left- Two finite 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_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.mem_union- An element belongs to the union of two sets if and only if it belongs to at least one of them.
op1370_balanced_cross_incomparable_hub- Given two cross-incomparable families of subsets of an n-element set (with n ≥ 2), each of size 2^(n-2), there exists a hub element in the second family that shares a common superset in that family with every other member of the family.
Or.inr- If B holds, then the disjunction A ∨ B holds.
Or.inl- If A holds, then the disjunction A ∨ B holds.
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_balanced_three_families_exclusion (n : ℕ) (hn : 2 ≤ n) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (h0 : (𝒜 0).card = 2 ^ (n - 2)) (h12 : (𝒜 1).card + (𝒜 2).card = 2 ^ (n - 2)) : False := by classical set G := 𝒜 1 ∪ 𝒜 2 with hGdef have hdisj : Disjoint (𝒜 1) (𝒜 2) := by rw [Finset.disjoint_left] intro A hA1 hA2 exact hinc 1 2 (by decide) A hA1 A hA2 (Finset.Subset.refl A) have hGcard : G.card = 2 ^ (n - 2) := by rw [hGdef, Finset.card_union_of_disjoint hdisj, h12] have hcross : ∀ A ∈ 𝒜 0, ∀ B ∈ G, ¬ A ⊆ B ∧ ¬ B ⊆ A := by intro A hA B hB rw [hGdef, Finset.mem_union] at hB rcases hB with hB | hB · exact ⟨hinc 0 1 (by decide) A hA B hB, hinc 1 0 (by decide) B hB A hA⟩ · exact ⟨hinc 0 2 (by decide) A hA B hB, hinc 2 0 (by decide) B hB A hA⟩ obtain ⟨Z, hZ, hhub⟩ := op1370_balanced_cross_incomparable_hub n hn (𝒜 0) G hcross h0 hGcard rw [hGdef, Finset.mem_union] at hZ rcases hZ with hZ1 | hZ2 · obtain ⟨X, hX⟩ := hne 2 obtain ⟨W, hW, hXW, hZW⟩ := hhub X (by rw [hGdef, Finset.mem_union]; exact Or.inr hX) rw [hGdef, Finset.mem_union] at hW rcases hW with hW1 | hW2 · exact hinc 2 1 (by decide) X hX W hW1 hXW · exact hinc 1 2 (by decide) Z hZ1 W hW2 hZW · obtain ⟨X, hX⟩ := hne 1 obtain ⟨W, hW, hXW, hZW⟩ := hhub X (by rw [hGdef, Finset.mem_union]; exact Or.inl hX) rw [hGdef, Finset.mem_union] at hW rcases hW with hW1 | hW2 · exact hinc 2 1 (by decide) Z hZ2 W hW1 hZW · exact hinc 1 2 (by decide) X hX W hW2 hXW