AFTD Auto-Formalizing Theoretical Domains

fiber_family_eq_empty_of_card_gt

theoremverified

Let F be a family of subsets with VC-dimension at most d on a finite ground set, and let S ⊆ J with |S| > d. Then the fiber family R_{J,S} is empty.

Statement

theorem fiber_family_eq_empty_of_card_gt {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S : Finset α} {d : ℕ} (hVC : ℱ.vcDim ≤ d) (hS : S ⊆ J) (hSd : d < S.card) : finset_fiber_family ℱ J S = ∅
Source
arXiv:2611.06860 Lemma 2.4
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • shatters_union_of_shatters_fiber_familyLet F be a family of subsets on a finite ground set, S ⊆ J, and let R_{J,S} be the fiber family. If T is shattered by R_{J,S}, then S ∪ T…
  • 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…
Used by 1

Read back from the Lean

Let α be a finite type with decidable equality. Let ℱ be a finite family of finite subsets of α (ℱ : Finset (Finset α)), let J and S be finite subsets of α, and let d be a natural number. If: 1. The VC dimension of ℱ is at most d (ℱ.vcDim ≤ d), 2. S ⊆ J, and 3. The cardinality of S is strictly greater than d (d < S.card), then finset_fiber_family ℱ J S = ∅.

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

The proof proceeds by contradiction. If the fiber family R_{J,S} were nonempty, it would shatter the empty set ∅. By the lifting property of fiber families (shatters_union_of_shatters_fiber_family), the original family ℱ would then shatter S ∪ ∅ = S, implying |S| ≤ VC(ℱ). But this contradicts the hypotheses that VC(ℱ) ≤ d and |S| > d.

  1. Assuming the fiber family is nonempty, it shatters the empty set.

    We proceed by contradiction and assume that the fiber family is not empty (`h_ne`). By `Finset.nonempty_iff_ne_empty.2`, being distinct from the empty set means the family is nonempty (`h_nonempty`). By `Finset.shatters_empty.2`, any nonempty family of sets shatters the empty set ∅.

    lines 3–5

    uses Finset.nonempty_iff_ne_empty.2, Finset.shatters_empty.2

      by_contra h_ne
      have h_nonempty : (finset_fiber_family ℱ J S).Nonempty := Finset.nonempty_iff_ne_empty.2 h_ne
      have h_shat_empty : (finset_fiber_family ℱ J S).Shatters ∅ := Finset.shatters_empty.2 h_nonempty
  2. The ambient family ℱ shatters S.

    The lemma `shatters_union_of_shatters_fiber_family` states that whenever S ⊆ J and the fiber family R_{J,S} shatters T, the original family ℱ shatters S ∪ T. Applying this with T = ∅ gives that ℱ shatters S ∪ ∅, which simplifies to S via `Finset.union_empty`.

    lines 6–7

    uses shatters_union_of_shatters_fiber_family, Finset.union_empty

      have h_shat_union := shatters_union_of_shatters_fiber_family hS h_shat_empty
      rw [Finset.union_empty] at h_shat_union
  3. A contradiction is reached between the cardinality of S and the VC-dimension bound.

    Since ℱ shatters S, the cardinality of S cannot exceed the VC-dimension of ℱ by `card_le_vcDim` (giving |S| ≤ VC(ℱ)). But we are given VC(ℱ) ≤ d and d < |S|, which forms an impossible cycle of inequalities |S| ≤ VC(ℱ) ≤ d < |S|; linear arithmetic (`omega`) closes the contradiction.

    lines 8–9

    uses card_le_vcDim

      have h_card_le := h_shat_union.card_le_vcDim
      omega
Finset.nonempty_iff_ne_empty.2
A finite set is nonempty if it is not equal to the empty set.
Finset.shatters_empty.2
A family of sets shatters the empty set if it is nonempty.
shatters_union_of_shatters_fiber_family
If S ⊆ J and the fiber family R_{J,S} shatters T, then ℱ shatters S ∪ T.
Finset.union_empty
The union of any set with the empty set is the set itself.
card_le_vcDim
If a family shatters a set, the cardinality of that set is at most the VC-dimension of the family.

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

/-- If |S| > d and VC(F) ≤ d, then the fiber family R_{J,S} is empty. -/theorem fiber_family_eq_empty_of_card_gt {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S : Finset α} {d : ℕ} (hVC : ℱ.vcDim ≤ d) (hS : S ⊆ J) (hSd : d < S.card) : finset_fiber_family ℱ J S = ∅ := by  by_contra h_ne  have h_nonempty : (finset_fiber_family ℱ J S).Nonempty := Finset.nonempty_iff_ne_empty.2 h_ne  have h_shat_empty : (finset_fiber_family ℱ J S).Shatters ∅ := Finset.shatters_empty.2 h_nonempty  have h_shat_union := shatters_union_of_shatters_fiber_family hS h_shat_empty  rw [Finset.union_empty] at h_shat_union  have h_card_le := h_shat_union.card_le_vcDim  omega
See it in the graphDiscuss this resultChallenge it