Jump to content

Prewellordering

From Wikipedia, the free encyclopedia
Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total, Semiconnex Anti-
reflexive
Equivalence relation Green tickY Green tickY
Preorder (Quasiorder) Green tickY
Partial order Green tickY Green tickY
Total preorder Green tickY Green tickY
Total order Green tickY Green tickY Green tickY
Prewellordering Green tickY Green tickY Green tickY
Well-quasi-ordering Green tickY Green tickY
Well-ordering Green tickY Green tickY Green tickY Green tickY
Lattice Green tickY Green tickY Green tickY Green tickY
Join-semilattice Green tickY Green tickY Green tickY
Meet-semilattice Green tickY Green tickY Green tickY
Strict partial order Green tickY Green tickY Green tickY
Strict weak order Green tickY Green tickY Green tickY
Strict total order Green tickY Green tickY Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions, for all and
Green tickY indicates that the column's property is always true for 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 Green tickY 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.

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 set

[edit]

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]

Examples

[edit]
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

[edit]

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

[edit]

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

[edit]

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

Consequences

[edit]

Reduction

[edit]

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

[edit]

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 also

[edit]
  • Descriptive set theory – Subfield of mathematical logic
  • Graded poset – partially ordered set equipped with a rank function – 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

References

[edit]
  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.