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

<ol> <li>[Reflexivity](https://bliptext.com/articles/reflexive-relation): x \leq x for all x \in X. </li> <li>[Transitivity](https://bliptext.com/articles/transitive-relation): if x < y and y < z then x < z for all </li> <li>[Total/Strongly connected](https://bliptext.com/articles/strongly-connected-relation): x \leq y or y \leq x for all x, y \in X.</li> <li>for every non-empty subset there exists some m \in S such that m \leq s for all s \in S. </ol> A [homogeneous binary relation](https://bliptext.com/articles/homogeneous-binary-relation) \,\leq\, on X is a prewellordering if and only if there exists a [surjection](https://bliptext.com/articles/surjection) into a [well-ordered set](https://bliptext.com/articles/well-ordered-set) such that for all x, y \in X, x \leq y if and only if

Examples

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

Properties

If \leq is a prewellordering on X, then the relation \sim defined by 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 is a norm, the associated prewellordering is given by Conversely, every prewellordering is induced by a unique regular norm (a norm is regular if, for any x \in X and any there is y \in X such that ).

Prewellordering property

If 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 then \leq is said to be a -prewellordering of P if the relations <^* and \leq^* are elements of where for x, y \in X, 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

and both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every and 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 and any sets A and B both in the union A \cup B may be partitioned into sets A^, B^, both in such that and

Separation

If is an adequate pointclass whose dual pointclass has the prewellordering property, then has the separation property: For any space and any sets A and B disjoint sets both in there is a set such that both C and its complement are in with and For example, has the prewellordering property, so 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.