Prewellordering - AbsoluteAstronomy.com

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

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

, 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

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

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

, 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

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

is an adequate pointclass

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

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

such that

includes

and is disjoint from

Prewellordering property

Examples

Reduction

Separation

See also