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.

Thresholds on the real line have VC dimension one

Example

Equip $R$ with its Borel sigma-algebra. Let $H_{t h} : = {h_{t} : t \in R}$ , where $h_{t} (x) = 1$ exactly when $x \leq t$ . On the ordered sample $x_{1} < x_{2} < x_{3}$ , the threshold $t = x_{2}$ labels the first two points by $1$ and the third by $0$ . The sketch is illustrative; the verification proves the dimension and growth count for every finite tuple.

Facts & Assumptions

Given: The threshold class $H_{t h}$ described in the Example.

[F1]

Shattering is defined on indexed tuples; a one-point tuple is shattered when both labels occur, and $VCdim$ is the largest shattered length. Indexed shattering and VC dimension of a binary class

[F2]

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

Verification

1.1F1givenconstruct

If $s < t$ , the midpoint $x = (s + t) / 2$ satisfies $h_{s} (x) = 0$ and $h_{t} (x) = 1$ , so the functions $h_{t}$ are all distinct as $t$ varies over $R$ and the class is infinite. For any single $x$ , $t < x$ realizes label $0$ and $t = x$ realizes label $1$ , so every one-point tuple is shattered.

2.1F1step 1.1

For two distinct points $x < y$ , the possible trace vectors are only $(0, 0)$ , $(1, 0)$ , and $(1, 1)$ as the threshold passes from left to right; $(0, 1)$ never occurs. If the two indexed points repeat, their labels always agree. Hence no two-point tuple is shattered, and $VCdim (H_{t h}) = 1$ .

3.1F2step 2.1algebra∎

For $m$ distinct points ordered $x_{1} < \dots < x_{m}$ , a threshold realizes exactly the $m + 1$ vectors consisting of $k$ initial ones followed by $m - k$ zeros, for $0 \leq k \leq m$ . A tuple with only $r$ distinct points has at most $r + 1 \leq m + 1$ traces, while a distinct $m$ -tuple attains $m + 1$ ; for $m = 0$ the unique empty trace is counted once. Thus $Π_{H_{t h}} (m) = m + 1$ .

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.