AFTD Auto-Formalizing Theoretical Domains

finset_fiber_family_empty

theoremverified

The fiber family of the empty family is empty.

Statement

theorem finset_fiber_family_empty {α : Type*} [Fintype α] [DecidableEq α] (J S : Finset α) : finset_fiber_family (∅ : Finset (Finset α)) J S = ∅
Source
arXiv:2611.06860, Section 2.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • finset_fiber_familyGiven a family of sets F on a finite universe, a subset J, and a subset S of J, the fiber family R_{J,S} consists of all subsets U of the…
  • finset_restricted_family_emptyThe restricted family of the empty family is empty.
  • finset_restricted_familyGiven a family of sets F and sets J and U, the restricted family F_{J,U} consists of all subsets A of J such that A ∪ U is in F.
Used by 1

Read back from the Lean

For any finite type α with decidable equality, and any two finsets J, S : Finset α, the fiber family of the empty set family ∅ : Finset (Finset α) with respect to J and S (finset_fiber_family ∅ J S) is equal to the empty finset ∅.

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

By definition, the fiber family of the empty family consists of those subsets U ⊆ Jᶜ whose restriction of ∅ to J and U shatters S. Since every restriction of the empty family is empty, the fiber family reduces to filtering the powerset of Jᶜ by the condition that ∅ shatters S. Because shattering any set requires a nonempty family, the empty family shatters nothing and the resulting fiber family is empty.

  1. It suffices to show that the empty family cannot shatter S.

    By definition of `finset_fiber_family` and `finset_restricted_family_empty` (any restriction of the empty family is empty), the fiber family simplifies to filtering the powerset of Jᶜ by whether ∅ shatters S. By `Finset.filter_false_of_mem`, a filtered set is empty whenever the selection predicate is everywhere false, so it suffices to show that ∅ does not shatter S for any U ⊆ Jᶜ.

    lines 3–4

    uses finset_fiber_family, finset_restricted_family_empty, Finset.filter_false_of_mem

      simp only [finset_fiber_family, finset_restricted_family_empty]
      apply Finset.filter_false_of_mem
  2. The empty family cannot shatter S, so the fiber family is empty.

    Fix U ⊆ Jᶜ and assume for contradiction that ∅ shatters S (`hS`). By definition of shattering, any shattering family must be nonempty (`hS.nonempty`), contradicting the fact that the empty set is not nonempty (`Finset.not_nonempty_empty`).

    lines 5–6

    uses Finset.not_nonempty_empty

      intro U _ hS
      exact Finset.not_nonempty_empty hS.nonempty
finset_fiber_family
The fiber family of a family of sets ℱ with respect to J and S consists of all subsets U ⊆ Jᶜ whose restriction of ℱ to J and U shatters S.
finset_restricted_family_empty
Any restriction of the empty family of sets is empty.
Finset.filter_false_of_mem
Filtering a finite set by a predicate that is false for every element yields the empty set.
Finset.not_nonempty_empty
The empty set is not nonempty.

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

/-- The fiber family of the empty family is empty. -/theorem finset_fiber_family_empty {α : Type*} [Fintype α] [DecidableEq α] (J S : Finset α) : finset_fiber_family (∅ : Finset (Finset α)) J S = ∅ := by  simp only [finset_fiber_family, finset_restricted_family_empty]  apply Finset.filter_false_of_mem  intro U _ hS  exact Finset.not_nonempty_empty hS.nonempty
See it in the graphDiscuss this resultChallenge it