Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.
All definitions tacitly require the
homogeneous relation be
transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.
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]
Properties
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 property
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.
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 and both in the union may be partitioned into sets 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 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
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