# Prewellordering

In set theory, a prewellordering on a set $X$ is a preorder $\leq$ on $X$ (a transitive and reflexive relation on $X$ ) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation $x defined by $x\leq y{\text{ and }}y\nleq x$ is a well-founded relation.

## Prewellordering on a set

A prewellordering on a set $X$  is a homogeneous binary relation $\,\leq \,$  on $X$  that satisfies the following conditions:

1. Reflexivity: $x\leq x$  for all $x\in X.$
2. Transitivity: if $x  and $y  then $x  for all $x,y,z\in X.$
3. Total/Strongly connected: $x\leq y$  or $y\leq x$  for all $x,y\in X.$
4. for every non-empty subset $S\subseteq X,$  there exists some $m\in S$  such that $m\leq s$  for all $s\in S.$
• This condition is equivalent to the induced strict preorder $x  defined by $x\leq y$  and $y\nleq x$  being a well-founded relation.

A homogeneous binary relation $\,\leq \,$  on $X$  is a prewellordering if and only if there exists a surjection $\pi :X\to Y$  into a well-ordered set $(Y,\lesssim )$  such that for all $x,y\in X,$  ${\textstyle x\leq y}$  if and only if $\pi (x)\lesssim \pi (y).$ 

### Examples

Hasse diagram of the prewellordering $\lfloor x/4\rfloor \leq \lfloor y/5\rfloor$  on the non-negative integers, shown up to 29. Cycles are indicated in red and $\lfloor \cdot \rfloor$  denotes the floor function.

Hasse diagram of the prewellordering $\lfloor x/4\rfloor \leq \lfloor y/4\rfloor$  on the non-negative integers, shown up to 18. The associated equivalence relation is $\lfloor x/4\rfloor =\lfloor y/4\rfloor ;$  it identifies the numbers in each light red square.

Given a set $A,$  the binary relation on the set $X:=\operatorname {Finite} (A)$  of all finite subsets of $A$  defined by $S\leq T$  if and only if $|S|\leq |T|$  (where $|\cdot |$  denotes the set's cardinality) is a prewellordering.

### Properties

If $\leq$  is a prewellordering on $X,$  then the relation $\sim$  defined by

$x\sim y{\text{ if and only if }}x\leq y\land y\leq x$

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{\text{ if and only if }}\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{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))$
2. $x\leq ^{*}y{\text{ if and only if }}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=\varnothing .$

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.$