AFTD Auto-Formalizing Theoretical Domains

op_1370_incomparable_two_sets_card_bound

theoremverified

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.

  1. 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.

    lines 14–22

    uses Finset.disjoint_left, Finset.mem_image.mp, Finset.card_image_of_injective, compl_injective

      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
  2. 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.

    lines 23–50

    uses Finset.card_compl, congrArg

      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
  3. 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.

    lines 51–55

    uses Finset.card_insert_eq_ite, Ne.symm

      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]
  4. 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.

    lines 56–69

    uses Finset.disjoint_left, mem_insert, mem_singleton, mem_image.mp, compl_compl, disjoint_union_right.mpr

      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⟩
  5. 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.

    lines 70–76

    uses Finset.card_le_univ, Finset.card_union_of_disjoint, Finset.card_univ, Finset.powerset_univ, Finset.card_powerset

      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
      omega
  6. 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.

    lines 85–88

    uses Finset.not_subset.mp

      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
  7. 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.

    lines 89–95

    uses op_1370_pair_count_missing_six, empty_subset, subset_univ, singleton_subset_iff.mpr, mem_compl, mem_singleton

      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
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

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
See it in the graphDiscuss this resultChallenge it