Prewellordering
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In set theory, a prewellordering on a set X is a preorder \leq on X (a transitive and reflexive relation on X ) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation x defined by x \leq y \text{ and } y \nleq x is a well-founded relation.
In set theory, a prewellordering on a set X is a preorder \leq on X (a transitive and reflexive relation on X ) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation x defined by x \leq y \text{ and } y \nleq x is a well-founded relation.
Prewellordering on a set
A prewellordering on a set X is a homogeneous binary relation \,\leq\, on X that satisfies the following conditions: Reflexivity: x \leq x for all x \in X. Transitivity: if x and y then x for all x, y, z \in X. Total/Strongly connected: x \leq y or y \leq x for all x, y \in X. for every non-empty subset S \subseteq X, there exists some m \in S such that m \leq s for all s \in S. This condition is equivalent to the induced strict preorder x defined by x \leq y and y \nleq x being a well-founded relation. A homogeneous binary relation \,\leq\, on X is a prewellordering if and only if there exists a surjection \pi : X \to Y into a well-ordered set (Y, \lesssim) such that for all x, y \in X, x \leq y if and only if \pi(x) \lesssim \pi(y).
Examples
of the prewellordering \lfloor x/4\rfloor \leq \lfloor y/5\rfloor on the non-negative integers, shown up to 29. Cycles are indicated in red and \lfloor \cdot\rfloor denotes the floor function.]] of the prewellordering \lfloor x/4\rfloor \leq \lfloor y/4\rfloor on the non-negative integers, shown up to 18. The associated equivalence relation is \lfloor x/4\rfloor = \lfloor y/4\rfloor; it identifies the numbers in each light red square.]] Given a set A, the binary relation on the set X := \operatorname{Finite}(A) of all finite subsets of A defined by S \leq T if and only if |S| \leq |T| (where |\cdot| denotes the set's cardinality) is a prewellordering.
Properties
If \leq is a prewellordering on X, then the relation \sim defined by x \sim y \text{ if and only if } x \leq y \land y \leq x is an equivalence relation on X, and \leq induces a wellordering on the quotient X / {\sim}. The order-type of this induced wellordering is an ordinal, referred to as the length of the prewellordering. A norm on a set X is a map from X into the ordinals. Every norm induces a prewellordering; if \phi : X \to Ord is a norm, the associated prewellordering is given by x \leq y \text{ if and only if } \phi(x) \leq \phi(y) Conversely, every prewellordering is induced by a unique regular norm (a norm \phi : X \to Ord is regular if, for any x \in X and any \alpha there is y \in X such that \phi(y) = \alpha ).
Prewellordering property
If \boldsymbol{\Gamma} is a pointclass of subsets of some collection \mathcal{F} of Polish spaces, \mathcal{F} closed under Cartesian product, and if \leq is a prewellordering of some subset P of some element X of \mathcal{F}, then \leq is said to be a \boldsymbol{\Gamma} -prewellordering of P if the relations and \leq^* are elements of \boldsymbol{\Gamma}, where for x, y \in X, x x \leq^* y \text{ if and only if } x \in P \land (y \notin P \lor x \leq y) \boldsymbol{\Gamma} is said to have the prewellordering property if every set in \boldsymbol{\Gamma} admits a \boldsymbol{\Gamma} -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
\boldsymbol{\Pi}^1_1 and \boldsymbol{\Sigma}^1_2 both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every n \in \omega, \boldsymbol{\Pi}^1_{2n+1} and \boldsymbol{\Sigma}^1_{2n+2} have the prewellordering property.
Consequences
Reduction
If \boldsymbol{\Gamma} is an adequate pointclass with the prewellordering property, then it also has the reduction property: For any space X \in \mathcal{F} and any sets A, B \subseteq X, A and B both in \boldsymbol{\Gamma}, the union A \cup B may be partitioned into sets A^*, B^*, both in \boldsymbol{\Gamma}, such that A^* \subseteq A and B^* \subseteq B.
Separation
If \boldsymbol{\Gamma} is an adequate pointclass whose dual pointclass has the prewellordering property, then \boldsymbol{\Gamma} has the separation property: For any space X \in \mathcal{F} and any sets A, B \subseteq X, A and B disjoint sets both in \boldsymbol{\Gamma}, there is a set C \subseteq X such that both C and its complement X \setminus C are in \boldsymbol{\Gamma}, with A \subseteq C and B \cap C = \varnothing. For example, \boldsymbol{\Pi}^1_1 has the prewellordering property, so \boldsymbol{\Sigma}^1_1 has the separation property. This means that if A and B are disjoint analytic subsets of some Polish space X, then there is a Borel subset C of X such that C includes A and is disjoint from B.
See also
– a graded poset is analogous to a prewellordering with a norm, replacing a map to the ordinals with a map to the natural numbers
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1273597295 under CC BY-SA 4.0; modifications have been made.