# Prewellordering

In set theory, a prewellordering is a binary relation ${\displaystyle \leq }$ that is transitive, connex, and wellfounded (more precisely, the relation ${\displaystyle x\leq y\land y\nleq x}$ is wellfounded). In other words, if ${\displaystyle \leq }$ is a prewellordering on a set ${\displaystyle X}$, and if we define ${\displaystyle \sim }$ by

${\displaystyle x\sim y\iff x\leq y\land y\leq x}$

then ${\displaystyle \sim }$ is an equivalence relation on ${\displaystyle X}$, and ${\displaystyle \leq }$ induces a wellordering on the quotient ${\displaystyle X/\sim }$. The order-type of this induced wellordering is an ordinal, referred to as the length of the prewellordering.

A norm on a set ${\displaystyle X}$ is a map from ${\displaystyle X}$ into the ordinals. Every norm induces a prewellordering; if ${\displaystyle \phi :X\to Ord}$ is a norm, the associated prewellordering is given by

${\displaystyle x\leq y\iff \phi (x)\leq \phi (y)}$

Conversely, every prewellordering is induced by a unique regular norm (a norm ${\displaystyle \phi :X\to Ord}$ is regular if, for any ${\displaystyle x\in X}$ and any ${\displaystyle \alpha <\phi (x)}$, there is ${\displaystyle y\in X}$ such that ${\displaystyle \phi (y)=\alpha }$).

## Prewellordering property

If ${\displaystyle {\boldsymbol {\Gamma }}}$  is a pointclass of subsets of some collection ${\displaystyle {\mathcal {F}}}$  of Polish spaces, ${\displaystyle {\mathcal {F}}}$  closed under Cartesian product, and if ${\displaystyle \leq }$  is a prewellordering of some subset ${\displaystyle P}$  of some element ${\displaystyle X}$  of ${\displaystyle {\mathcal {F}}}$ , then ${\displaystyle \leq }$  is said to be a ${\displaystyle {\boldsymbol {\Gamma }}}$ -prewellordering of ${\displaystyle P}$  if the relations ${\displaystyle <^{*}}$  and ${\displaystyle \leq ^{*}}$  are elements of ${\displaystyle {\boldsymbol {\Gamma }}}$ , where for ${\displaystyle x,y\in X}$ ,

1. ${\displaystyle x<^{*}y\iff x\in P\land [y\notin P\lor \{x\leq y\land y\not \leq x\}]}$
2. ${\displaystyle x\leq ^{*}y\iff x\in P\land [y\notin P\lor x\leq y]}$

${\displaystyle {\boldsymbol {\Gamma }}}$  is said to have the prewellordering property if every set in ${\displaystyle {\boldsymbol {\Gamma }}}$  admits a ${\displaystyle {\boldsymbol {\Gamma }}}$ -prewellordering.

The prewellordering property is related to the stronger scale property; in practice, many pointclasses having the prewellordering property also have the scale property, which allows drawing stronger conclusions.

### Examples

${\displaystyle {\boldsymbol {\Pi }}_{1}^{1}}$  and ${\displaystyle {\boldsymbol {\Sigma }}_{2}^{1}}$  both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every ${\displaystyle n\in \omega }$ , ${\displaystyle {\boldsymbol {\Pi }}_{2n+1}^{1}}$  and ${\displaystyle {\boldsymbol {\Sigma }}_{2n+2}^{1}}$  have the prewellordering property.

### Consequences

#### Reduction

If ${\displaystyle {\boldsymbol {\Gamma }}}$  is an adequate pointclass with the prewellordering property, then it also has the reduction property: For any space ${\displaystyle X\in {\mathcal {F}}}$  and any sets ${\displaystyle A,B\subseteq X}$ , ${\displaystyle A}$  and ${\displaystyle B}$  both in ${\displaystyle {\boldsymbol {\Gamma }}}$ , the union ${\displaystyle A\cup B}$  may be partitioned into sets ${\displaystyle A^{*},B^{*}}$ , both in ${\displaystyle {\boldsymbol {\Gamma }}}$ , such that ${\displaystyle A^{*}\subseteq A}$  and ${\displaystyle B^{*}\subseteq B}$ .

#### Separation

If ${\displaystyle {\boldsymbol {\Gamma }}}$  is an adequate pointclass whose dual pointclass has the prewellordering property, then ${\displaystyle {\boldsymbol {\Gamma }}}$  has the separation property: For any space ${\displaystyle X\in {\mathcal {F}}}$  and any sets ${\displaystyle A,B\subseteq X}$ , ${\displaystyle A}$  and ${\displaystyle B}$  disjoint sets both in ${\displaystyle {\boldsymbol {\Gamma }}}$ , there is a set ${\displaystyle C\subseteq X}$  such that both ${\displaystyle C}$  and its complement ${\displaystyle X\setminus C}$  are in ${\displaystyle {\boldsymbol {\Gamma }}}$ , with ${\displaystyle A\subseteq C}$  and ${\displaystyle B\cap C=\emptyset }$ .

For example, ${\displaystyle {\boldsymbol {\Pi }}_{1}^{1}}$  has the prewellordering property, so ${\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}$  has the separation property. This means that if ${\displaystyle A}$  and ${\displaystyle B}$  are disjoint analytic subsets of some Polish space ${\displaystyle X}$ , then there is a Borel subset ${\displaystyle C}$  of ${\displaystyle X}$  such that ${\displaystyle C}$  includes ${\displaystyle A}$  and is disjoint from ${\displaystyle B}$ .