AFTD Auto-Formalizing Theoretical Domains

op1370_zero_fiber_count

theoremverified

For n at least three, if a family of subsets of Fin n omits the empty set, {x}, its complement, and the full set, and no x-erased fiber has both orientations present, then it has at most 2^(n-1)-2 members.

Statement

lemma op1370_zero_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 = 0) :
    U.card ≤ 2 ^ (n - 1) - 2
Source
Zero-doubled-fiber counting lemma for OP-1370, arXiv:2611.12199 Conjecture 4.3.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The family $U$ is partitioned into two subfamilies: $P$, consisting of the subsets omitting $x$, and $Q_0$, consisting of the subsets containing $x$. Erasing $x$ from each set in $Q_0$ yields a family $Q$ of the same size, which is disjoint from $P$ by hypothesis, so $|U| = |P| + |Q| = |P \cup Q|$. Every set in $P \cup Q$ is a non-empty, proper subset of $V = \mathrm{univ} \setminus \{x\}$ because $U$ contains neither $\emptyset$, $\{x\}$, $V$, nor $\mathrm{univ}$, so $P \cup Q \subseteq \mathcal{P}(V) \setminus \{\emptyset, V\}$. Since $|V| = n - 1 \ge 2$, this gives $|U| = |P \cup Q| \le 2^{n-1} - 2$.

  1. Define $V = \mathrm{univ} \setminus \{x\}$, partition $U$ into $P = \{s \in U \mid x \notin s\}$ and $Q_0 = \{s \in U \mid x \in s\}$, and define $Q = \{s \setminus \{x\} \mid s \in Q_0\}$.

    We set up the notation for decomposing $U$ along $x$. The universe with $x$ removed is called $V$. The family $U$ is partitioned into sets avoiding $x$ ($P$) and sets containing $x$ ($Q_0$). Erasing $x$ from each member of $Q_0$ yields the family $Q$, whose elements are subsets of $V$.

    lines 7–12

      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. $P \cup Q \subseteq \mathcal{P}(V) \setminus \{\emptyset, V\}$.

    Let $S \in P \cup Q$. By construction, $x \notin S$: if $S \in P$ this holds by definition, and if $S \in Q$ then $S = T \setminus \{x\}$ for some $T \in Q_0$. Thus $S \subseteq V = \mathrm{univ} \setminus \{x\}$. Furthermore, $S \neq \emptyset$: if $S \in P$, then $S = \emptyset$ would mean $\emptyset \in U$, contradicting $h_0$; if $S \in Q$, then $T \setminus \{x\} = \emptyset$ implies $T = \{x\}$ (by `insert_erase`), contradicting $h_1$. Similarly, $S \neq V$: if $S \in P$, then $V \in U$, contradicting $h_2$; if $S \in Q$, then $T \setminus \{x\} = V$ implies $T = \mathrm{univ}$ (by `insert_erase`), contradicting $h_3$. Hence, $S$ is in the power set of $V$ but is neither $\emptyset$ nor $V$.

    lines 13–49

    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. $|V| = n - 1$, $V \neq \emptyset$, $\{\emptyset, V\} \subseteq \mathcal{P}(V)$, and $|\{\emptyset, V\}| = 2$.

    Since $V = \mathrm{univ} \setminus \{x\}$, $|V| = n - 1$. As $n \ge 3$, $n - 1 \ge 2 > 0$, so $V \neq \emptyset$ (taking cardinalities via `congrArg`). Both $\emptyset$ and $V$ are subsets of $V$ (via `empty_subset` and `subset_rfl`), so $\{\emptyset, V\} \subseteq \mathcal{P}(V)$ (via `insert_subset_iff` and `singleton_subset_iff`). Because $V \neq \emptyset$, the two sets are distinct, so $|\{\emptyset, V\}| = 2$.

    lines 50–59

    uses congrArg, insert_subset_iff, singleton_subset_iff, empty_subset, subset_rfl

      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]
  4. $|P \cup Q| \le 2^{n-1} - 2$.

    Since $P \cup Q \subseteq \mathcal{P}(V) \setminus \{\emptyset, V\}$, its cardinality is bounded by that of the superset (by `card_le_card`). The cardinality of the difference is $|\mathcal{P}(V)| - |\{\emptyset, V\}|$ (by `card_sdiff_of_subset`). Since $|\mathcal{P}(V)| = 2^{|V|} = 2^{n-1}$ (by `card_powerset`) and $|\{\emptyset, V\}| = 2$, this upper bound is $2^{n-1} - 2$.

    lines 60–63

    uses card_le_card, card_sdiff_of_subset, card_powerset

      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
  5. $|Q| = |Q_0|$.

    Erasing $x$ is injective on $Q_0$: if $a, b \in Q_0$ satisfy $a \setminus \{x\} = b \setminus \{x\}$, then since $x \in a$ and $x \in b$, re-inserting $x$ into both sides with `insert_erase` recovers $a = b$. By `card_image_of_injOn`, the image $Q$ has the same cardinality as $Q_0$.

    lines 64–73

    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
  6. $|P| + |Q_0| = |U|$.

    The families $P$ and $Q_0$ partition $U$ into the elements not containing $x$ and those containing $x$. By `card_filter_add_card_filter_not` and commutativity of addition (`Nat.add_comm`), the sum of their sizes equals $|U|$.

    lines 74–76

    uses Nat.add_comm, 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))
  7. $|U| \le 2^{n-1} - 2$.

    Inclusion-exclusion (`card_union_add_card_inter`) states that $|P \cup Q| + |P \cap Q| = |P| + |Q|$. The assumption `hover` means $|P \cap Q| = 0$, so $|P \cup Q| = |P| + |Q| = |P| + |Q_0| = |U|$. Since $|P \cup Q| \le 2^{n-1} - 2$, and $4 \le 2^{n-1}$ (by `Nat.pow_le_pow_right` since $n \ge 3$) ensures no underflow occurs in natural number subtraction, linear arithmetic concludes $|U| \le 2^{n-1} - 2$.

    lines 77–82

    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 = 0 at hover
      omega
insert_erase
For any finite set $s$ and element $a \in s$, inserting $a$ into $s \setminus \{a\}$ returns $s$.
congrArg
If two inputs are equal, applying a function to them yields equal outputs.
insert_subset_iff
The set $\{a\} \cup s$ is a subset of $t$ if and only if $a \in t$ and $s \subseteq t$.
singleton_subset_iff
The singleton set $\{a\}$ is a subset of $s$ if and only if $a \in s$.
empty_subset
The empty set is a subset of every set.
subset_rfl
Every set is a subset of itself.
card_le_card
If $s \subseteq t$ for finite sets $s$ and $t$, then $|s| \le |t|$.
card_sdiff_of_subset
If $s \subseteq t$ for finite sets $s$ and $t$, then $|t \setminus s| = |t| - |s|$.
card_powerset
The power set of a finite set $s$ has cardinality $2^{|s|}$.
card_image_of_injOn
If a function is injective on a finite set $s$, its image has cardinality $|s|$.
Nat.add_comm
Addition of natural numbers is commutative: $n + m = m + n$.
card_filter_add_card_filter_not
For any predicate on a finite set, the number of elements satisfying it plus the number not satisfying it equals the cardinality of the set.
card_union_add_card_inter
For any finite sets $s$ and $t$, $|s \cup t| + |s \cap t| = |s| + |t|$.
Nat.pow_le_pow_right
If $n > 0$ and $i \le j$, then $n^i \le 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_zero_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 = 0) :    U.card ≤ 2 ^ (n - 1) - 2 := 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 = 0 at hover  omega
See it in the graphDiscuss this resultChallenge it