Norm (descriptive Set Theory)

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 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,$ $x \leq y$ if and only if $\pi(x) \lesssim \pi(y).$

Examples

Given a set $A,$ the binary relation on the set $X := \operatorname(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 x \leq y \land y \leq x$
is an equivalence relation on $X,$ and $\leq$ induces a wellordering on the quotient $X / .$ 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 \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$ is a pointclass of subsets of some collection $\mathcal$ of Polish spaces, $\mathcal$ closed under Cartesian product, and if $\leq$ is a prewellordering of some subset $P$ of some element $X$ of $\mathcal,$ then $\leq$ is said to be a $\boldsymbol$-prewellordering of $P$ if the relations $<^*$ and $\leq^*$ are elements of $\boldsymbol,$ where for $x, y \in X,$
# $x <^* y \text x \in P \land (y \notin P \lor (x \leq y \land y \not\leq x))$
# $x \leq^* y \text x \in P \land (y \notin P \lor x \leq y)$

$\boldsymbol$ is said to have the prewellordering property if every set in $\boldsymbol$ admits a $\boldsymbol$-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^1_1$ and $\boldsymbol^1_2$ both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every $n \in \omega,$ $\boldsymbol^1_$ and $\boldsymbol^1_$
have the prewellordering property.

Consequences

Reduction

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

Separation

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

For example, $\boldsymbol^1_1$ has the prewellordering property, so $\boldsymbol^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

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

References

*
*

{{Order theory

Descriptive set theory
Order theory
Wellfoundedness