prewellordering

A prewellordering on a set $X$ is a homogeneous binary relation $\backslash ,\backslash leq\backslash ,$ on $X$ that satisfies the following conditions:{{sfn|Moschovakis|2006|p=106}}

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

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

Image:Prewellordering example x div 4 leq y div 5.gif of the prewellordering $\backslash lfloor\; x/4\backslash rfloor\; \backslash leq\; \backslash lfloor\; y/5\backslash rfloor$ on the non-negative integers, shown up to 29. Cycles are indicated in red and $\backslash lfloor\; \backslash cdot\backslash rfloor$ denotes the floor function.]]

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

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

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

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

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.

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

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 text\{\; if\; and\; only\; if\; \}\; x\; \backslash in\; P\; \backslash land\; (y\; \backslash notin\; P\; \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.

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.

$\backslash boldsymbol\{\backslash Pi\}^1\_1$ 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.

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^*,$ both in $\backslash boldsymbol\{\backslash Gamma\},$ such that $A^*\; \backslash subseteq\; A$ and $B^*\; \backslash subseteq\; B.$

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

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

• {{annotated link|Descriptive set theory}}
• {{annotated link|Graded poset}} – a graded poset is analogous to a prewellordering with a norm, replacing a map to the ordinals with a map to the natural numbers
• {{annotated link|Scale property}}

{{reflist}}

{{refbegin}}

• {{cite book|author=Moschovakis, Yiannis N.|authorlink=Yiannis N. Moschovakis|title=Descriptive Set Theory|publisher=North Holland|publication-place=Amsterdam|year=1980|isbn=978-0-08-096319-8|oclc=499778252|url=https://archive.org/details/descriptivesetth0000mosc|url-access=registration}}
• {{cite book|last=Moschovakis|first=Yiannis N.|author-link=Yiannis N. Moschovakis|title=Notes on set theory|publisher=Springer|publication-place=New York|year=2006|isbn=978-0-387-31609-3|oclc=209913560}}

{{refend}}

{{Order theory}}

Category:Descriptive set theory

Category:Order theory

Category:Wellfoundedness