2. EQUIVALENCE RESULT

We begin by recalling the definition of a VC class of sets. A class of subsets

of a set S shatters a set S₀ of V points in S if

, the power set of S₀. In other words,

shatters S₀ if it picks out all 2^V subsets of S₀. The class

is a VC class of sets if there exists a V < ∞ such that

can shatter no V point set S₀ ⊆ S (see, e.g., Pollard, 1984, Ch. 2). The following result was proved by van den Dries in 1998.

THEOREM 1.

is a VC class of sets if and only if Π_Θ(A) is a VC class of sets.

Proof. By symmetry, it is enough to show that Π_Θ(A) not VC implies

not VC. So, suppose that Π_Θ(A) is not a VC class of sets. We must show that for each n ≥ 1, there exists an n point set

that

shatters.

Fix n ≥ 1. Since Π_Θ(A) is not VC, it can shatter some V point set for each V ≥ 1. In particular, there exists a 2ⁿ point set Θ₀ = {θ_i : 1 ≤ i ≤ 2ⁿ} ⊆ Θ that Π_Θ(A) shatters. This implies that there exists a 2²ⁿ point set

such that

. Define a 2ⁿ × 2²ⁿ matrix M_n such that for i = 1,…,2ⁿ and j = 1,…,2²ⁿ,

Thus, the jth column of M_n corresponds to Π_Θ(A|r_j) ∩ Θ₀, the subset of Θ₀ that Π_Θ(A|r_j) picks out. For example, take n = 2 and order the r_j's so that

The ninth column of M₂ is [0,1,1,0]′, and so Π_Θ(A|r₉) ∩ Θ₀ = {θ₂,θ₃}.

The key insight is that the ith row of M_n corresponds to

, the subset of

that

picks out. We want to select

such that

is an n point set and

. This will prove the result.

For n ≥ 1, define P_n to be the 2ⁿ × n matrix of 0's and 1's such that the rows of P_n correspond to the 2ⁿ subsets of an n element set. For example,

Note that the columns of both M_n and P_n have 2ⁿ elements. Moreover, by construction, M_n consists of all possible columns of 2ⁿ elements of 0's and 1's. In particular, the columns of P_n must appear as columns of M_n, say, as columns j₁,j₂,…,j_n. Let

. From the previous discussion,

. █

Remark. The VC dimension of a class of subsets

of a set S is the largest V for which some set of V points in S is shattered by

. Fix n ≥ 1. We see from the proof of Theorem 1 that if Π_Θ(A) has VC dimension at least 2ⁿ, then

has VC dimension at least n. See Wenocur and Dudley (1981) and Stengle and Yukich (1989) for complementary results on VC classes of sets.

We apply Theorem 1 to an example in Asparouhova et al. (2002). These authors state sufficient conditions for

-consistency and asymptotic normality of rank estimator of Han (1987a) of the parameter vector characterizing the transformation in a semiparametric transformation model. They also state sufficient conditions for

-consistency and asymptotic normality of a new class of rank estimators of this parameter vector.

Their key assumption, A7, is that a certain class of sets is a VC class. In the special case of the Box–Cox (1964) transformation, this class of sets has the form

, where

with r = (y₁,y₂,y₃,y₄) and h(r,θ) = y₁^θ − y₂^θ − y₃^θ + y₄^θ. The nonlinearity of h as a function of θ makes it difficult to prove directly that

is a VC class. Because of this nonlinearity, Lemma 2.4 in Pakes and Pollard (1989) does not apply.

However, showing that Π_Θ(A) is a VC class is easy. Fix

. Simple calculus shows that h(r,·) has at most three zeros. It follows that Π_Θ(A|r) is a union of at most two intervals on Θ. Since the set of all intervals on Θ is a VC class, and, for each k ≥ 1, the set of all unions of k sets from a VC class is a VC class (see, e.g., Pollard, 1989), it follows that Π_Θ(A) is a VC class. Deduce from Theorem 1 that

is a VC class.

Finally, we note that Lemma 1 in Asparouhova et al. (2002) is used to establish that

is a VC class of sets for the Box–Cox (1964) example. Though the respective proofs are quite different, their Lemma 1 can be viewed as a special case of Theorem 1. Their Lemma 1 requires that (i) the parameter space Θ be a subset of the real line and (ii) the set A have the form

. Theorem 1, on the other hand, applies to an arbitrary parameter space (e.g., it could be infinite-dimensional) and does not require that the set A have the form specified in (ii); A can be any subset of the product space

.