# Prewellordering

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

$x\sim y\iff x\leq y\land y\leq x$ then $\sim$ is an equivalence relation on $X$ , and $\leq$ induces a wellordering on the quotient $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 $X$ is a map from $X$ into the ordinals. Every norm induces a prewellordering; if $\phi :X\to Ord$ is a norm, the associated prewellordering is given by

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

## Prewellordering property

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

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

${\boldsymbol {\Gamma }}$  is said to have the prewellordering property if every set in ${\boldsymbol {\Gamma }}$  admits a ${\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

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

### Consequences

#### Reduction

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

#### Separation

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

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