ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

An infinite singleton class has VC dimension one

Example

Let $X = N$ with its discrete sigma-algebra, and let $H = {0} \cup {h_{a} : a \in N}$ , where $h_{a} (n) = 1$ exactly when $n = a$ . The sketch shows the singleton indicator $h_{2}$ on four elements of $N$ (the ambient number line continues indefinitely). The verification proves the exact trace count for every finite tuple.

diagram failed to render:
\begin{tikzpicture}[baseline=-0.4ex]
  \draw[->] (-0.2,0) -- (4.2,0);
  \foreach \x in {0,1,2,3} {\draw (\x,0.1) -- (\x,-0.1) node[below=3pt] {\x};}
  \fill (2,0) circle (1.8pt);
  \node[above] at (2,0.1) {$h_2=1$};
  \node[above] at (0,0.1) {$0$};
  \node[above] at (1,0.1) {$0$};
  \node[above] at (3,0.1) {$0$};
\end{tikzpicture}

Facts & Assumptions

Given: The class $H$ of the zero function and all singleton-indicator functions on $N$ .

[F1]

A tuple is shattered when every binary label vector occurs; repeated coordinates stay indexed. Indexed shattering and VC dimension of a binary class

[F2]

$Π_{H} (m)$ counts the distinct traces on indexed $m$ -tuples. Growth function of a binary hypothesis class

Verification

1.1F1givenconstruct

For distinct $a, b \in N$ , $h_{a} (a) = 1$ and $h_{b} (a) = 0$ , so the classifiers $h_{a}$ are pairwise distinct and $H$ is infinite. For any single $a$ , the zero function realizes label $0$ and $h_{a}$ realizes label $1$ , so each one-point tuple is shattered.

2.1F1step 1.1

For any two distinct points, no member of $H$ labels both points by $1$ , so their $(1, 1)$ pattern is absent; a repeated two-point tuple also cannot be shattered because both coordinates always agree. Thus no two-point tuple is shattered and $VCdim (H) = 1$ .

3.1F2step 2.1algebra∎

On $m$ distinct natural numbers, the traces are the empty vector and the $m$ vectors with exactly one positive coordinate, so there are $m + 1$ . If a tuple repeats values, its trace is determined by its $r \leq m$ distinct values and has at most $r + 1 \leq m + 1$ patterns. The empty tuple has one trace. Therefore $Π_{H} (m) = m + 1$ for every $m \geq 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.