 Prewellordering
Get Prewellordering essential facts below. View Videos or join the Prewellordering discussion. Add Prewellordering to your PopFlock.com topic list for future reference or share this resource on social media.
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$ .