AFTD Auto-Formalizing Theoretical Domains

op1370_sparse_fiber_count

theoremverified

For 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, and at most one x-erased fiber has both orientations present, then the family has at most 2^(n-1)-1 members.

Statement

lemma op1370_sparse_fiber_count (n : ℕ) (hn : 3 ≤ n) (U : Finset (Finset (Fin n))) (x : Fin n) (h0 : (∅ : Finset (Fin n)) ∉ U) (h1 : ({x} : Finset (Fin n)) ∉ U) (h2 : (Finset.univ.erase x : Finset (Fin n)) ∉ U) (h3 : (Finset.univ : Finset (Fin n)) ∉ U) (hover : ((U.filter (fun s => x ∉ s)) ∩ ((U.filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : U.card ≤ 2 ^ (n - 1) - 1
Source
Coordinate-fiber counting helper for OP-1370, arXiv:2611.12199 Conjecture 4.3.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • op1370_sparse_double_fiber_boundLet n and t be at least three. For nonempty, uncomplemented, mutually strongly incomparable indexed families of subsets of Fin n, suppose…

The proof, explained

We partition the family U into subsets omitting x (denoted P) and subsets containing x (denoted Q0). Erasing x from each set in Q0 yields a collection Q of the same size, so |U| = |P| + |Q|. Because U omits the empty set, the singleton {x}, the full set, and its complement V, every member of P ∪ Q is a non-empty proper subset of V, giving |P ∪ Q| ≤ 2^(n-1) - 2. By inclusion-exclusion, |U| = |P ∪ Q| + |P ∩ Q|, and since |P ∩ Q| ≤ 1 by hypothesis, we conclude |U| ≤ 2^(n-1) - 1.

  1. Define V as the ground set without x, and partition U into the subfamily P of sets omitting x and the subfamily Q0 of sets containing x, projecting Q0 to Q by removing x.

    We fix the ambient sub-universe V = Fin n \ {x}. We partition the family U into sets not containing x (denoted P) and sets containing x (denoted Q0). We also define Q as the collection obtained by erasing x from each member of Q0. Both P and Q thus consist of subsets of V.

    lines 2–7

      open Finset in
      classical
      let V : Finset (Fin n) := univ.erase x
      let P := U.filter (fun s => x ∉ s)
      let Q0 := U.filter (fun s => x ∈ s)
      let Q := Q0.image (fun s => s.erase x)
  2. Every set in P ∪ Q is a non-empty, proper subset of V, so P ∪ Q ⊆ 𝒫(V) \ {∅, V}.

    Take any S ∈ P ∪ Q. If S ∈ P, then x ∉ S by definition; if S ∈ Q, then S = T \ {x} for some T ∈ Q0, so again x ∉ S. Because S ⊆ Fin n and x ∉ S, we have S ⊆ V. Next, S cannot be empty: S ∈ P with S = ∅ would mean ∅ ∈ U, contradicting hypothesis h0; S ∈ Q with S = ∅ means T \ {x} = ∅, which via insert_erase implies T = {x} ∈ U, contradicting hypothesis h1. Similarly, S cannot be V: S ∈ P with S = V implies V ∈ U, contradicting hypothesis h2; S ∈ Q with S = V means T \ {x} = V, which via insert_erase implies T = Fin n ∈ U, contradicting hypothesis h3. Hence S ∈ 𝒫(V) \ {∅, V}.

    lines 8–44

    uses insert_erase

      have hpq : P ∪ Q ⊆ V.powerset \ {∅, V} := by
        intro S hS
        have hxS : x ∉ S := by
          rcases mem_union.mp hS with hS | hS
          · exact (mem_filter.mp hS).2
          · obtain ⟨T, hT, rfl⟩ := mem_image.mp hS
            simp
        have hsub : S ⊆ V := by
          intro y hy
          simp only [V, mem_erase, mem_univ, and_true]
          exact fun h => hxS (h ▸ hy)
        have hn0 : S ≠ ∅ := by
          intro h
          subst S
          rcases mem_union.mp hS with hp | hq
          · exact h0 (mem_filter.mp hp).1
          · obtain ⟨T, hT, heq⟩ := mem_image.mp hq
            have hTx : x ∈ T := (mem_filter.mp hT).2
            have hTeq : T = {x} := by
              have hi := insert_erase hTx
              rw [heq] at hi
              simpa using hi.symm
            exact h1 (hTeq ▸ (mem_filter.mp hT).1)
        have hnV : S ≠ V := by
          intro h
          subst S
          rcases mem_union.mp hS with hp | hq
          · exact h2 (mem_filter.mp hp).1
          · obtain ⟨T, hT, heq⟩ := mem_image.mp hq
            have hTx : x ∈ T := (mem_filter.mp hT).2
            have hTu : T = univ := by
              have hi := insert_erase hTx
              rw [heq] at hi
              simpa [V] using hi.symm
            exact h3 (hTu ▸ (mem_filter.mp hT).1)
        simp only [mem_sdiff, mem_powerset, mem_insert, mem_singleton, not_or]
        exact ⟨hsub, hn0, hnV⟩
  3. The union P ∪ Q has cardinality at most 2^(n-1) - 2.

    Since V = Fin n \ {x}, its cardinality is n - 1. Because n ≥ 3, V is non-empty, which means ∅ and V are distinct elements of 𝒫(V), so |{∅, V}| = 2. By card_sdiff_of_subset and card_powerset, |𝒫(V) \ {∅, V}| = 2^(n-1) - 2. Since P ∪ Q ⊆ 𝒫(V) \ {∅, V}, monotonicity of cardinality (card_le_card) gives |P ∪ Q| ≤ 2^(n-1) - 2.

    lines 45–58

    uses card_sdiff_of_subset, card_powerset, card_le_card

      have hVcard : V.card = n - 1 := by simp [V]
      have hVne : V ≠ ∅ := by
        intro h
        have hc := congrArg Finset.card h
        simp [hVcard] at hc
        omega
      have hdel : ({∅, V} : Finset (Finset (Fin n))) ⊆ V.powerset := by
        rw [insert_subset_iff, singleton_subset_iff]
        exact ⟨mem_powerset.mpr (empty_subset V), mem_powerset.mpr subset_rfl⟩
      have hcarddel : ({∅, V} : Finset (Finset (Fin n))).card = 2 := by simp [hVne.symm]
      have hbound : (P ∪ Q).card ≤ 2 ^ (n - 1) - 2 := by
        have h := card_le_card hpq
        rw [card_sdiff_of_subset hdel, hcarddel, card_powerset, hVcard] at h
        exact h
  4. The projection from Q0 to Q is a bijection, so |Q| = |Q0|.

    By card_image_of_injOn, it suffices to check that erasing x is injective on Q0. If two sets a, b ∈ Q0 satisfy a \ {x} = b \ {x}, then since x ∈ a and x ∈ b, reinserting x using insert_erase yields a = (a \ {x}) ∪ {x} = (b \ {x}) ∪ {x} = b.

    lines 59–68

    uses card_image_of_injOn, insert_erase

      have hQcard : Q.card = Q0.card := by
        apply card_image_of_injOn
        intro a ha b hb hab
        have hax : x ∈ a := (mem_filter.mp ha).2
        have hbx : x ∈ b := (mem_filter.mp hb).2
        change a.erase x = b.erase x at hab
        calc
          a = insert x (a.erase x) := (insert_erase hax).symm
          _ = insert x (b.erase x) := by rw [hab]
          _ = b := insert_erase hbx
  5. The size of U decomposes as |U| = |P| + |Q0|.

    Every set in U either contains x or does not. By card_filter_add_card_filter_not, the cardinality of U is the sum of the cardinalities of the two complementary filtered subfamilies P and Q0.

    lines 69–71

    uses card_filter_add_card_filter_not

      have hsplit : P.card + Q0.card = U.card := by
        simpa [P, Q0, Nat.add_comm] using
          (card_filter_add_card_filter_not (s := U) (fun s => x ∈ s))
  6. |U| ≤ 2^(n-1) - 1.

    By inclusion-exclusion (card_union_add_card_inter), |P| + |Q| = |P ∪ Q| + |P ∩ Q|. Since |Q0| = |Q| and |U| = |P| + |Q0|, this becomes |U| = |P ∪ Q| + |P ∩ Q|. Combining the bound |P ∪ Q| ≤ 2^(n-1) - 2 with the fiber-overlap hypothesis |P ∩ Q| ≤ 1 (hover) yields |U| ≤ 2^(n-1) - 1. The fact that 2^(n-1) ≥ 4 (derived via Nat.pow_le_pow_right from n - 1 ≥ 2) ensures natural number subtraction does not underflow, allowing linear arithmetic (omega) to conclude.

    lines 72–77

    uses card_union_add_card_inter, Nat.pow_le_pow_right

      have hPQ := card_union_add_card_inter P Q
      have hpow : 4 ≤ 2 ^ (n - 1) := by
        calc 4 = 2 ^ 2 := by norm_num
             _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by omega) (by omega)
      change (P ∩ Q).card ≤ 1 at hover
      omega
insert_erase
For an element a in a finite set s, inserting a into s with a removed yields s.
card_sdiff_of_subset
If s ⊆ t for finite sets s and t, then the cardinality of t \ s is |t| - |s|.
card_powerset
The powerset of a finite set s has cardinality 2^|s|.
card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
card_image_of_injOn
If a function is injective on a finite set s, then its image has the same cardinality as s.
card_filter_add_card_filter_not
The cardinality of a finite set s is the sum of the number of elements satisfying a predicate and the number of elements not satisfying it.
card_union_add_card_inter
For two finite sets s and t, |s ∪ t| + |s ∩ t| = |s| + |t|.
Nat.pow_le_pow_right
If n > 0 and i ≤ j, then n^i ≤ n^j.

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

lemma op1370_sparse_fiber_count (n : ℕ) (hn : 3 ≤ n) (U : Finset (Finset (Fin n))) (x : Fin n) (h0 : (∅ : Finset (Fin n)) ∉ U) (h1 : ({x} : Finset (Fin n)) ∉ U) (h2 : (Finset.univ.erase x : Finset (Fin n)) ∉ U) (h3 : (Finset.univ : Finset (Fin n)) ∉ U) (hover : ((U.filter (fun s => x ∉ s)) ∩ ((U.filter (fun s => x ∈ s)).image (fun s => s.erase x))).card ≤ 1) : U.card ≤ 2 ^ (n - 1) - 1 := by  open Finset in  classical  let V : Finset (Fin n) := univ.erase x  let P := U.filter (fun s => x ∉ s)  let Q0 := U.filter (fun s => x ∈ s)  let Q := Q0.image (fun s => s.erase x)  have hpq : P ∪ Q ⊆ V.powerset \ {∅, V} := by    intro S hS    have hxS : x ∉ S := by      rcases mem_union.mp hS with hS | hS      · exact (mem_filter.mp hS).2      · obtain ⟨T, hT, rfl⟩ := mem_image.mp hS        simp    have hsub : S ⊆ V := by      intro y hy      simp only [V, mem_erase, mem_univ, and_true]      exact fun h => hxS (h ▸ hy)    have hn0 : S ≠ ∅ := by      intro h      subst S      rcases mem_union.mp hS with hp | hq      · exact h0 (mem_filter.mp hp).1      · obtain ⟨T, hT, heq⟩ := mem_image.mp hq        have hTx : x ∈ T := (mem_filter.mp hT).2        have hTeq : T = {x} := by          have hi := insert_erase hTx          rw [heq] at hi          simpa using hi.symm        exact h1 (hTeq ▸ (mem_filter.mp hT).1)    have hnV : S ≠ V := by      intro h      subst S      rcases mem_union.mp hS with hp | hq      · exact h2 (mem_filter.mp hp).1      · obtain ⟨T, hT, heq⟩ := mem_image.mp hq        have hTx : x ∈ T := (mem_filter.mp hT).2        have hTu : T = univ := by          have hi := insert_erase hTx          rw [heq] at hi          simpa [V] using hi.symm        exact h3 (hTu ▸ (mem_filter.mp hT).1)    simp only [mem_sdiff, mem_powerset, mem_insert, mem_singleton, not_or]    exact ⟨hsub, hn0, hnV⟩  have hVcard : V.card = n - 1 := by simp [V]  have hVne : V ≠ ∅ := by    intro h    have hc := congrArg Finset.card h    simp [hVcard] at hc    omega  have hdel : ({∅, V} : Finset (Finset (Fin n))) ⊆ V.powerset := by    rw [insert_subset_iff, singleton_subset_iff]    exact ⟨mem_powerset.mpr (empty_subset V), mem_powerset.mpr subset_rfl⟩  have hcarddel : ({∅, V} : Finset (Finset (Fin n))).card = 2 := by simp [hVne.symm]  have hbound : (P ∪ Q).card ≤ 2 ^ (n - 1) - 2 := by    have h := card_le_card hpq    rw [card_sdiff_of_subset hdel, hcarddel, card_powerset, hVcard] at h    exact h  have hQcard : Q.card = Q0.card := by    apply card_image_of_injOn    intro a ha b hb hab    have hax : x ∈ a := (mem_filter.mp ha).2    have hbx : x ∈ b := (mem_filter.mp hb).2    change a.erase x = b.erase x at hab    calc      a = insert x (a.erase x) := (insert_erase hax).symm      _ = insert x (b.erase x) := by rw [hab]      _ = b := insert_erase hbx  have hsplit : P.card + Q0.card = U.card := by    simpa [P, Q0, Nat.add_comm] using      (card_filter_add_card_filter_not (s := U) (fun s => x ∈ s))  have hPQ := card_union_add_card_inter P Q  have hpow : 4 ≤ 2 ^ (n - 1) := by    calc 4 = 2 ^ 2 := by norm_num         _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by omega) (by omega)  change (P ∩ Q).card ≤ 1 at hover  omega
See it in the graphDiscuss this resultChallenge it