The Hierarchy Theorems

Preliminaries#

Definition: Parametrization. A parametrization of a set \(S\) on \(I\) (with \(I\) called the code set) is any surjection \(I\twoheadrightarrow S\).

Defintion: Pointclass restriction. Given a pointclass \(\Gamma\), \(\Gamma\restriction \mathcal{X}\) for \(\mathcal{X}\) a product space is deined as \(\{P\subseteq \mathcal{X} : P\in\Gamma\}\).

Definition: Section. Let \(P\subseteq \mathcal{Y}\times \mathcal{X}\) and \(y\in\mathcal{Y}\), the \(y\)-section of \(P\) is \(P_y = \{x\in\mathcal{X}:P(y,x)\}\).

We say that a pointset \(G\subseteq \mathcal{Y}\times\mathcal{X}\) is universal for \(\Gamma\restriction\mathcal{X}\) if \(G\in\Gamma\) and the map \(\mathcal{Y}\to\Gamma\restriction\mathcal{X}:y \mapsto G_y\) is a parametrization of \(\Gamma\restriction\mathcal{X}\). Namely, for \(P\subseteq \mathcal{X}\) we have

\[P\in\Gamma\text{ iff }\exists y\in\mathcal{Y}, P=G_y.\]

A pointclass \(\Gamma\) is \(\mathcal{Y}\)-parametrized if for every product space \(\mathcal{X}\) there is some \(G\subseteq \mathcal{Y}\times\mathcal{X}\) which is universal for \(\Gamma\restriction\mathcal{X}\).

The Parametrization Theorem#

Theorem (for Borel pointclasses). All the Borel pointclasses \(\mathbf{\Sigma}^0_n\) and their duals \(\mathbf{\Pi}^0_n\) are \(\mathcal{Y}\)-parametrized, where \(\mathcal{Y}\) is any perfect product space.

Theorem (for Lusin pointclasses). All the Lusin pointclasses \(\mathbf{\Sigma}^1_n\) and their duals \(\mathbf{\Pi}^1_n\) are \(\mathcal{Y}\)-parametrized, where \(\mathcal{Y}\) is any perfect product space.

Actually, we have more:

Theorem (general). Given a pointclass \(\Gamma\) that is \(\mathcal{Y}\)-parametrized, then so are the pointclasses \(\neg\Gamma\) and \(\exists^\mathcal{Z}\Gamma\) where \(\mathcal{Z}\) is any product space.

The above theorem together with the parametrization theorem for \(\mathbf{\Sigma}^0_1\), namely, the statement that for every perfect product space \(\mathcal{Y}\), \(\mathbf{\Sigma}^0_1\) is \(\mathcal{Y}\)-parametrized, proves the first theorem (for Borel pointclasses). Take \(\mathbf{\Sigma}^1_1\) instead of \(\mathbf{\Sigma}^0_1\), we then have the theorem for Lusin pointclasses.

The general theorem is in fact easier. If \(G\subseteq \mathcal{Y}\times\mathcal{X}\) is universal for \(\Gamma\restriction\mathcal{X}\), then \(\neg G = \mathcal{Y}\times\mathcal{X}\setminus G\) is obviously universal for \(\neg \Gamma \restriction \mathcal{X}\). If \(G \subseteq \mathcal{Y}\times\mathcal{X}\times\mathcal{Z}\) is universal for \(\Gamma\restriction(\mathcal{X}\times\mathcal{Z}\), define \(H\subseteq \mathcal{Y}\times\mathcal{X}\) by \(H(y,x)\) iff \(\exists z, G(y,x,z)\) and it can immediately be seen that \(H\) is universal for \(\exists^\mathcal{Z} \Gamma\restriction\mathcal{X}\).

For the particular theorem for Borel classes, we only need the parametrization theorem for \(\mathbf{\Sigma}^0_1\), but this takes us into topological details. The idea is oft-used in descriptive set theory, namely, assigning to each finite binary sequence a neighborhood from the enumeration of a basis for the topology, and by this construct the desired set. In more detail, let \(N(\mathcal{Y},0),N(\mathcal{Y},1),\ldots\) and \(N(\mathcal{X},0),N(\mathcal{X},1),\ldots\) be enumerations of bases for the topology of a perfect product space \(\mathcal{Y}\) and a fixed product space \(\mathcal{X}\), use a coding that utilizes prime factorization to assign to each finite binary sequence \(u\) a neighborhood \(N(\mathcal{Y},\sigma(u)\), and with \(\sigma\) define \(G\subset\mathcal{Y}\times\mathcal{X}\) by requiring that \(G(y,x)\) iff there is a finite binary sequence \(u = (t_0, \ldots, t_n)\) s.t. \(t_n = 0\), \(y\in N(\mathcal{Y},\sigma(u)\), and \(x\in N(\mathcal{X},n)\). Prove that every open subset of \(\mathcal{X}\) is a section of \(G\), then the proof will be complete.

The Hierarchy Theorems#

The significance of parametrization becomes evident ini the following lemma:

Lemma: the Hierarchy lemma. Let \(\Gamma\) be a pointclass s.t. for every product space and every pointset \(P\subset \mathcal{X}\times\mathcal{X}\) in \(\Gamma\), the diagonal \(\Delta(P) = \{x: P(x,x)\}\) is also in \(\Gamma\). If \(\Gamma\) is \(\mathcal{Y}\)-parametrized, then some \(P\subseteq \mathcal{Y}\) is in \(\Gamma\) but not in \(\neg\Gamma\).

From which immediately we get the Hierarchy theorem for the Borel pointclasses of finite rank. That is, the following diagram

holds with all the spaces restricted to any perfect product space \(\mathcal{X}\). The same is true of the Lusin pointclasses.