AFTD Auto-Formalizing Theoretical Domains

op_1370_four_elements_bound

theoremverifiedoriginal

Any at least three nonempty uncomplemented mutually strongly incomparable families on a four-element ground set have total size at most seven.

Statement

theorem op_1370_four_elements_bound (t : β„•) (ht : 3 ≀ t) (π’œ : Fin t β†’ Finset (Finset (Fin 4))) (hne : βˆ€ i, (π’œ i).Nonempty) (hunc : βˆ€ i, is_uncomplemented (π’œ i)) (hinc : strongly_incomparable π’œ) : βˆ‘ i, (π’œ i).card ≀ 7
Related work
arXiv:2611.12199, Conjecture 4.3, specialized to a four-element ground set.
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…

Read back from the Lean

For any natural number $t \ge 3$ and any family $\mathcal{A} = (\mathcal{A}_i)_{i \in \{0, \dots, t-1\}}$ of finite sets of subsets of $\{0, 1, 2, 3\}$, if: 1. each $\mathcal{A}_i$ is nonempty; 2. each $\mathcal{A}_i$ is uncomplemented (for every $A \in \mathcal{A}_i$, its complement $A^c$ in $\{0, 1, 2, 3\}$ is not in $\mathcal{A}_i$); and 3. $\mathcal{A}$ is strongly incomparable (for all distinct indices $i \ne j$, no set $A \in \mathcal{A}_i$ is a subset of any set $B \in \mathcal{A}_j$), then the sum of the cardinalities of all the $\mathcal{A}_i$, $\sum_{i=0}^{t-1} |\mathcal{A}_i|$, is at most $7$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof classifies the sets in the families by their cardinality. Strong incomparability and nonemptiness rule out the empty set and the entire ground set, so every set has size 1, 2, or 3. If any family contains a singleton, that element cannot belong to any set in any other family, and an existing private-element bound limits the total size to at most 2^(4 - 1) - 1 = 7. If no singletons exist but some family contains a 3-element set, taking set complements dualizes the system into an equivalent collection containing a singleton, yielding the same bound of 7. Finally, if all sets have size 2, strong incomparability forces the families to be pairwise disjoint subsets of the (4 choose 2) = 6 possible pairs, so their total size is at most 6.

  1. For each index i, there exists a distinct index j β‰  i.

    The index set has size t β‰₯ 3. Removing i from the full set of t indices leaves t - 1 β‰₯ 2 elements, which is strictly greater than 1. By the pigeonhole principle on finite sets, there exist at least two distinct elements in the remainder, so we can pick one, j, which is distinct from i.

    lines 2–9

    uses Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, Finset.one_lt_card.mp, Finset.mem_erase.mp

      classical
      have hother : βˆ€ i : Fin t, βˆƒ j : Fin t, j β‰  i := by
        intro i
        have hcard : 1 < (Finset.univ.erase i).card := by
          rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin]
          omega
        obtain ⟨j, hj, k, hk, hjk⟩ := Finset.one_lt_card.mp hcard
        exact ⟨j, (Finset.mem_erase.mp hj).1⟩
  2. No family π’œ i contains the empty set.

    Suppose for contradiction that βˆ… ∈ π’œ i. Since t β‰₯ 3, there is another index j β‰  i, and because π’œ j is nonempty, it contains some set B. Then βˆ… βŠ† B, which violates strong incomparability between π’œ i and π’œ j.

    lines 10–14

    uses Ne.symm, Finset.empty_subset

      have hempty : βˆ€ i, (βˆ… : Finset (Fin 4)) βˆ‰ π’œ i := by
        intro i hi
        obtain ⟨j, hji⟩ := hother i
        obtain ⟨B, hB⟩ := hne j
        exact hinc i j (Ne.symm hji) βˆ… hi B hB (Finset.empty_subset B)
  3. No family π’œ i contains the whole ground set.

    Suppose for contradiction that the entire ground set belongs to π’œ i. Choosing another index j β‰  i and any set B ∈ π’œ j, we have B βŠ† univ, which contradicts strong incomparability from π’œ j to π’œ i.

    lines 15–19

    uses Finset.subset_univ

      have huniv : βˆ€ i, (Finset.univ : Finset (Fin 4)) βˆ‰ π’œ i := by
        intro i hi
        obtain ⟨j, hji⟩ := hother i
        obtain ⟨B, hB⟩ := hne j
        exact hinc j i hji B hB Finset.univ hi (Finset.subset_univ B)
  4. Every set in every family π’œ i has cardinality 1, 2, or 3.

    Let S ∈ π’œ i. Its cardinality cannot be 0, because S = βˆ… was ruled out. It is at most 4 since the ground set has 4 elements. Nor can it be 4, because any 4-element subset of a 4-element set is the entire universal set, which was also ruled out. Hence |S| ∈ {1, 2, 3}.

    lines 20–36

    uses Finset.card_eq_zero, Finset.card_le_univ, Finset.eq_univ_of_card

      have hcard3 : βˆ€ i (S : Finset (Fin 4)) (hS : S ∈ π’œ i), S.card = 1 ∨ S.card = 2 ∨ S.card = 3 := by
        intro i S hS
        have h0 : S.card β‰  0 := by
          intro h
          rw [Finset.card_eq_zero] at h
          rw [h] at hS
          exact hempty i hS
        have hle : S.card ≀ 4 := by
          have := Finset.card_le_univ S
          simpa using this
        have h4 : S.card β‰  4 := by
          intro h
          have hS4 : S.card = Fintype.card (Fin 4) := by simpa using h
          have hSu : S = Finset.univ := Finset.eq_univ_of_card S hS4
          rw [hSu] at hS
          exact huniv i hS
        omega
  5. If some family contains a 1-element set, the sum of cardinalities across all families is at most 7.

    Suppose some π’œ i contains a singleton S = {x}. For any j β‰  i and any T ∈ π’œ j, we cannot have x ∈ T, because that would imply {x} βŠ† T, violating strong incomparability. Thus x is a private element for π’œ i. Applying the lemma op_1370_private_element_bound gives βˆ‘_j |π’œ j| ≀ 2^(4 - 1) - 1 = 7.

    lines 37–45

    uses Finset.card_eq_one.mp, Ne.symm, Finset.singleton_subset_iff.mpr, op_1370_private_element_bound

      by_cases hSingle : βˆƒ i : Fin t, βˆƒ S ∈ π’œ i, S.card = 1
      · obtain ⟨i, S, hS, hScard1⟩ := hSingle
        obtain ⟨x, hxeq⟩ := Finset.card_eq_one.mp hScard1
        have hx : βˆ€ j, j β‰  i β†’ βˆ€ T ∈ π’œ j, x βˆ‰ T := by
          intro j hji T hT hxT
          exact hinc i j (Ne.symm hji) S hS T hT (by rw [hxeq]; exact Finset.singleton_subset_iff.mpr hxT)
        have hb := op_1370_private_element_bound 4 t ht π’œ hne hinc i x (hunc i) hx
        norm_num at hb
        exact hb
  6. In the case where no singletons exist but some family contains a 3-element set, the complemented families ℬ i = {Sᢜ : S ∈ π’œ i} are nonempty, equicardinal to π’œ i, uncomplemented, and strongly incomparable.

    Define ℬ i as the image of π’œ i under set complementation. Nonemptiness follows from nonemptiness of π’œ i. Since complementation on subsets of a finite set is injective, each |ℬ i| = |π’œ i|. Uncomplementedness of ℬ i follows because a complementary pair in ℬ i would pull back to a complementary pair in π’œ i. Finally, ℬ is strongly incomparable: if Sᢜ βŠ† Tᢜ for S ∈ π’œ i and T ∈ π’œ j with i β‰  j, taking complements reverses the inclusion to T βŠ† S, which contradicts strong incomparability of π’œ.

    lines 46–73

    uses Finset.mem_image.mpr, Finset.card_image_of_injOn, congrArg, Finset.mem_image.mp, Ne.symm, Finset.compl_subset_compl.mp

      Β· by_cases hThree : βˆƒ i : Fin t, βˆƒ S ∈ π’œ i, S.card = 3
        · obtain ⟨i0, S0, hS0, hS0card⟩ := hThree
          let ℬ : Fin t β†’ Finset (Finset (Fin 4)) := fun i => (π’œ i).image compl
          have hBne : βˆ€ i, (ℬ i).Nonempty := by
            intro i
            obtain ⟨S, hS⟩ := hne i
            exact ⟨Sᢜ, Finset.mem_image.mpr ⟨S, hS, rfl⟩⟩
          have hBcard : βˆ€ i, (ℬ i).card = (π’œ i).card := by
            intro i
            apply Finset.card_image_of_injOn
            intro a _ b _ hab
            have := congrArg compl hab
            simpa using this
          have hBunc : βˆ€ i, is_uncomplemented (ℬ i) := by
            intro i A hA hAc
            obtain ⟨B, hB, rfl⟩ := Finset.mem_image.mp hA
            obtain ⟨C, hC, hCeq⟩ := Finset.mem_image.mp hAc
            have hCB : C = Bᢜ := by
              have := congrArg compl hCeq
              simpa using this
            rw [hCB] at hC
            exact hunc i B hB hC
          have hBinc : strongly_incomparable ℬ := by
            intro i j hij A hA B' hB'
            obtain ⟨S, hS, rfl⟩ := Finset.mem_image.mp hA
            obtain ⟨T, hT, rfl⟩ := Finset.mem_image.mp hB'
            intro hsub
            exact hinc j i (Ne.symm hij) T hT S hS (Finset.compl_subset_compl.mp hsub)
  7. In the 3-element set case, the total cardinality across all families is at most 7.

    The complement Sβ‚€αΆœ of the 3-element set Sβ‚€ ∈ π’œ iβ‚€ has cardinality 4 - 3 = 1, so Sβ‚€αΆœ = {x} is a singleton in ℬ iβ‚€. By strong incomparability of ℬ, x belongs to no set of ℬ j for any j β‰  iβ‚€, making x a private element for ℬ iβ‚€. Applying op_1370_private_element_bound to ℬ yields βˆ‘_j |ℬ j| ≀ 2^(4 - 1) - 1 = 7. Since |ℬ j| = |π’œ j| for each j, the same bound holds for the original families.

    lines 74–90

    uses Finset.card_compl, Fintype.card_fin, Finset.card_eq_one.mp, Finset.mem_image.mpr, Ne.symm, Finset.singleton_subset_iff.mpr, op_1370_private_element_bound, Finset.sum_congr

          have hScard : S0ᢜ.card = 1 := by
            rw [Finset.card_compl, Fintype.card_fin]
            omega
          obtain ⟨x, hxeq⟩ := Finset.card_eq_one.mp hScard
          have hmem : ({(x)} : Finset (Fin 4)) ∈ ℬ i0 := by
            exact Finset.mem_image.mpr ⟨S0, hS0, hxeq⟩
          have hx : βˆ€ j, j β‰  i0 β†’ βˆ€ T ∈ ℬ j, x βˆ‰ T := by
            intro j hji T hT hxT
            exact hBinc i0 j (Ne.symm hji) {(x)} hmem T hT (Finset.singleton_subset_iff.mpr hxT)
          have hb := op_1370_private_element_bound 4 t ht ℬ hBne hBinc i0 x (hBunc i0) hx
          norm_num at hb
          have hsum : βˆ‘ j, (ℬ j).card = βˆ‘ j, (π’œ j).card := by
            apply Finset.sum_congr rfl
            intro j _
            exact hBcard j
          rw [hsum] at hb
          exact hb
  8. When neither 1-element sets nor 3-element sets exist, every set in every family has size exactly 2.

    Every set has size 1, 2, or 3. Since the existence of singletons and 3-element sets has been ruled out by the preceding case analyses, every set must have size 2.

    lines 91–97

        Β· have hall2 : βˆ€ i (S : Finset (Fin 4)) (hS : S ∈ π’œ i), S.card = 2 := by
            intro i S hS
            have h := hcard3 i S hS
            rcases h with h | h | h
            · exact absurd ⟨i, S, hS, h⟩ hSingle
            Β· exact h
            · exact absurd ⟨i, S, hS, h⟩ hThree
  9. When all sets have size 2, the families are pairwise disjoint subsets of the 2-subsets of a 4-element set, so their total cardinality is at most 6 ≀ 7.

    If two distinct families π’œ i and π’œ j shared a set S, then S βŠ† S would violate strong incomparability; thus the families are mutually disjoint. The cardinality of their union therefore equals the sum of their individual sizes. Since every element in the union has size 2, the union is a subset of the collection of all 2-element subsets of a 4-element set, which has size (4 choose 2) = 6. Hence βˆ‘_i |π’œ i| ≀ 6 ≀ 7.

    lines 98–116

    uses Finset.disjoint_left, Finset.Subset.refl, Finset.card_biUnion, Finset.mem_powersetCard, Finset.mem_biUnion.mp, Finset.subset_univ, Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin, Finset.card_le_card

          have hdisj : βˆ€ i j : Fin t, i β‰  j β†’ Disjoint (π’œ i) (π’œ j) := by
            intro i j hij
            rw [Finset.disjoint_left]
            intro S hi hj
            exact hinc i j hij S hi S hj (Finset.Subset.refl S)
          have hsumEq : (Finset.univ.biUnion π’œ).card = βˆ‘ i, (π’œ i).card := by
            rw [Finset.card_biUnion (fun i _ j _ hij => hdisj i j hij)]
          have hsub : Finset.univ.biUnion π’œ βŠ† Finset.univ.powersetCard 2 := by
            intro S hS
            rw [Finset.mem_powersetCard]
            obtain ⟨i, _, hiS⟩ := Finset.mem_biUnion.mp hS
            exact ⟨Finset.subset_univ S, hall2 i S hiS⟩
          have hcard6 : (Finset.univ.powersetCard 2 : Finset (Finset (Fin 4))).card = 6 := by
            rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin]
            decide
          have hle := Finset.card_le_card hsub
          rw [hcard6] at hle
          rw [hsumEq] at hle
          omega
Finset.card_erase_of_mem
Removing an element a from a finite set s (where a ∈ s) decreases the cardinality of s by 1.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ of that type.
Finset.card_univ
The cardinality of the universal set Finset.univ of a finite type equals the number of elements in that type.
Fintype.card_fin
The standard finite type Fin n has cardinality n.
Finset.one_lt_card.mp
If a finite set has cardinality strictly greater than 1, then it contains at least two distinct elements.
Finset.mem_erase.mp
If an element belongs to s with a removed, then it is not equal to a and belongs to s.
Ne.symm
Inequality is symmetric: if a β‰  b, then b β‰  a.
Finset.empty_subset
The empty set is a subset of every finite set.
Finset.subset_univ
Every finite set is a subset of the universal set of its element type.
Finset.card_eq_zero
A finite set has cardinality 0 if and only if it is the empty set.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the total cardinality of that type.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals that of the entire type is the universal set.
Finset.card_eq_one.mp
If a finite set has cardinality 1, then it is a singleton {a} for some element a.
Finset.singleton_subset_iff.mpr
An element belongs to a set if and only if the corresponding singleton is a subset of that set.
op_1370_private_element_bound
For at least three nonempty strongly incomparable families on an n-element ground set, if one uncomplemented family contains a private element that belongs to no set in any other family, then the total cardinality across all families is at most 2^(n-1) - 1.
Finset.mem_image.mpr
If an element is the image of some element of s under f, then it belongs to the image f(s).
Finset.card_image_of_injOn
If a function f is injective on a finite set s, then the image f(s) has the same cardinality as s.
congrArg
Applying a function to equal arguments produces equal results.
Finset.mem_image.mp
If an element belongs to the image f(s), then it is of the form f(a) for some a ∈ s.
Finset.compl_subset_compl.mp
If the complement of A is a subset of the complement of B, then B is a subset of A.
Finset.card_compl
The cardinality of the complement of a subset is the ambient ground set cardinality minus the subset's cardinality.
Finset.sum_congr
Sums of two functions over the same finite set are equal if their values agree at each element.
Finset.disjoint_left
Two 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_biUnion
The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
Finset.mem_powersetCard
A set belongs to the collection of n-element subsets of s if and only if it is a subset of s and has cardinality n.
Finset.mem_biUnion.mp
An element belongs to a union of sets indexed by a finite set if and only if it belongs to one of the component sets.
Finset.card_powersetCard
The number of k-element subsets of a set of size n is n choose k.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then |s| ≀ |t|.

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

theorem op_1370_four_elements_bound (t : β„•) (ht : 3 ≀ t) (π’œ : Fin t β†’ Finset (Finset (Fin 4))) (hne : βˆ€ i, (π’œ i).Nonempty) (hunc : βˆ€ i, is_uncomplemented (π’œ i)) (hinc : strongly_incomparable π’œ) : βˆ‘ i, (π’œ i).card ≀ 7 := by  classical  have hother : βˆ€ i : Fin t, βˆƒ j : Fin t, j β‰  i := by    intro i    have hcard : 1 < (Finset.univ.erase i).card := by      rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin]      omega    obtain ⟨j, hj, k, hk, hjk⟩ := Finset.one_lt_card.mp hcard    exact ⟨j, (Finset.mem_erase.mp hj).1⟩  have hempty : βˆ€ i, (βˆ… : Finset (Fin 4)) βˆ‰ π’œ i := by    intro i hi    obtain ⟨j, hji⟩ := hother i    obtain ⟨B, hB⟩ := hne j    exact hinc i j (Ne.symm hji) βˆ… hi B hB (Finset.empty_subset B)  have huniv : βˆ€ i, (Finset.univ : Finset (Fin 4)) βˆ‰ π’œ i := by    intro i hi    obtain ⟨j, hji⟩ := hother i    obtain ⟨B, hB⟩ := hne j    exact hinc j i hji B hB Finset.univ hi (Finset.subset_univ B)  have hcard3 : βˆ€ i (S : Finset (Fin 4)) (hS : S ∈ π’œ i), S.card = 1 ∨ S.card = 2 ∨ S.card = 3 := by    intro i S hS    have h0 : S.card β‰  0 := by      intro h      rw [Finset.card_eq_zero] at h      rw [h] at hS      exact hempty i hS    have hle : S.card ≀ 4 := by      have := Finset.card_le_univ S      simpa using this    have h4 : S.card β‰  4 := by      intro h      have hS4 : S.card = Fintype.card (Fin 4) := by simpa using h      have hSu : S = Finset.univ := Finset.eq_univ_of_card S hS4      rw [hSu] at hS      exact huniv i hS    omega  by_cases hSingle : βˆƒ i : Fin t, βˆƒ S ∈ π’œ i, S.card = 1  Β· obtain ⟨i, S, hS, hScard1⟩ := hSingle    obtain ⟨x, hxeq⟩ := Finset.card_eq_one.mp hScard1    have hx : βˆ€ j, j β‰  i β†’ βˆ€ T ∈ π’œ j, x βˆ‰ T := by      intro j hji T hT hxT      exact hinc i j (Ne.symm hji) S hS T hT (by rw [hxeq]; exact Finset.singleton_subset_iff.mpr hxT)    have hb := op_1370_private_element_bound 4 t ht π’œ hne hinc i x (hunc i) hx    norm_num at hb    exact hb  Β· by_cases hThree : βˆƒ i : Fin t, βˆƒ S ∈ π’œ i, S.card = 3    Β· obtain ⟨i0, S0, hS0, hS0card⟩ := hThree      let ℬ : Fin t β†’ Finset (Finset (Fin 4)) := fun i => (π’œ i).image compl      have hBne : βˆ€ i, (ℬ i).Nonempty := by        intro i        obtain ⟨S, hS⟩ := hne i        exact ⟨Sᢜ, Finset.mem_image.mpr ⟨S, hS, rfl⟩⟩      have hBcard : βˆ€ i, (ℬ i).card = (π’œ i).card := by        intro i        apply Finset.card_image_of_injOn        intro a _ b _ hab        have := congrArg compl hab        simpa using this      have hBunc : βˆ€ i, is_uncomplemented (ℬ i) := by        intro i A hA hAc        obtain ⟨B, hB, rfl⟩ := Finset.mem_image.mp hA        obtain ⟨C, hC, hCeq⟩ := Finset.mem_image.mp hAc        have hCB : C = Bᢜ := by          have := congrArg compl hCeq          simpa using this        rw [hCB] at hC        exact hunc i B hB hC      have hBinc : strongly_incomparable ℬ := by        intro i j hij A hA B' hB'        obtain ⟨S, hS, rfl⟩ := Finset.mem_image.mp hA        obtain ⟨T, hT, rfl⟩ := Finset.mem_image.mp hB'        intro hsub        exact hinc j i (Ne.symm hij) T hT S hS (Finset.compl_subset_compl.mp hsub)      have hScard : S0ᢜ.card = 1 := by        rw [Finset.card_compl, Fintype.card_fin]        omega      obtain ⟨x, hxeq⟩ := Finset.card_eq_one.mp hScard      have hmem : ({(x)} : Finset (Fin 4)) ∈ ℬ i0 := by        exact Finset.mem_image.mpr ⟨S0, hS0, hxeq⟩      have hx : βˆ€ j, j β‰  i0 β†’ βˆ€ T ∈ ℬ j, x βˆ‰ T := by        intro j hji T hT hxT        exact hBinc i0 j (Ne.symm hji) {(x)} hmem T hT (Finset.singleton_subset_iff.mpr hxT)      have hb := op_1370_private_element_bound 4 t ht ℬ hBne hBinc i0 x (hBunc i0) hx      norm_num at hb      have hsum : βˆ‘ j, (ℬ j).card = βˆ‘ j, (π’œ j).card := by        apply Finset.sum_congr rfl        intro j _        exact hBcard j      rw [hsum] at hb      exact hb    Β· have hall2 : βˆ€ i (S : Finset (Fin 4)) (hS : S ∈ π’œ i), S.card = 2 := by        intro i S hS        have h := hcard3 i S hS        rcases h with h | h | h        Β· exact absurd ⟨i, S, hS, h⟩ hSingle        Β· exact h        Β· exact absurd ⟨i, S, hS, h⟩ hThree      have hdisj : βˆ€ i j : Fin t, i β‰  j β†’ Disjoint (π’œ i) (π’œ j) := by        intro i j hij        rw [Finset.disjoint_left]        intro S hi hj        exact hinc i j hij S hi S hj (Finset.Subset.refl S)      have hsumEq : (Finset.univ.biUnion π’œ).card = βˆ‘ i, (π’œ i).card := by        rw [Finset.card_biUnion (fun i _ j _ hij => hdisj i j hij)]      have hsub : Finset.univ.biUnion π’œ βŠ† Finset.univ.powersetCard 2 := by        intro S hS        rw [Finset.mem_powersetCard]        obtain ⟨i, _, hiS⟩ := Finset.mem_biUnion.mp hS        exact ⟨Finset.subset_univ S, hall2 i S hiS⟩      have hcard6 : (Finset.univ.powersetCard 2 : Finset (Finset (Fin 4))).card = 6 := by        rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin]        decide      have hle := Finset.card_le_card hsub      rw [hcard6] at hle      rw [hsumEq] at hle      omega
See it in the graphDiscuss this resultChallenge it