A prewellordering on a set ${\displaystyle X}$  is a homogeneous binary relation ${\displaystyle \,\leq \,}$  on ${\displaystyle X}$  that satisfies the following conditions:^[1]

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

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

Examples edit

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

Properties edit

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

A norm on a set ${\displaystyle X}$  is a map from ${\displaystyle X}$  into the ordinals. Every norm induces a prewellordering; if ${\displaystyle \phi :X\to Ord}$  is a norm, the associated prewellordering is given by

If ${\displaystyle {\boldsymbol {\Gamma }}}$  is a pointclass of subsets of some collection ${\displaystyle {\mathcal {F}}}$  of Polish spaces, ${\displaystyle {\mathcal {F}}}$  closed under Cartesian product, and if ${\displaystyle \leq }$  is a prewellordering of some subset ${\displaystyle P}$  of some element ${\displaystyle X}$  of ${\displaystyle {\mathcal {F}},}$  then ${\displaystyle \leq }$  is said to be a ${\displaystyle {\boldsymbol {\Gamma }}}$ -prewellordering of ${\displaystyle P}$  if the relations ${\displaystyle <^{*}}$  and ${\displaystyle \leq ^{*}}$  are elements of ${\displaystyle {\boldsymbol {\Gamma }},}$  where for ${\displaystyle x,y\in X,}$ 

1. ${\displaystyle x<^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))}$ 
2. ${\displaystyle x\leq ^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor x\leq y)}$ 

${\displaystyle {\boldsymbol {\Gamma }}}$  is said to have the prewellordering property if every set in ${\displaystyle {\boldsymbol {\Gamma }}}$  admits a ${\displaystyle {\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 edit

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

Consequences edit

Reduction edit

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

Separation edit

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

For example, ${\displaystyle {\boldsymbol {\Pi }}_{1}^{1}}$  has the prewellordering property, so ${\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}$  has the separation property. This means that if ${\displaystyle A}$  and ${\displaystyle B}$  are disjoint analytic subsets of some Polish space ${\displaystyle X,}$  then there is a Borel subset ${\displaystyle C}$  of ${\displaystyle X}$  such that ${\displaystyle C}$  includes ${\displaystyle A}$  and is disjoint from ${\displaystyle B.}$ 

• Descriptive set theory – Subfield of mathematical logic
• Graded poset – partially ordered set equipped with a rank function, sometimes called a ranked posetPages 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