AFTD Auto-Formalizing Theoretical Domains

finset_vc_dim_le_of_not_contains_trace

theoremverifiedformalization

Let H be a set system on an h-element ground set, h ≥ 1. If a finite set system F is trace-H-free, then VCdim(F) ≤ h − 1.

Statement

theorem finset_vc_dim_le_of_not_contains_trace {α : Type*} [DecidableEq α] {h : ℕ} (hh : 1 ≤ h)
    (𝓗 : Finset (Finset (Fin h))) (𝓕 : Finset (Finset α))
    (hfree : ¬ finset_contains_trace 𝓕 𝓗) : 𝓕.vcDim ≤ h - 1
Formalizes
arXiv:2610.08151 (Polynomial-in-r bounds for forbidden traces of uniform hypergraphs), Proposition 1. VCdim is Mathlib's Finset.vcDim (largest shattered set).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finset_contains_traceA set system F contains the set system H on the ground set {0,…,h−1} as a trace if there is an injection φ of the ground set of H into…

The proof, explained

We prove the bound by contradiction. If the VC dimension of $\mathcal{F}$ were greater than $h - 1$, then $\mathcal{F}$ would shatter some set $s$ of cardinality at least $h$, and consequently would shatter an $h$-element subset $t \subseteq s$. By embedding the $h$-element ground set of $\mathcal{H}$ bijectively onto $t$, the shattering of $t$ ensures that every edge $e \in \mathcal{H}$ can be realized as the trace of some member of $\mathcal{F}$ on $t$. This exhibits $\mathcal{H}$ as a trace of $\mathcal{F}$, contradicting the hypothesis that $\mathcal{F}$ is trace-$\mathcal{H}$-free.

  1. To bound $\mathrm{vcDim}(\mathcal{F}) \le h - 1$, it suffices to show that every set shattered by $\mathcal{F}$ has cardinality at most $h - 1$.

    The VC dimension $\mathrm{vcDim}(\mathcal{F})$ is defined as the supremum of cardinalities of all sets shattered by $\mathcal{F}$ (lines 4 and 6). By `Finset.sup_le` (line 5), this supremum is bounded by $h - 1$ provided that every shattered set $s$ satisfies $|s| \le h - 1$.

    lines 4–6

    uses Finset.sup_le, Finset.mem_shatterer

      unfold Finset.vcDim
      refine Finset.sup_le fun s hs => ?_
      rw [Finset.mem_shatterer] at hs
  2. Assuming for contradiction that some shattered set has cardinality greater than $h - 1$, there exists a subset $t \subseteq s$ of size $h$ that is also shattered by $\mathcal{F}$.

    Suppose for contradiction that $|s| \not\le h - 1$ (`by_contra`, line 7), so $|s| > h - 1$ (`not_le`, line 8). Because $h \ge 1$, linear arithmetic (`omega`, line 9) gives $h \le |s|$. By `Finset.exists_subset_card_eq` (line 9), $s$ contains a subset $t \subseteq s$ of cardinality $|t| = h$. Since $\mathcal{F}$ shatters $s$, it also shatters the subset $t$ by monotonicity of shattering (line 10).

    lines 7–10

    uses not_le, Finset.exists_subset_card_eq

      by_contra hlt
      rw [not_le] at hlt
      obtain ⟨t, hts, htc⟩ := Finset.exists_subset_card_eq (show h ≤ s.card by omega)
      have ht : 𝓕.Shatters t := hs.mono_right hts
  3. There exists an embedding $\varphi : \mathrm{Fin}\; h \hookrightarrow \alpha$ whose image on $\mathrm{Fin}\; h$ is precisely $t$.

    Since $|t| = h$, there is a bijection between $\mathrm{Fin}\; h$ and the subtype of elements of $t$. Composing this inverse bijection with the subtype inclusion embedding (`Function.Embedding.subtype`, lines 11–12) defines an embedding $\varphi : \mathrm{Fin}\; h \hookrightarrow \alpha$. We verify that $\varphi(\mathrm{Fin}\; h) = t$ by extensionality and double inclusion (`ext x`, lines 14–21): every element $\varphi(i)$ lies in $t$ by subtype membership (lines 17–18), and conversely every $x \in t$ is the image of its associated index in $\mathrm{Fin}\; h$ under $\varphi$ (lines 19–21).

    lines 11–21

    uses Function.Embedding.subtype, Finset.mem_map, Finset.mem_univ, true_and

      let φ : Fin h ↪ α :=
        (t.equivFinOfCardEq htc).symm.toEmbedding.trans (Function.Embedding.subtype _)
      have himg : Finset.univ.map φ = t := by
        ext x
        simp only [Finset.mem_map, Finset.mem_univ, true_and]
        constructor
        · rintro ⟨i, rfl⟩
          exact ((t.equivFinOfCardEq htc).symm i).2
        · intro hx
          refine ⟨t.equivFinOfCardEq htc ⟨x, hx⟩, ?_⟩
          simp [φ]
  4. The family $\mathcal{F}$ contains $\mathcal{H}$ as a trace via $\varphi$, producing a contradiction with the hypothesis that $\mathcal{F}$ is trace-$\mathcal{H}$-free.

    Applying the trace-freeness assumption `hfree` leaves the goal of showing that $\mathcal{F}$ contains $\mathcal{H}$ as a trace (line 22). Choosing the embedding $\varphi$ (line 23), consider any configuration $e \in \mathcal{H}$. Because $e \subseteq \mathrm{univ}$ (`Finset.subset_univ`), its image satisfies $\varphi(e) \subseteq \varphi(\mathrm{univ}) = t$ using `Finset.map_subset_map.2` (lines 24–26). Since $\mathcal{F}$ shatters $t$, there exists some $u \in \mathcal{F}$ with $t \cap u = \varphi(e)$ (line 27). Rewriting $t$ as $\varphi(\mathrm{univ})$ and using commutativity of intersection (`Finset.inter_comm`), we obtain $u \cap \varphi(\mathrm{univ}) = \varphi(e)$ (line 28). This shows that $\mathcal{F}$ induces $\mathcal{H}$ via $\varphi$, which contradicts `hfree`.

    lines 22–28

    uses Finset.subset_univ, Finset.map_subset_map.2, Finset.inter_comm

      apply hfree
      refine ⟨φ, fun e _ => ?_⟩
      have hsub : e.map φ ⊆ t := by
        rw [← himg]
        exact Finset.map_subset_map.2 (Finset.subset_univ e)
      obtain ⟨u, hu, hut⟩ := ht hsub
      exact ⟨u, hu, by rw [himg, Finset.inter_comm]; exact hut⟩
Finset.sup_le
The supremum of a function $f$ over a finite set $s$ is at most $a$ if $f(b) \le a$ for all $b \in s$.
Finset.mem_shatterer
A set $s$ belongs to the shatterer of a set family $\mathcal{A}$ if and only if $\mathcal{A}$ shatters $s$.
not_le
In a linear order, $a \not\le b$ if and only if $b < a$.
Finset.exists_subset_card_eq
If $n \le |s|$, then $s$ contains a subset of cardinality $n$.
Function.Embedding.subtype
The canonical inclusion of a subtype into its ambient type as an embedding.
Finset.mem_map
An element $b$ belongs to the image of a finset under an embedding $f$ if and only if $b = f(a)$ for some $a$ in the domain.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and
Conjunction with `True` is logically redundant: `True ∧ p` simplifies to `p`.
Finset.subset_univ
Every finite set in a finite type is a subset of `Finset.univ`.
Finset.map_subset_map.2
An embedding preserves subset inclusion: if $s_1 \subseteq s_2$, then $f(s_1) \subseteq f(s_2)$.
Finset.inter_comm
Intersection of finite sets is commutative: $s_1 \cap s_2 = s_2 \cap s_1$.

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 finset_vc_dim_le_of_not_contains_trace {α : Type*} [DecidableEq α] {h : ℕ} (hh : 1 ≤ h)    (𝓗 : Finset (Finset (Fin h))) (𝓕 : Finset (Finset α))    (hfree : ¬ finset_contains_trace 𝓕 𝓗) : 𝓕.vcDim ≤ h - 1 := by  unfold Finset.vcDim  refine Finset.sup_le fun s hs => ?_  rw [Finset.mem_shatterer] at hs  by_contra hlt  rw [not_le] at hlt  obtain ⟨t, hts, htc⟩ := Finset.exists_subset_card_eq (show h ≤ s.card by omega)  have ht : 𝓕.Shatters t := hs.mono_right hts  let φ : Fin h ↪ α :=    (t.equivFinOfCardEq htc).symm.toEmbedding.trans (Function.Embedding.subtype _)  have himg : Finset.univ.map φ = t := by    ext x    simp only [Finset.mem_map, Finset.mem_univ, true_and]    constructor    · rintro ⟨i, rfl⟩      exact ((t.equivFinOfCardEq htc).symm i).2    · intro hx      refine ⟨t.equivFinOfCardEq htc ⟨x, hx⟩, ?_⟩      simp [φ]  apply hfree  refine ⟨φ, fun e _ => ?_⟩  have hsub : e.map φ ⊆ t := by    rw [← himg]    exact Finset.map_subset_map.2 (Finset.subset_univ e)  obtain ⟨u, hu, hut⟩ := ht hsub  exact ⟨u, hu, by rw [himg, Finset.inter_comm]; exact hut⟩
See it in the graphDiscuss this resultChallenge it