Prewellordering

Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true for the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

In set theory, a prewellordering on a set $X$ is a preorder $\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 $x<y$ defined by $x\leq y{\text{ and }}y\nleq x$ is a well-founded relation.

Prewellordering on a set

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

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

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

Examples

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

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

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

Properties

If $\leq$ is a prewellordering on $X,$ then the relation $\sim$ defined by $$x\sim y{\text{ if and only if }}x\leq y\land y\leq x$$ 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{\text{ if and only if }}\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 $\alpha <\phi (x),$ there is $y\in X$ such that $\phi (y)=\alpha$).

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

1. $x<^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))$
2. $x\leq ^{*}y{\text{ if and only if }}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.

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

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

Consequences

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

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

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

See also

• Descriptive set theory – Subfield of mathematical logic
• Graded poset – partially ordered set equipped with a rank functionPages displaying wikidata descriptions as a fallback – a graded poset is analogous to a prewellordering with a norm, replacing a map to the ordinals with a map to the natural numbers
• Scale property – kind of object in descriptive set theoryPages displaying wikidata descriptions as a fallback

References

• Moschovakis, Yiannis N. (1980). Descriptive Set Theory. Amsterdam: North Holland. ISBN 978-0-08-096319-8. OCLC 499778252.
• Moschovakis, Yiannis N. (2006). Notes on set theory. New York: Springer. ISBN 978-0-387-31609-3. OCLC 209913560.