Prewellordering
Encyclopedia
In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, a prewellordering is a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

 that is transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

, wellfounded
Well-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...

, and total
Total relation
In mathematics, a binary relation R over a set X is total if for all a and b in X, a is related to b or b is related to a .In mathematical notation, this is\forall a, b \in X,\ a R b \or b R a....

. In other words, if is a prewellordering on a set , and if we define by
then is an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

 on , and induces a wellordering on the quotient . The order-type of this induced wellordering is an ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...

, 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
Pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a point is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by some sort of definability property; for example, the...

 of subsets of some collection of Polish space
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named because they were first extensively studied by Polish...

s, closed under Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...

, 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
Scale property
In the mathematical discipline of descriptive set theory, a scale is a certain kind of object defined on a set of points in some Polish space...

; 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.

Reduction

If is an adequate pointclass
Adequate pointclass
In the mathematical field of descriptive set theory, a pointclass can be called adequate if it contains all recursive pointsets and is closed under recursive substitution, bounded universal and existential quantification and preimages by recursive functions....

 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
Adequate pointclass
In the mathematical field of descriptive set theory, a pointclass can be called adequate if it contains all recursive pointsets and is closed under recursive substitution, bounded universal and existential quantification and preimages by recursive functions....

 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
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

  are in , with and .

For example, has the prewellordering property, so has the separation property. This means that if and are disjoint analytic
Analytic set
In descriptive set theory, a subset of a Polish space X is an analytic set if it is a continuous image of a Polish space. These sets were first defined by and his student .- Definition :There are several equivalent definitions of analytic set...

 subsets of some Polish space , then there is a Borel
Borel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets through the operations of countable union, countable intersection, and relative complement...

 subset of such that includes and is disjoint from .

See also

  • Descriptive set theory
    Descriptive set theory
    In mathematical logic, descriptive set theory is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces...

  • Scale property
    Scale property
    In the mathematical discipline of descriptive set theory, a scale is a certain kind of object defined on a set of points in some Polish space...

  • Graded poset
    Graded poset
    In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...

    – a graded poset is analogous to a prewellordering with a norm, replacing a map to the ordinals with a map to the integers
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK