Prewellordering

From Wikipedia, the free encyclopedia

In set theory, a prewellordering is a binary relation that is transitive, wellfounded, and total. 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 $α < φ(x)$ , there is $y\in X$ such that $φ(y) = α$ ).

1 Prewellordering property
- 1.1 Examples
- 1.2 Consequences
  - 1.2.1 Reduction
  - 1.2.2 Separation
2 References

[edit] 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$ ,

$x<^*y\iff x\in P\land[y\notin P\lor\{x\leq y\land y\not\leq x\}]$
$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.

[edit] Examples

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

[edit] Consequences

[edit] 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$ .

[edit] 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$ .