Prewellordering

Template:Short description Template:Stack 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:Template:Sfn

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).$Template:Sfn

Examples

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.

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.Template:Sfn

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.

Template:AnchorA 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

• Template:Cite book
• Template:Cite book