Classes of Functions

From Intervals to Labels

An interval over the real numbers can be viewed as a binary-valued function. Choose an interval with endpoints a and b, where a is less than b. Every real-number input receives a label according to membership: a point inside the chosen interval receives 1, and a point outside it receives 0. The collection of all such interval functions is the class we will study.

Meaning of Shattering

A finite set is shattered by a class of functions when the class achieves every possible labeling of that set. For a set of n points, each point can receive either 0 or 1, so there are 2^n possible binary labelings. To prove shattering, we must show that every one of those labelings is produced by at least one function in the class.

Two Points Fully Controlled

Consider the set C = {1, 2}. There are four possible binary labelings of these two points: (0, 0), (1, 0), (0, 1), and (1, 1). The interval class can realize all four. Choose an interval that contains neither point for (0, 0), an interval that contains only the first point for (1, 0), an interval that contains only the second point for (0, 1), and an interval that contains both points for (1, 1). Therefore, the class of intervals shatters {1, 2}.

Three Points Reveal the Limit

Now take any three real points and arrange them in order as c1 less than or equal to c2 less than or equal to c3. Consider the labeling (1, 0, 1). It asks for an interval that contains the first and third points but excludes the middle point. That is impossible: an interval that reaches both outer points must also contain the point lying between them. Thus, the interval class fails to realize at least one labeling on every three-point set.

Reading the VC-Dimension

The VC-dimension of a function class is the size of the largest set that the class shatters. For intervals, the two-point result gives a lower bound: the VC-dimension is at least 2. The three-point obstruction gives the matching upper bound: no set of size 3 is shattered, so the VC-dimension cannot be 3 or larger. Together, these facts establish VCdim(H) = 2 for the class H of intervals over the real numbers.

Common Reasoning Errors

• Confusing some labelings with every labeling.

  Shattering requires every possible labeling, not merely multiple labelings.

  Fix: List all binary labelings and verify that each one has an interval witness.

• Ignoring the order of three real points.

  The impossibility depends on the middle point lying between the two outer points.

  Fix: Write the points in order as c1, c2, c3 before analyzing the labeling.

• Thinking that failure on one particular three-point set is sufficient by itself.

  To rule out VC-dimension 3, the argument must apply to every three-point set.

  Fix: Use the ordering argument for an arbitrary three-point set.

• Stopping after proving that two points can be shattered.

  The two-point construction gives only a lower bound.

  Fix: Also prove that no three-point set can be shattered.

Quick Check

1. Intervals label real-number points by membership: inside receives 1 and outside receives 0. Shattering means realizing every possible binary labeling of a finite set. Intervals shatter two points because all four two-point labelings can be realized. They cannot shatter three points because the ordered labeling (1, 0, 1) would require an interval to contain two outer points while excluding the point between them. Therefore, the VC-dimension of the class of intervals over the real numbers is 2.