The Boldface Borel Hierarchy of finite rank

Preliminary Notions: pointclasses#

Fix once and for all a collection \(\mathcal{F}\) of metric spaces, with the following properties:

1. The discrete space \(\omega\), the reals \(\R\), \(\mathcal{N}\) and \(\mathbb{C}\) are in \(\mathcal{F}\).
2. Every space in \(\mathcal{F}\) other than \(\omega\) is a perfect Polish space.

Basically we put in \(\mathcal{F}\) all the perfect Polish spaces in which we are interested, along with \(\omega\). The members of \(\mathcal{F}\) are the basic spaces. A product space (definition) is any finite cartesian product of basic spaces (including basic spaces themselves) topologized naturally with product topology (recall that for finite products product or Tychnoff topology coincides with box topology).  Products of product spaces are defined by going back to the basic factors: \(\mathcal{X}\times \mathcal{Y} = X_1\times\ldots\times X_k\times Y_1\times\ldots\times Y_l\) when \(\mathcal{X} = X_1 \times\ldots\times X_k\) and \(\mathcal{Y} = Y_1\times \ldots\times Y_l\). 

Tuples in product spaces are called points and the subsets of these spaces pointsets. Pointsets may be thought of as sets, or as relations (maybe predicates) with arguments in the basic spaces. For \(S \subseteq \mathcal{X}\), \(x\in S\) is also denoted as \(S(x)\). A collection of pointsets is called pointclasses. Typically, in definability theory, we start with a small pointclass \(\Lambda\) and certain operations on pointsets, and then study the sets which can be constructed by applying the given operations to the members of \(\Lambda\).

“Logical” operations#

Take the logical symbols \(\forall,\exists, \to,\wedge,\vee,\neg\) with their customary meanings, one can view them as denoting operations on pointsets. In general a \(k\)-ary pointset operation is a function \(\Phi\) with domain some set of \(k\)-tuples of pointsets, and with pointsets as values. Then we have the following propositional pointset operations:

• \(\wedge\), the conjunction, is the binary pointset operation that assigns to every pair \(P,Q\) of subsets of the same space \(\mathcal{X}\) the set \(P\wedge Q\): \(x\in (P\wedge Q)\) iff \(P(x) \wedge Q(x)\). Obviously \(P\wedge Q = P\cap Q\), but we may keep the symbol \(\cap\) for general set theoretic operation of intersection for arbitrary sets.
• \(vee\), the disjunction, is the binary pointset operation that assigns to \(P, Q\subseteq \mathcal{X}\) the set \(P\vee Q = P\cup Q = \{x: P(x) \vee Q(x)\}\).
• \(\neg\), negation, is most conveniently regarded as a collection operations \(\neg_\mathcal{X}\), one for each product space \(\mathcal{X}\), with \(\sigma_\mathcal{X} S\) defined for \(S\subseteq \mathcal{X}\), which is the taking of complements: \(\neg \mathcal{X} S = \neg_\mathcal{X} S = \mathcal{X}\setminus S = \{x\in\mathcal{X} : \neg S(x)\}\).
• By composition we can define \(\to\), the implication: \(P\to Q = \neg P\vee Q\).

 Further we have the following quantifiers, or projections and dual projections:

• For each fixed product space \(\mathcal{Y}\), we call the operation \(\exists^\mathcal{Y}\) projection along \(\mathcal{Y}\), or existential quantification on \(\mathcal{Y}\). If \(S\subseteq \mathcal{X}\times \mathcal{Y}\), put \(\exists^\mathcal{Y} = \{x\in\mathcal{X} : (\exists y) S(x,y)\}\).
• Put \(\forall^\mathcal{Y} S = \neg \exists^\mathcal{Y} \neg S\) for \(S\subseteq \mathcal{X}\times\mathcal{Y}\), and call the operation \(\forall^\mathcal{Y}\) dual projection along \(\mathcal{Y}\), or universal quantification on \(\mathcal{Y}\).

Only the projections along basic spaces are fundamental since all the others can be obtained from these by composition, e.g. \(\mathcal{Y} = \omega\times\mathcal{N}\), then for each \(S\subseteq \mathcal{X}\times\mathcal{Y}\), \(\exists^\mathcal{Y} S = \exists^\omega\exists^\mathcal{N} S\). Furthermore, we take \(\exists^{\leq}\) and \(\forall^\leq\) to be the bounded number quantifiers. \((x,n)\in\exists^\leq S\) iff \((\exists m\leq n) S(x,n)\).

The Boldface Borel Hierarchy (finite rank)#

Define by recursion:

\[\begin{align*} \mathbf{\Sigma}^0_1 &= \text{ all open pointsets},\\ \mathbf{\Pi}^0_n &= \neg\mathbf{\Sigma}^0_{n}, \\ \mathbf{\Sigma}^0_{n+1} &= \exists^\omega  \mathbf{\Pi}^0_n\end{align*}\]

and put \(\mathbf{\Sigma}^0_n = \mathbf{\Sigma}^0_n \cap \mathbf{\Pi}^0_n\). The number \(n\) is called the rank of the pointclasses. The pointclasses \(\mathbf{\Sigma}^0_n\) are called the Borel pointclasses, \(\mathbf{\Pi}^0_n\) are the dual Borel pointclasses, and finally \(\mathbf{\Delta}^0_n\) are the ambiguous Borel pointclasses.

• \(\mathbf{\Pi}^0_1\) consists of all closed pointsets.
• \(\mathbf{\Delta}^0_1\) consists of all clopen sets.
• \(\mathbf{\Sigma}^0_2\) consists of all \(F_\sigma\) sets, i.e. countable union of closed sets.
• \(\mathbf{\Delta}^0_2\) are \(G_\delta\) sets, which are countable intersection of open sets.
• and so on and so forth.

It is easy to prove that

\[\mathbf{\Sigma}^0_n,\mathbf{\Pi}^0_n \subseteq \Delta^0_{n+1}\]

in fact by the hierarchy theorem the subset inclusions are all strict after parametrizations.

Closure Properties#

Preliminaries: closure (finite), continuous substitution.#

Definition: Closure (finite). A pointclass \(\Lambda\) is cloased under a \(k\)-ary pointset operation \(\Phi\) if (definition) whenever \(P_1,\ldots,P_k \in \Lambda\) and \(\Phi(P_1,\ldots,P_k)\) is defined, \(\Phi(P_1,\ldots,P_k)\in \Lambda\).

Definition: Continuous substitution. \(\Lambda\) is said to be closed under continuous substitution if for every continuous function \(f:\mathcal{X}\to\mathcal{Y}\) and every \(P\in\Lambda, P\subseteq \mathcal{Y}, f^{-1}(P)\in \Lambda\). That is, the continuous preimage of a pointset in the pointclass is in the pointclass.

Closure properties of Borel pointclasses of finite rank#

Theorem. Each Borel pointlass \(\mathbf{\Sigma}^0_n\ (n\geq 1)\) is closed under continuous substituion, \(\vee\),\(\wedge\),\(\forall^\leq\),\(\exists^\leq\),\(\exists^\omega\).

Theorem. Each dual pointclass \(\mathbf{\Pi}^0_n\ (n\geq 1)\) is closed under continuous substitution, \(\vee\), \(\wedge\), \(\forall^\leq\),\(\exists^\leq\),\(\forall^\omega\).

Theorem. Each ambiguous Borel pointclass \(\mathbf{\Delta}^0_n\ (n\geq 1)\) is closed under continuous substituion, \(\neg\), \(\vee\),\(\wedge\),\(\exists^\leq\),\(\forall^\leq\).

The proofs are trivial. Just to note that one needs quantifier contraction, and for that a trick to code a finite sequence of integers into one integer is needed, which is provided by prime factorization. For example, we prove by induction the closure properties, and to prove the closure of \(\mathbf{\Sigma}^{n+1}\) under \(\wedge\), suppose that \(P,Q\in\mathbf{\Sigma}^0_n\) and consider
 

\[R(x) \leftrightarrow (\exists s)\neg (P,s) \wedge (\exists t)\neg Q(x,t),\]

we may take the sequence \(\langle s, t\rangle\) and encode it into the integer \(u= p_0^s p_1^t\) where \(p_i\) is the \(i\)-th prime; given \(u\) by prime factorization it is possible to recover \((u)_0 = s\) and \((u)_1 = t\). Hence
 

\[R(x)\leftrightarrow (\exists u)\neg [P(x,(u)_0) \wedge Q(x,(u)_1)],\]

and by closure under continuous substituion and \(\vee\) of \(\mathbf{\Sigma}^0_n\).