Scales 101 - Part I: What & Why?

In classical descriptive set theory a need arose to analyse the analytical and projective hierarchies more abstractly, isolating the key structural properties of the various levels. I’ll describe these here and how these concepts can be generalised to the so-called scale property. This is going to be the first post in a series on scales, where we here will focus on what scales are and why they’re useful. The next ones will be concerned with where we find scales and how we construct new scales from existing ones.

This post is part of a series on scales:

Before we start let’s fix some terminology. Throughout, I’ll fix some space $X$ which is any space of the form $(\omega^\omega)^k\times\omega^m$ for some $k,m\in\omega$. We call the subsets of such $X$ pointsets, and we also call sets of pointsets pointclasses, which we denote by $\Gamma$. Okay, that being settled, let’s get started.

Let’s start off chronologically with some of the structural properties of pointclasses leading up to the scale notion. One of these properties is the separation property, which holds for a pointclass $\Gamma$ if any disjoint pair $A,B\in\Gamma$ can be separated by some $C\in\Gamma\cap\lnot\Gamma$, meaning it contains one and is disjoint from the other. Taking $\Gamma=\bf\Sigma^1_1$, the analytic sets, this is a theorem due to Lusin (Лýзин): every disjoint pair of analytic sets can be separated by a Borel set.

Another such property is the reduction property, stating that any pair $A,B\in\Gamma$ can be reduced by a pair $A’,B’\in\Gamma$, meaning that $A’\subseteq A$, $B’\subseteq B$ and $A’\cap B’=\emptyset$. A proto-typical example here is the coanalytic (i.e. $\bf\Pi^1_1$) sets. A connection between these two properties is the following.

Proposition. If a pointclass $\Gamma$ has the reduction property then $\lnot\Gamma$ has the separation property.

Proof. Let $A,B\in\lnot\Gamma$ be disjoint. Then simply reduce $\lnot A,\lnot B\in\Gamma$ to $(\lnot A)‘,(\lnot B)’\in\Gamma$ and then $\lnot(\lnot A)'\in\lnot\Gamma$ works. QED

Our last ‘basic’ property is the uniformisation property, stating that given any binary relation $A\in\Gamma$ we can find a uniformisation $A^*\subseteq A$, $A^*\in\Gamma$, such that $\exists yA(x,y)$ holds iff $\exists!yA^*(x,y)$ holds. I.e. it’s a ‘choice principle for $\Gamma$’.

A natural thing to do is try to find out what these properties have in common, to find out what essential properties are needed to carry out known classical proofs, enabling generalisation. The first such generalisation is the prewellordering property. Recall that a prewellordering is an ordering which is reflexive, transitive, total and wellfounded.

Then a pointclass $\Gamma$ is said to have the prewellordering property if every $A\in\Gamma$ has a prewellordering $\leq_A$ such that there exist binary relations $\leq_A^\Gamma\in\Gamma$ and $\leq_A^{\lnot\Gamma}\in\lnot\Gamma$ satisfying that for every $y\in A$, $x\in A\land x\leq_A y$ iff $x\leq_A^\Gamma y$ iff $x\leq_A^{\lnot\Gamma} y$. The prewellordering property is capturing some of the above properties.

Proposition. Let $\Gamma$ be a pointclass that contains all the clopen sets and is closed under continuous preimages as well as finite intersections and unions. If $\Gamma$ has the prewellordering property then
$\Gamma$ has the reduction property;
$\lnot\Gamma$ has the separation property;
$\Gamma$ has the number uniformisation property, i.e. that every $A\subseteq X\times\omega$ in $\Gamma$ has a uniformisation in $\Gamma$.

Proof. (1) Let $A,B\in\Gamma$ and define the disjoint union $X$ as $(x,n)\in X$ iff $x\in A\land n=0$ or $x\in B\land n=1$. By the properties on $\Gamma$ we see that $X\in\Gamma$ as well. Let $\leq_X\in\Gamma$ be a prewellordering of $X$, and then define $A^*:=\{x\mid (x,0)<_X(x,1)\}$ and $B^*:=\{x\mid (x,1)\leq_X (x,0)\}$. Then $A^*,B^*\in\Gamma$ and they reduce $A,B$.

(2) follows from the previous proposition. For (3), let $X\subseteq X\times\omega$, $X\in\Gamma$. Define $X^*$ as the set of $(x,n)\in X$ with $n$ chosen to be the least integer such that $(x,n)$ has minimal $\leq_X$-rank. Then $X^*$ uniformises $X$. To see that $X^*\in\Gamma$, note that $(x,n)\in X^*$ iff $(x,n)\in X\land\forall m[(x,n)\leq_X (x,m)]\land\forall m[(x,n)<_X(x,m)\lor n\leq m]$. QED

So we get quite close to connecting the three properties now. To take this final step we consider scales. Note first that to every prewellordering $\leq_A$ on some set $A$ we can consider its corresponding rank function $\varphi:A\to\textsf{On}$, and to every function $\varphi:A\to\textsf{On}$ we can define a prewellordering $\leq_A$ on $A$ as $x\leq_A y$ iff $\varphi(x)\leq \varphi(y)$. We call these functions norms. The prewellordering property precisely postulates the existence of a “$\Gamma$-norm” on every $A\in\Gamma$, so a way to generalise this is to postulate the existence of many norms on $A$ – this is exactly what a scale is.

More precisely, a scale on $A$ is a sequence $\left<\varphi_n\mid n<\omega\right<$ of norms $\varphi_n:A\to\textsf{On}$ such that whenever we have a sequence $\left< x_n\mid n<\omega\right<$ of elements of $A$ satisfying that, for some $x$,

(convergence) $x_n\to x$;
(norm-convergence) $\varphi_k(x_n)\to\alpha_k$ for all $k<\omega$;

then $x\in A$ and $\varphi_n(x)\leq\alpha_n$ for every $n<\omega$. Now, a pointclass $\Gamma$ is then said to have the scale property, or to be scaled, if every $A\in\Gamma$ has a $\Gamma$-scale, which is simply that each prewellordering ,associated to every norm $\varphi_n$ in the scale, satisfies the criteria given in the prewellordering property. This gives us enough strength to yield the full uniformisation property.

Proposition. Let $\Gamma$ be a scaled pointclass that contains all the Borel sets and is closed under Borel preimages as well as countable intersections, finite unions and universal quantifiers. Then
$\Gamma$ has the prewellordering property;
$\Gamma$ has the reduction property;
$\lnot\Gamma$ has the separation property;
$\Gamma$ has the uniformisation property.

Proof. (1) is clear by definition and (2)-(3) was shown in the above proposition, so we just have to show (4). Let $A\subseteq X$ be a binary relation in $\Gamma$ and let $\vec\varphi$ be $\Gamma$-scale on $A$. We first build a new scale $\vec\psi$ out of $\vec\varphi$ such that (a) if $\psi_n(x)\leq\psi_n(y)$ then $\forall m\leq n:\psi_m(x)\leq\psi_m(y)$ and (b) If $\vec x\subseteq A$ and $\psi_k(x_n)\to\alpha_k$ for all $k<\omega$ then $x_n\to x$ for some $x\in A$ (a scale satisfying these two conditions is called a very good $\Gamma$-scale).

Let $f:\mathbb R\to X$ be a continuous bijection and let $A’:=f^{-1}[A]$. By our closure properties on $\Gamma$ it suffices to build a very good $\Gamma$-scale $\vec\psi$ on $A’$, which then implies that $\vec\psi\circ f^{-1}$ is a very good $\Gamma$-scale on $A$. In other words, we may assume without loss of generality that $A\subseteq\mathbb R$. We then define $\vec\psi$ as

$$ \psi_n(x):=G^n(\left<\varphi_0(x),x_0,\dots,\varphi_n(x),x_n \right<), $$

where we view $\mathbb R$ as the Baire space $\omega^\omega$ as usual, and $G^n:\textsf{On}^n\to\textsf{On}$ being the ($n$-dimensional) Gödel pairing $G^n(x_1,\dots,x_n):=G(G(\cdots G(G(x_1,x_2),x_3)\cdots)$. It isn’t too hard to see that $\vec\psi$ satisfies (a)-(b), so we need to show that it’s a $\Gamma$-scale. Let $y\in A$. then note that $x\in A\land\psi_n(x)\leq\psi_n(y)$ holds iff

$x<_{\varphi_0}^\Gamma y$; or
$x\leq_{\varphi_0}^\Gamma y\land y\leq_{\varphi_0}^\Gamma x\land x_0 < y_0$; or
$x\leq_{\varphi_0}^\Gamma y\land y\leq_{\varphi_0}^\Gamma x\land x_0=y_0\land x<_{\varphi_1}^\Gamma y$; or…

and the analogous property for $\lnot\Gamma$ holds as well, showing that $\psi_n$ is a $\Gamma$-norm for all $n<\omega$, making $\vec\psi$ a very good $\Gamma$-scale.

The great thing about these very good scales is that given such a scale $\vec\chi$ on a set $B$ we can use it to pick a canonical element of $B$. Indeed, since the definition ensures that each prewellordering $\leq_{\chi_{n+1}}$ refines the previous one $\leq_{\chi_n}$, we can define $A_n:=\{x\in A\mid \chi_n(x)\text{ is least}\}$, so that $\bigcap_{n<\omega}A_n=\{x\}$ for some $x\in A$ – this is our canonical element.

Going back to our binary relation $A\subseteq X$, let $\vec\psi$ be a very good $\Gamma$-scale on $A$, as produced above. Define new scales $\vec\psi^x$ on the cross-sections $A_x:=\{y\in A\mid (x,y)\in A\}$ as given by $\psi^x_n(y):=\psi_n(x,y)$. These new scales are then also very good $\Gamma$-scales on $A_x$, for each $x\in A$. But then, by the procedure in the above paragraph, we can choose canonical elements $y_x\in A_x$ for every $x\in A$, so that we can define a uniformisation $A^*\subseteq A$ as $A^*(x,y)$ iff $y=y_x$. Further, $A^*\in\Gamma$, since

$$ A^*(x,y)\text{ iff }\forall n\forall z[(x,y)\leq_{\psi_n}(x,z)]. $$

QED

Sooo… the conclusion for now is then that the scaled pointclasses really generalise all the previously mentioned properties. But can we even find scaled pointclasses anywhere? This leads us to Moschovakis’ periodicity theorems and Steel’s analysis of scales in $L(\mathbb R)$. More on that next time!