Prewellordering
Encyclopedia
In set theory
, a prewellordering is a binary relation
that is transitive
, wellfounded
, and total
. In other words, if is a prewellordering on a set , and if we define by
then 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 ).
of subsets of some collection of Polish space
s, 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.
have the prewellordering property.
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 .
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 .
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 pointclassPointclass
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 , andhave the prewellordering property.
Reduction
If is an adequate pointclassAdequate 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 pointclassAdequate 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 theoryDescriptive set theoryIn mathematical logic, descriptive set theory is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces...
- Scale propertyScale propertyIn 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 posetGraded posetIn 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