finset_fiber_family_empty
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
- not_is_uncomplemented_pair_complThe family consisting of a set and its complement is not uncomplemented.
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.
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ᶜ.
uses
finset_fiber_family,finset_restricted_family_empty,Finset.filter_false_of_memsimp only [finset_fiber_family, finset_restricted_family_empty] apply Finset.filter_false_of_mem
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`).
uses
Finset.not_nonempty_emptyintro 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
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.
/-- 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