op1370_zero_fiber_count
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
- op1370_two_set_complement_block_boundLet n be at least three and let indexed families of subsets of Fin n be mutually strongly incomparable. Suppose there is a coordinate x…
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$.
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$.
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)
$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$.
uses
insert_erasehave 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⟩
$|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$.
uses
congrArg,insert_subset_iff,singleton_subset_iff,empty_subset,subset_rflhave 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]
$|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$.
uses
card_le_card,card_sdiff_of_subset,card_powersethave 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
$|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$.
uses
card_image_of_injOn,insert_erasehave 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
$|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|$.
uses
Nat.add_comm,card_filter_add_card_filter_nothave 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))
$|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$.
uses
card_union_add_card_inter,Nat.pow_le_pow_righthave 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$.
- The hypothesis $n \ge 3$ ensures that $4 \le 2^{n-1}$, which is needed formally so that the natural number subtraction $2^{n-1} - 2$ does not truncate at zero.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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