Interval — VC = 2

Parent: examples Prereq: learning-theory — H, h, shattering.

Class $H = \{\, h_{a,b} : a \le b \,\}$ , two parameters:

h_{a,b}(x) = \begin{cases} + & a \le x \le b \\ - & \text{otherwise} \end{cases}

Count it the same way. (Recall $h_{a,b}(p) = {+}$ iff $a \le p \le b$ .)

Shatter 2 points p₁ < p₂? labeling (h(p₁), h(p₂)); exhibit an [a,b] for each:

labeling	a witnessing `[a,b]`	realizable?
`(−,−)`	any `[a,b]` with `b < p₁`	✓
`(+,−)`	`[p₁, p₁]` (so `p₁ ≤ b < p₂`)	✓
`(−,+)`	`[p₂, p₂]` (so `p₁ < a ≤ p₂`)	✓
`(+,+)`	`[p₁, p₂]`	✓

All 4 realizable → shatters 2 → VC ≥ 2. (The (+,−)/(−,+) a threshold couldn't do, the interval now can.)

Shatter 3 points p₁ < p₂ < p₃? the labeling (+,−,+) requires a ≤ p₁ ≤ b and a ≤ p₃ ≤ b; together these give a ≤ p₁ < p₂ < p₃ ≤ b, forcing p₂ ∈ [a,b], i.e. h(p₂) = + — contradiction. So (+,−,+) is unrealizable → no 3 points shatter → VC < 3. So VC = 2.

So the interval's VC 2 came from counting shatterable points (2), not from "it has 2 endpoints" — the endpoint count matched here by luck.

Breaks on + − + (needs two separate bands) → climb to union-of-intervals.