Scales 101 – part II: where & how?

Last time we got an idea of what scales are and why they’re useful. The next questions we then might ask is where do we find them, and how do we create new ones from existing ones? We’ll cover the ‘classical’ answers to these questions here, meaning the ones concerned with the projective hiearchy.

The first question, where we find the scales, is given by the following theorem, due to Novikov (Нóвиков), Kondô (近藤), Addison and Moschovakis (Μοσχοβάκης). We’ll give a full proof here to give an idea of how these scales are constructed.

Theorem (Novikov-Kondô-Addison-Moschovakis). \bf\Pi^1_1 has the scale property.

Proof. It suffices to prove that \Pi^1_1 has the scale property, as the closure properties of \Pi^1_1 allows us to define \bf\Pi^1_1-scales from \Pi^1_1-scales, simply by including the relevant real parameter.

So let A\in\Pi^1_1. Then for some recursive function f:\mathbb R\to\mathbb R it holds that x\in A iff f(x)\in\textsf{WO}, where \textsf{WO} is the set of all x\in\mathbb R such that

\leq_x:=\{(m,n)\mid x(\langle m,n\rangle)=0\}

is a wellordering (it can be shown that this set is a universal \Pi^1_1-set). For x\in\textsf{WO} define x\upharpoonright n:=\{m<\omega\mid m<_xn\} and define, for x,y\in A and n<\omega,

x\leq_n y iff |f(x)|<|f(y)|\lor(|f(x)|=|f(y)|\land|f(x)\upharpoonright n|\leq|f(y)\upharpoonright n|),

and let \varphi_n:A\to\textsf{On} be the norm corresponding to \leq_n. We’ll show that \langle\varphi_n\mid n<\omega\rangle is a \Pi^1_1-scale on A.

Claim. \vec\varphi is a scale.

Proof of claim. Let \langle x_i\mid i<\omega\rangle be a sequence of elements of A and assume that x_i\to x for some x\in\mathbb R and \varphi_n(x_i)\to\alpha_n for some \alpha_n. We first show that x\in A; i.e. that f(x)\in\textsf{WO}. We achieve this by showing that the mapping n\mapsto\tilde\alpha_n is an order-preserving map from the domain of \leq_{f(x)} to \textsf{On}. Here \tilde\alpha_n is such that |f(x_i)\upharpoonright n|=\tilde\alpha_n for sufficiently large i<\omega, which is possible as \varphi_n(x_i)\to\alpha_n.

Assume that n<_{f(x)}m. By continuity of f we get that n<_{f(x_i)}m for sufficiently large i<\omega, so that |f(x_i)\upharpoonright n|<|f(x_i)\upharpoonright m| by definition and then \tilde\alpha_n<\tilde\alpha_m. This shows that x\in A. Next, we have to show that \varphi_n(x)\leq\alpha_n for all n<\omega. If we stare at the following equation for a while, we see that it’s sufficient to show that

|f(x)|<\tilde\alpha\lor(|f(x)|=\tilde\alpha\land|f(x)\upharpoonright n|\leq\tilde\alpha_n),

where again \tilde\alpha=|f(x_i)| for sufficiently large i<\omega. By monotonicity of n\mapsto\tilde\alpha_n we get that |f(x)\upharpoonright n|\leq\tilde\alpha_n, since m<_{f(x)}n implies \tilde\alpha_m<\tilde\alpha_n, so there can be at most \tilde\alpha_n many \leq_{f(x)}-predecessors of n by injectivity of n\mapsto\tilde\alpha_n. As \tilde\alpha_n\leq\tilde\alpha holds for every n<\omega we can conclude that

|f(x)|=\text{sup}_n|f(x)\upharpoonright n|\leq\tilde\alpha,

making \vec\varphi a scale. QED

It remains to show that \vec\varphi is a \Pi^1_1-scale; but this follows from the fact that there exist relations Q_{\Pi^1_1}\in\Pi^1_1 and Q_{\Sigma^1_1}\in\Sigma^1_1 such that for y\in\textsf{WO},

x\in\textsf{WO}\land|x|\leq|y| iff Q_{\Pi^1_1}(x,y) iff Q_{\Sigma^1_1}(x,y).

Indeed, Q_{\Pi^1_1}(x,y) holds iff \leq_x is a wellorder and given any map f:(\omega,\leq_y)\to(\omega,\leq_x) it holds that f is injective iff it’s bijective. In other words, we’re simply saying that x\in\textsf{WO} (which is \Pi^1_1) and that |y|\not<|x|, which we described in a \Pi^1_1 fashion as well. The other formula, Q_{\Sigma^1_1}(x,y) is defined as there exists an injective f:(\omega,\leq_x)\to(\omega,\leq_y). Since we assumed that y\in\textsf{WO} this automatically gives us that x\in\textsf{WO} as well. QED

Okay, so we can find scaled pointclasses. Now, the question is how we move from one scaled pointclass to another. Say a pointclass is adequate if it contains all recursive sets and is closed under disjunction, conjunction, bounded number quantification of both kinds (i.e. over \omega and \mathbb R) and substitution of recursive functions. The usual arithmetical (\Sigma^0_n and \Pi^0_n), analytical (\Sigma^1_n and \Pi^1_n), Borel (\bf\Sigma^0_n and \bf\Pi^0_n) and projective (\bf\Sigma^1_n and \bf\Pi^1_n) hierarchies are all adequate. We then got the following theorem.

Theorem (Moschovakis). If \Gamma is adequate and A\in\Gamma admits a \Gamma-scale, then \exists^{\mathbb R}A admits an \exists^{\mathbb R}\forall^{\mathbb R}\Gamma-scale.

I won’t give the proof, but the scale \vec\psi in question is given by

\psi_n(x):=\text{min}\{\langle\varphi_0(x,\alpha),\alpha_0,\hdots,\varphi_n(x,\alpha),\alpha_n\rangle\mid(x,\alpha)\in A\},

where \vec\varphi is the \Gamma-scale given by assumption, and \langle \cdot,\hdots,\cdot \rangle a coding of tuples of ordinals to ordinals. This then yields the corollary stating that for adequate scaled \Gamma with \forall^{\mathbb R}\Gamma\subseteq\Gamma, \exists^{\mathbb R}\Gamma has the scale property. In particular we then get that \bf\Sigma^1_2 has the scale property.

To cover the rest of the projective hierarchy we need to assume some determinacy. We arrive at the following second peridicity theorem.

Theorem (Moschovakis). Assume \Gamma is adequate and \text{Det}(\Gamma\cap\lnot\Gamma) holds. Then whenever A\in\Gamma admits a \Gamma-scale, \forall^{\mathbb R}A admits a \forall^{\mathbb R}\exists^{\mathbb R}\Gamma-scale.

Here the construction of the scale is a bit more elaborate and will be omitted here — see “Notes on the theory of scales” in the first Cabal volume by Kechris (Κεχρής) and Moschovakis. Again we get that for adequate scaled \Gamma such that \text{Det}(\Gamma\cap\lnot\Gamma) holds, \forall^{\mathbb R}\Gamma is scaled as well. This yields the following picture under projective determinacy, with the scaled pointclasses encircled:

fig3

This finishes the classical scale theory. The next step is to analyse the pointclasses of the form \bf\Sigma_n^{J_\alpha(\mathbb R)} and \bf\Pi_n^{J_\alpha(\mathbb R)}, which is due to Steel. Note that \bf\Sigma^1_n=\bf\Sigma_n^{J_0(\mathbb R)} and \bf\Pi^1_n=\bf\Pi_n^{J_0(\mathbb R)}, so all the classical theorems cover the case where \alpha=0 and Steel’s analysis focuses on the \alpha>0 case. But that’s not until next time.