AFTD Auto-Formalizing Theoretical Domains

op1370_sparse_double_fiber_bound

theoremverifiedoriginal

Let n and t be at least three. For nonempty, uncomplemented, mutually strongly incomparable indexed families of subsets of Fin n, suppose some ground element has at most one erased fiber whose two orientations both belong to the union. Then the total size is at most 2^(n-1)-1.

Statement

theorem op1370_sparse_double_fiber_bound (n t : ℕ) (hn : 3 ≤ n) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hunc : ∀ i, is_uncomplemented (𝒜 i)) (hinc : strongly_incomparable 𝒜) (x : Fin n) (hover : (((Finset.univ.biUnion 𝒜).filter (fun s => x ∉ s)) ∩ (((Finset.univ.biUnion 𝒜).filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1
Related work
A conditional bound for Conjecture 4.3 of arXiv:2611.12199: at most one coordinate fiber is doubled.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • op1370_sparse_fiber_countFor n at least three, if a family of subsets of Fin n omits the empty set, the singleton {x}, its complement, and the whole ground set,…

Read back from the Lean

For all natural numbers $n \ge 3$ and $t \ge 3$, and every family $\mathcal{A}$ of $t$ collections of subsets of $\{0, \dots, n-1\}$ (indexed by $\mathrm{Fin}\ t$), assuming: 1. each collection $\mathcal{A}(i)$ is non-empty; 2. each collection $\mathcal{A}(i)$ is uncomplemented (no set in $\mathcal{A}(i)$ has its complement in $\mathcal{A}(i)$); 3. $\mathcal{A}$ is strongly incomparable (for any $i \ne j$, no set in $\mathcal{A}(i)$ is a subset of any set in $\mathcal{A}(j)$); and given an element $x \in \{0, \dots, n-1\}$ such that: 4. the number of sets $s \subseteq \{0, \dots, n-1\} \setminus \{x\}$ for which both $s \in \bigcup_{i} \mathcal{A}(i)$ and $s \cup \{x\} \in \bigcup_{i} \mathcal{A}(i)$ is at most $1$ (expressed as the intersection of sets in the union not containing $x$ with the image under removing $x$ of sets in the union containing $x$ having cardinality $\le 1$), then the sum of the sizes of the collections, $\sum_{i \in \mathrm{Fin}\ t} |\mathcal{A}(i)|$, is at most $2^{n-1} - 1$.

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

We express the total cardinality ∑_i |𝒜_i| as the cardinality of the union U = ⋃_i 𝒜_i, which is disjoint because strong incomparability prevents any two families from sharing a set. Strong incomparability and the assumption t ≥ 3 also guarantee that neither the empty set nor the universal set belongs to U. We then case-split on whether {x} or its complement belongs to U: if either does, that set isolates x in one family, allowing either op_1370_private_element_bound or op_1370_private_absence_bound to bound the total size by 2^(n-1) - 1. If neither does, U contains none of the four trivial sets, and the sparse fiber counting lemma op1370_sparse_fiber_count bounds |U| by 2^(n-1) - 1 directly.

  1. The total size ∑_i |𝒜_i| equals the cardinality of the union U = ⋃_i 𝒜_i.

    We define U as the union of all families 𝒜_i. Any two distinct families 𝒜_i and 𝒜_j (with i ≠ j) must be disjoint, since if they shared a set S, then S ⊆ S would contradict strong incomparability. By card_biUnion, the cardinality of the disjoint union U is the sum of the cardinalities of the individual families.

    lines 2–12

    uses disjoint_left, Subset.refl, card_biUnion

      open Finset in
      classical
      let U := univ.biUnion 𝒜
      have hdisj : ∀ i j : Fin t, i ≠ j → Disjoint (𝒜 i) (𝒜 j) := by
        intro i j hij
        rw [disjoint_left]
        intro S hSi hSj
        exact hinc i j hij S hSi S hSj (Subset.refl S)
      have hsum : U.card = ∑ i, (𝒜 i).card := by
        dsimp [U]
        rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)]
  2. For every index i, there exists another index j distinct from i.

    Since t ≥ 3, the index set Fin t contains at least three elements. Setting j to 1 if i = 0 and to 0 otherwise gives an index in Fin t distinct from i.

    lines 13–21

    uses congrArg

      have hother : ∀ i : Fin t, ∃ j : Fin t, j ≠ i := by
        intro i
        let j : Fin t := ⟨if i.val = 0 then 1 else 0, by split <;> omega⟩
        have hj : j ≠ i := by
          intro h
          have hv := congrArg Fin.val h
          dsimp [j] at hv
          split at hv <;> omega
        exact ⟨j, hj⟩
  3. The empty set does not belong to U.

    If the empty set belonged to U, it would belong to some family 𝒜_i. Choosing an index j ≠ i and any set T in 𝒜_j (which exists because 𝒜_j is nonempty), we would have ∅ ⊆ T, contradicting the strong incomparability of 𝒜_i and 𝒜_j.

    lines 22–27

    uses mem_biUnion.mp, empty_subset

      have hempty : (∅ : Finset (Fin n)) ∉ U := by
        intro h
        obtain ⟨i, _, hi⟩ := mem_biUnion.mp h
        obtain ⟨j, hji⟩ := hother i
        obtain ⟨T, hT⟩ := hne j
        exact hinc i j hji.symm ∅ hi T hT (empty_subset T)
  4. The universal set does not belong to U.

    If the universal set belonged to U, it would belong to some family 𝒜_i. Picking an index j ≠ i and any set T in 𝒜_j, we would have T ⊆ univ, which again contradicts strong incomparability.

    lines 28–33

    uses mem_biUnion.mp, subset_univ

      have huniv : (univ : Finset (Fin n)) ∉ U := by
        intro h
        obtain ⟨i, _, hi⟩ := mem_biUnion.mp h
        obtain ⟨j, hji⟩ := hother i
        obtain ⟨T, hT⟩ := hne j
        exact hinc j i hji T hT univ hi (subset_univ T)
  5. If the singleton {x} belongs to U, the total size is at most 2^(n-1) - 1.

    If {x} ∈ U, then {x} belongs to some family 𝒜_i. For every other index j ≠ i and every set T ∈ 𝒜_j, x cannot belong to T, because otherwise {x} ⊆ T, violating strong incomparability. Hence x is absent from all other families, so op_1370_private_element_bound implies the desired bound.

    lines 34–38

    uses mem_biUnion.mp, op_1370_private_element_bound, singleton_subset_iff.mpr

      by_cases hs : ({x} : Finset (Fin n)) ∈ U
      · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hs
        apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i)
        intro j hji T hT hxT
        exact hinc i j hji.symm {x} hi T hT (singleton_subset_iff.mpr hxT)
  6. If {x} ∉ U but univ \ {x} ∈ U, the total size is at most 2^(n-1) - 1.

    If univ \ {x} belongs to U, it belongs to some family 𝒜_i. For every other index j ≠ i and every set T ∈ 𝒜_j, we must have x ∈ T; otherwise T would be contained in univ \ {x}, violating strong incomparability. Thus every set in every other family contains x, so op_1370_private_absence_bound implies the desired bound.

    lines 39–48

    uses mem_biUnion.mp, op_1370_private_absence_bound, mem_erase, mem_univ, and_true

      · by_cases hv : (univ.erase x : Finset (Fin n)) ∈ U
        · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hv
          apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i)
          intro j hji T hT
          by_contra hxT
          have hsub : T ⊆ (univ.erase x : Finset (Fin n)) := by
            intro y hy
            simp only [mem_erase, mem_univ, and_true]
            exact fun hyx => hxT (hyx ▸ hy)
          exact hinc j i hji T hT (univ.erase x) hi hsub
  7. If neither {x} nor univ \ {x} belongs to U, the total size is at most 2^(n-1) - 1.

    In the remaining case, U contains none of ∅, {x}, univ \ {x}, or univ. Combined with the assumption hover that at most one fiber has both orientations in U, lemma op1370_sparse_fiber_count implies that |U| ≤ 2^(n-1) - 1. Since |U| equals the total size ∑_i |𝒜_i|, the claim follows.

    lines 49–50

    uses op1370_sparse_fiber_count

        · have h := op1370_sparse_fiber_count n hn U x hempty hs hv huniv hover
          rwa [hsum] at h
and_true
For any proposition P, the conjunction P ∧ True is equivalent to P.
card_biUnion
The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
congrArg
A function applied to equal arguments yields equal results.
disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
empty_subset
The empty set is a subset of every set.
mem_erase
An element belongs to s.erase b if and only if it is distinct from b and belongs to s.
mem_biUnion.mp
An element belongs to a union of sets if and only if it belongs to at least one set in the family (left-to-right implication).
mem_univ
Every element of a finite type belongs to the universal set of that type.
op_1370_private_absence_bound
If an element is present in every set of all other families in a strongly incomparable collection, and the remaining family is uncomplemented, the total cardinality is at most 2^(n-1) - 1.
op_1370_private_element_bound
If a family in a strongly incomparable collection contains an element absent from all sets of all other families, and is uncomplemented, the total cardinality is at most 2^(n-1) - 1.
op1370_sparse_fiber_count
If a family of subsets contains none of ∅, {x}, univ \ {x}, or univ, and at most one fiber at x has both orientations in the family, then its cardinality is at most 2^(n-1) - 1.
singleton_subset_iff.mpr
An element belongs to a set if the singleton containing that element is a subset of the set (the right-to-left direction).
Subset.refl
Every set is a subset of itself.
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

theorem op1370_sparse_double_fiber_bound (n t : ℕ) (hn : 3 ≤ n) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hunc : ∀ i, is_uncomplemented (𝒜 i)) (hinc : strongly_incomparable 𝒜) (x : Fin n) (hover : (((Finset.univ.biUnion 𝒜).filter (fun s => x ∉ s)) ∩ (((Finset.univ.biUnion 𝒜).filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1 := by  open Finset in  classical  let U := univ.biUnion 𝒜  have hdisj : ∀ i j : Fin t, i ≠ j → Disjoint (𝒜 i) (𝒜 j) := by    intro i j hij    rw [disjoint_left]    intro S hSi hSj    exact hinc i j hij S hSi S hSj (Subset.refl S)  have hsum : U.card = ∑ i, (𝒜 i).card := by    dsimp [U]    rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)]  have hother : ∀ i : Fin t, ∃ j : Fin t, j ≠ i := by    intro i    let j : Fin t := ⟨if i.val = 0 then 1 else 0, by split <;> omega⟩    have hj : j ≠ i := by      intro h      have hv := congrArg Fin.val h      dsimp [j] at hv      split at hv <;> omega    exact ⟨j, hj⟩  have hempty : (∅ : Finset (Fin n)) ∉ U := by    intro h    obtain ⟨i, _, hi⟩ := mem_biUnion.mp h    obtain ⟨j, hji⟩ := hother i    obtain ⟨T, hT⟩ := hne j    exact hinc i j hji.symm ∅ hi T hT (empty_subset T)  have huniv : (univ : Finset (Fin n)) ∉ U := by    intro h    obtain ⟨i, _, hi⟩ := mem_biUnion.mp h    obtain ⟨j, hji⟩ := hother i    obtain ⟨T, hT⟩ := hne j    exact hinc j i hji T hT univ hi (subset_univ T)  by_cases hs : ({x} : Finset (Fin n)) ∈ U  · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hs    apply op_1370_private_element_bound n t ht 𝒜 hne hinc i x (hunc i)    intro j hji T hT hxT    exact hinc i j hji.symm {x} hi T hT (singleton_subset_iff.mpr hxT)  · by_cases hv : (univ.erase x : Finset (Fin n)) ∈ U    · obtain ⟨i, _, hi⟩ := mem_biUnion.mp hv      apply op_1370_private_absence_bound n t ht 𝒜 hne hinc i x (hunc i)      intro j hji T hT      by_contra hxT      have hsub : T ⊆ (univ.erase x : Finset (Fin n)) := by        intro y hy        simp only [mem_erase, mem_univ, and_true]        exact fun hyx => hxT (hyx ▸ hy)      exact hinc j i hji T hT (univ.erase x) hi hsub    · have h := op1370_sparse_fiber_count n hn U x hempty hs hv huniv hover      rwa [hsum] at h
See it in the graphDiscuss this resultChallenge it