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.

This post is part of a series on scales:

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(\left< m,n\right<)=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 <_x n\}$ and define, for $x,y\in A$ and $n<\omega$,

$$ x\leq_n y\text{ 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 $\left<\varphi_n\mid n<\omega\right<$ is a $\Pi^1_1$-scale on $A$.

Claim. $\vec\varphi$ is a scale.

Proof of claim. Let $\left< x_i\mid i<\omega\right<$ 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}\{\left<\varphi_0(x,\alpha),\alpha_0, \dots, \varphi_n(x,\alpha),\alpha_n\right<\mid(x,\alpha)\in A\}, $$

where $\vec\varphi$ is the $\Gamma$-scale given by assumption, and $\left< \cdot,\dots,\cdot \right<$ 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:

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.