In set theory, a prewellordering on a set is a preorder on (a transitive and reflexive relation on ) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation defined by is a well-founded relation.

Prewellordering on a setEdit

A prewellordering on a set   is a homogeneous binary relation   on   that satisfies the following conditions:[1]

  1. Reflexivity:   for all  
  2. Transitivity: if   and   then   for all  
  3. Total/Strongly connected:   or   for all  
  4. for every non-empty subset   there exists some   such that   for all  
    • This condition is equivalent to the induced strict preorder   defined by   and   being a well-founded relation.

A homogeneous binary relation   on   is a prewellordering if and only if there exists a surjection   into a well-ordered set   such that for all     if and only if  [1]


Hasse diagram of the prewellordering   on the non-negative integers, shown up to 29. Cycles are indicated in red and   denotes the floor function.
Hasse diagram of the prewellordering   on the non-negative integers, shown up to 18. The associated equivalence relation is   it identifies the numbers in each light red square.

Given a set   the binary relation on the set   of all finite subsets of   defined by   if and only if   (where   denotes the set's cardinality) is a prewellordering.[1]


If   is a prewellordering on   then the relation   defined by

is an equivalence relation on   and   induces a wellordering on the quotient   The order-type of this induced wellordering is an ordinal, referred to as the length of the prewellordering.

A norm on a set   is a map from   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   and any   there is   such that  ).

Prewellordering propertyEdit

If   is a pointclass of subsets of some collection   of Polish spaces,   closed under Cartesian product, and if   is a prewellordering of some subset   of some element   of   then   is said to be a  -prewellordering of   if the relations   and   are elements of   where for  


  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.


  and   both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every     and   have the prewellordering property.



If   is an adequate pointclass with the prewellordering property, then it also has the reduction property: For any space   and any sets     and   both in   the union   may be partitioned into sets   both in   such that   and  


If   is an adequate pointclass whose dual pointclass has the prewellordering property, then   has the separation property: For any space   and any sets     and   disjoint sets both in   there is a set   such that both   and its complement   are in   with   and  

For example,   has the prewellordering property, so   has the separation property. This means that if   and   are disjoint analytic subsets of some Polish space   then there is a Borel subset   of   such that   includes   and is disjoint from  

See alsoEdit

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


  1. ^ a b c Moschovakis 2006, p. 106.
  • 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.