Prewellordering

 ( Descriptive Set Theory ) 

In set theory, a prewellordering on a set $X$ is a preorder $\backslash leq$ on $X$ (a transitive and reflexive relation on $X$) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation defined by $x\; \backslash leq\; y\; \backslash text\{\; and\; \}\; y\; \backslash nleq\; x$ is a well-founded relation.

---

Prewellordering on a set A prewellordering on a set $X$ is a homogeneous binary relation $\backslash ,\backslash leq\backslash ,$ on $X$ that satisfies the following conditions:

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

---

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

---

Properties 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 set $X\; /\; \{\backslash sim\}.$ The order-type of this induced wellordering is an ordinal number, 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 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$).

---

Prewellordering property If $\backslash boldsymbol\{\backslash Gamma\}$ is a pointclass of subsets of some collection $\backslash mathcal\{F\}$ of , $\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.

---

Examples $\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 , 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^*,$ 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 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 set subsets of some Polish space $X,$ then there is a Borel set subset $C$ of $X$ such that $C$ includes $A$ and is disjoint from $B.$

---

See also

• – a graded poset is analogous to a prewellordering with a norm, replacing a map to the ordinals with a map to the natural numbers

• Moschovakis, Yiannis N. (1980). 9780080963198, North Holland. . ISBN 9780080963198
• Yiannis N. Moschovakis (2025). 9780387316093, Springer. ISBN 9780387316093

Post Comment