In set theory, a prewellordering is a binary relation that is transitive, wellfounded, and connected. In other words, if $\backslash leq$ is a prewellordering on a set $X$, and if we define $\backslash sim$ by

$x\backslash sim\; y\backslash iff\; x\backslash leq\; y\; \backslash land\; y\backslash leq\; x$

then $\backslash sim$ is an equivalence relation on $X$, and $\backslash leq$ induces a wellordering on the quotient $X/\backslash 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 $\backslash phi:X\backslash to\; Ord$ is a norm, the associated prewellordering is given by

$x\backslash leq\; y\backslash iff\backslash phi(x)\backslash leq\backslash phi(y)$

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

Prewellordering property

---

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

2. $x\backslash leq^*\; y\backslash iff\; x\backslash in\; P\backslash landP\backslash lor\; x\backslash leq\; y$

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

Examples

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

Consequences

Reduction

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

Separation

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

For example, $\backslash boldsymbol\{\backslash Pi\}^1\_1$ has the prewellordering property, so $\backslash boldsymbol\{\backslash 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$.

References

---

Descriptive set theory | Order theory