Prewellordering

Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Green tickY Template:N& Template:N& Template:N& Template:N& Template:N& Green tickY Template:N& Template:N& Preorder (Quasiorder) Template:N& Template:N& Template:N& Template:N& Template:N& Template:N& Green tickY Template:N& Template:N& Partial order Template:N& Green tickY Template:N& Template:N& Template:N& Template:N& Green tickY Template:N& Template:N& Total preorder Template:N& Template:N& Green tickY Template:N& Template:N& Template:N& Green tickY Template:N& Template:N& Total order Template:N& Green tickY Green tickY Template:N& Template:N& Template:N& Green tickY Template:N& Template:N& Prewellordering Template:N& Template:N& Green tickY Green tickY Template:N& Template:N& Green tickY Template:N& Template:N& Well-quasi-ordering Template:N& Template:N& Template:N& Green tickY Template:N& Template:N& Green tickY Template:N& Template:N& Well-ordering Template:N& Green tickY Green tickY Green tickY Template:N& Template:N& Green tickY Template:N& Template:N& Lattice Template:N& Green tickY Template:N& Template:N& Green tickY Green tickY Green tickY Template:N& Template:N& Join-semilattice Template:N& Green tickY Template:N& Template:N& Green tickY Template:N& Green tickY Template:N& Template:N& Meet-semilattice Template:N& Green tickY Template:N& Template:N& Template:N& Green tickY Green tickY Template:N& Template:N& Strict partial order Template:N& Green tickY Template:N& Template:N& Template:N& Template:N& Template:N& Green tickY Green tickY Strict weak order Template:N& Green tickY Template:N& Template:N& Template:N& Template:N& Template:N& Green tickY Green tickY Strict total order Template:N& Green tickY Green tickY Template:N& Template:N& Template:N& Template:N& Green tickY Green tickY Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\ne \varnothing :$ $\begin{array}{cc}& aRb\\ \Rightarrow & bRa\end{array}$ $\begin{array}{cc}aRb\text{ and }& bRa\\ \Rightarrow a=& b\end{array}$ $\begin{array}{cc}a\ne & b\Rightarrow \\ aRb\text{ or }& bRa\end{array}$ $\begin{array}{c}minS\\ \text{exists}\end{array}$ $\begin{array}{c}a\vee b\\ \text{exists}\end{array}$ $\begin{array}{c}a\wedge b\\ \text{exists}\end{array}$ $aRa$ $\text{not }aRa$ $\begin{array}{c}aRb\Rightarrow \\ \text{not }bRa\end{array}$
Green tickY indicates that the column's property is always true for the row's term (at the very left), while Template:N& 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 Green tickY in the "Symmetric" column and Template:N& 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 $\le$ 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\le y\text{ and }y\nleqq x$ is a well-founded relation.

Prewellordering on a set

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

1. Reflexivity: $x\le 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\le y$ or $y\le 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\le s$ for all $s\in S.$
   • This condition is equivalent to the induced strict preorder $x<y$ defined by $x\le y$ and $y\nleqq x$ being a well-founded relation.

A homogeneous binary relation $\le$ 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,$ $x\le y$ if and only if $\pi (x)\lesssim \pi (y).$

Examples

File:Prewellordering example x div 4 leq y div 5.gif

Hasse diagram of the prewellordering $\lfloor x/4\rfloor \le \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.

File:Prewellordering example svg.svg

Hasse diagram of the prewellordering $\lfloor x/4\rfloor \le \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:=\mathrm{Finite}(A)$ of all finite subsets of $A$ defined by $S\le T$ if and only if $|S|\le |T|$ (where $|\cdot |$ denotes the set's cardinality) is a prewellordering.

Properties

If $\le$ is a prewellordering on $X,$ then the relation $\sim$ defined by $$x\sim y\text{ if and only if }x\le y\wedge y\le x$$ is an equivalence relation on $X,$ and $\le$ 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 $\varphi :X\to Ord$ is a norm, the associated prewellordering is given by $$x\le y\text{ if and only if }\varphi (x)\le \varphi (y)$$ Conversely, every prewellordering is induced by a unique regular norm (a norm $\varphi :X\to Ord$ is regular if, for any $x\in X$ and any $\alpha <\varphi (x),$ there is $y\in X$ such that $\varphi (y)=\alpha$).

Prewellordering property

If $𝜞$ is a pointclass of subsets of some collection $ℱ$ of Polish spaces, $ℱ$ closed under Cartesian product, and if $\le$ is a prewellordering of some subset $P$ of some element $X$ of $ℱ,$ then $\le$ is said to be a $𝜞$-prewellordering of $P$ if the relations ${<}^{\ast }$ and ${\le }^{\ast }$ are elements of $𝜞,$ where for $x,y\in X,$

1. $x{<}^{\ast }y\text{ if and only if }x\in P\wedge (y\notin P\vee (x\le y\wedge y\le ̸x))$
2. $x{\le }^{\ast }y\text{ if and only if }x\in P\wedge (y\notin P\vee x\le y)$

$𝜞$ is said to have the prewellordering property if every set in $𝜞$ admits a $𝜞$-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

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

Consequences

Reduction

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

Separation

If $𝜞$ is an adequate pointclass whose dual pointclass has the prewellordering property, then $𝜞$ has the separation property: For any space $X\in ℱ$ and any sets $A,B\subseteq X,$ $A$ and $B$ disjoint sets both in $𝜞,$ there is a set $C\subseteq X$ such that both $C$ and its complement $X\setminus C$ are in $𝜞,$ with $A\subseteq C$ and $B\cap C=\varnothing .$

For example, ${𝜫}_1^1$ has the prewellordering property, so ${𝜮}_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

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

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.