AFTD Auto-Formalizing Theoretical Domains

op_1370_no_private_reduction

theoremverified

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 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…
  • 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).

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

    lines 5–9

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

    lines 10–16

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

    lines 17–21

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

    lines 22–27

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

    lines 28–31

    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.

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