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.

Before we start let’s fix some terminology. Throughout, I’ll fix some space \mathcal 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 \mathcal 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

  1. \Gamma has the reduction property;
  2. \lnot\Gamma has the separation property;
  3. \Gamma has the number uniformisation property, i.e. that every A\subseteq \mathcal 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\mathcal 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 \langle\varphi_n\mid n<\omega\rangle of norms \varphi_n:A\to\textsf{On} such that whenever we have a sequence \langle x_n\mid n<\omega\rangle of elements of A satisfying that, for some x,

  1. (convergence) x_n\to x;
  2. (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

  1. \Gamma has the prewellordering property;
  2. \Gamma has the reduction property;
  3. \lnot\Gamma has the separation property;
  4. \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\mathcal 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\mathcal 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(\langle\varphi_0(x),x_0,\hdots,\varphi_n(x),x_n \rangle),

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\mathcal 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) 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!

Here’s a link to the follow-up post