AFTD Auto-Formalizing Theoretical Domains

op1370_coordinate_fiber_defect_identity

theoremverified

For a family U of subsets of Fin n and a coordinate x, the size of U plus the number of missing x-erased fibers equals 2^(n-1) plus the number of doubled x-erased fibers.

Statement

theorem op1370_coordinate_fiber_defect_identity (n : ℕ) (x : Fin n) (U : Finset (Finset (Fin n))) : let V := Finset.univ.erase x; let P := U.filter (fun S => x ∉ S); let Q := (U.filter (fun S => x ∈ S)).image (fun S => S.erase x); U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card
Source
Coordinate-fiber counting helper for OP-1370, arXiv:2611.12199 Conjecture 4.3.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

We partition the family U into the subfamily P of subsets avoiding x and the subfamily Q₀ of subsets containing x. Erasing x is an injection on Q₀, so its image Q has size |Q₀|, giving |U| = |P| + |Q|. Both P and Q consist of subsets of V = Fin n \ {x}, so by inclusion-exclusion |P ∪ Q| + |P ∩ Q| = |P| + |Q| = |U|. Since |𝒫(V)| = 2^(n-1), the missing fibers count |𝒫(V) \ (P ∪ Q)| equals 2^(n-1) - |P ∪ Q|, from which the identity follows immediately by cancellation.

  1. Define the universe without x as V = Fin n \ {x}, partition U into P = {S ∈ U | x ∉ S} and Q₀ = {S ∈ U | x ∈ S}, set Q = {S \ {x} | S ∈ Q₀}, and restate the theorem in these terms.

    We open the Finset namespace, enable classical logic, and introduce the local definitions: V is the universe with x removed, P is the subfamily of sets in U avoiding x, Q₀ is the subfamily containing x, and Q is obtained by erasing x from each set in Q₀. The goal is restated as |U| + |𝒫(V) \ (P ∪ Q)| = 2^(n-1) + |P ∩ Q|.

    lines 2–9

      open Finset in
      classical
      dsimp only
      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)
      change U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card
  2. P ∪ Q is a collection of subsets of V, so P ∪ Q ⊆ 𝒫(V).

    By mem_powerset, it suffices to show that any S ∈ P ∪ Q satisfies S ⊆ V. An element z ∈ S cannot equal x because if S ∈ P then x ∉ S by definition of P, and if S ∈ Q then S was formed by erasing x from some T, so x ∉ S by mem_erase. Thus every element of S belongs to V = Fin n \ {x}.

    lines 10–20

    uses mem_powerset, mem_erase

      have hsub : P ∪ Q ⊆ V.powerset := by
        intro S hS
        rw [mem_powerset]
        intro z hz
        simp only [V, mem_erase, mem_univ, and_true]
        intro hzx
        subst z
        rcases mem_union.mp hS with hP | hQ
        · exact (mem_filter.mp hP).2 hz
        · obtain ⟨T, _, rfl⟩ := mem_image.mp hQ
          exact (mem_erase.mp hz).1 rfl
  3. |Q| = |Q₀|.

    By card_image_of_injOn, the image of Q₀ under erasing x has the same size as Q₀ if the map is injective on Q₀. For any a, b ∈ Q₀ with a \ {x} = b \ {x}, because both a and b contain x, insert_erase allows reconstructing a = (a \ {x}) ∪ {x} = (b \ {x}) ∪ {x} = b.

    lines 21–30

    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
  4. |P| + |Q₀| = |U|.

    Filtering U by the condition x ∈ S and its negation partitions U into Q₀ and P. By card_filter_add_card_filter_not and commutativity of addition (Nat.add_comm), their cardinalities sum to |U|.

    lines 31–33

    uses card_filter_add_card_filter_not, Nat.add_comm

      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))
  5. |V| = n - 1 and |𝒫(V)| = 2^(n-1).

    Since V is Fin n with one element removed, its cardinality is n - 1. Its powerset 𝒫(V) therefore contains 2^(n-1) subsets.

    lines 34–35

      have hVcard : V.card = n - 1 := by simp [V]
      have hpow : V.powerset.card = 2 ^ (n - 1) := by simp [hVcard]
  6. |𝒫(V) \ (P ∪ Q)| = 2^(n-1) - |P ∪ Q| and |P ∪ Q| ≤ 2^(n-1).

    Because P ∪ Q ⊆ 𝒫(V), card_sdiff_of_subset gives |𝒫(V) \ (P ∪ Q)| = |𝒫(V)| - |P ∪ Q| = 2^(n-1) - |P ∪ Q|, and card_le_card confirms |P ∪ Q| ≤ |𝒫(V)| = 2^(n-1).

    lines 36–39

    uses card_sdiff_of_subset, card_le_card

      have hdiff := card_sdiff_of_subset hsub
      rw [hpow] at hdiff
      have hle := card_le_card hsub
      rw [hpow] at hle
  7. |U| + |𝒫(V) \ (P ∪ Q)| = 2^(n-1) + |P ∩ Q|.

    By the principle of inclusion-exclusion (card_union_add_card_inter), |P ∪ Q| + |P ∩ Q| = |P| + |Q|. Since |U| = |P| + |Q₀| = |P| + |Q|, we have |U| = |P ∪ Q| + |P ∩ Q|. Combining this with |𝒫(V) \ (P ∪ Q)| = 2^(n-1) - |P ∪ Q|, the terms |P ∪ Q| cancel, and omega verifies the resulting linear equality over ℕ.

    lines 40–41

    uses card_union_add_card_inter

      have hinclex := card_union_add_card_inter P Q
      omega
mem_powerset
An element belongs to the powerset of t if and only if it is a subset of t.
mem_erase
An element a belongs to s with b removed if and only if a ≠ b and a ∈ s.
card_image_of_injOn
If a function is injective on a finite set s, then the image of s has the same cardinality as s.
insert_erase
Inserting an element a into s \ {a} reconstructs s whenever a ∈ s.
card_filter_add_card_filter_not
The number of elements of a finite set satisfying a predicate plus the number satisfying its negation equals the cardinality of the set.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.
card_sdiff_of_subset
For a subset s ⊆ t of finite sets, |t \ s| = |t| - |s|.
card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
card_union_add_card_inter
For finite sets s and t, |s ∪ t| + |s ∩ t| = |s| + |t| (the principle of inclusion-exclusion).

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_coordinate_fiber_defect_identity (n : ℕ) (x : Fin n) (U : Finset (Finset (Fin n))) : let V := Finset.univ.erase x; let P := U.filter (fun S => x ∉ S); let Q := (U.filter (fun S => x ∈ S)).image (fun S => S.erase x); U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card := by  open Finset in  classical  dsimp only  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)  change U.card + (V.powerset \ (P ∪ Q)).card = 2 ^ (n - 1) + (P ∩ Q).card  have hsub : P ∪ Q ⊆ V.powerset := by    intro S hS    rw [mem_powerset]    intro z hz    simp only [V, mem_erase, mem_univ, and_true]    intro hzx    subst z    rcases mem_union.mp hS with hP | hQ    · exact (mem_filter.mp hP).2 hz    · obtain ⟨T, _, rfl⟩ := mem_image.mp hQ      exact (mem_erase.mp hz).1 rfl  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 hVcard : V.card = n - 1 := by simp [V]  have hpow : V.powerset.card = 2 ^ (n - 1) := by simp [hVcard]  have hdiff := card_sdiff_of_subset hsub  rw [hpow] at hdiff  have hle := card_le_card hsub  rw [hpow] at hle  have hinclex := card_union_add_card_inter P Q  omega
See it in the graphDiscuss this resultChallenge it