Prewellordering

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

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

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

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

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

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{\text{ if and only if }}\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 }$).

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

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

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=\varnothing .}$

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