AFTD Auto-Formalizing Theoretical Domains

op_1370_private_absence_bound

theoremverified

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 all i j : ΞΉ with i β‰  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.

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

    lines 5–6

      classical
      let ℬ : Fin t β†’ Finset (Finset (Fin n)) := fun j => (π’œ j).image compl
  2. 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.

    lines 7–10

    uses mem_image.mpr

      have hne' : βˆ€ j, (ℬ j).Nonempty := by
        intro j
        obtain ⟨S, hS⟩ := hne j
        exact ⟨Sᢜ, mem_image.mpr ⟨S, hS, rfl⟩⟩
  3. 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.

    lines 11–16

    uses mem_image.mp

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

    lines 17–25

    uses mem_image.mp, congrArg

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

    lines 26–29

    uses mem_image.mp

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

    line 30

    uses op_1370_private_element_bound

      have h := op_1370_private_element_bound n t ht ℬ hne' hinc' i x hunc' hx'
  7. 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 π’œ.

    lines 31–33

    uses card_image_of_injective, compl_injective

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

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