{"history":[],"article":{"id":"ac044549-8272-416e-b417-7380f2051219","title":"Prewellordering","slug":"prewellordering","content":":::summary\n:::\n\n# \nIn [set theory](https://bliptext.com/articles/[set](https://bliptext.com/articles/set-mathematics)-theory), a **prewellordering** on a [set](https://bliptext.com/articles/set-mathematics) X is a [preorder](https://bliptext.com/articles/preorder) \\leq on X (a [transitive](https://bliptext.com/articles/transitive-relation) and [reflexive](https://bliptext.com/articles/reflexive-relation) relation on X) that is [strongly connected](https://bliptext.com/articles/strongly-connected-relation) (meaning that any two points are comparable) and [well-founded](https://bliptext.com/articles/well-founded-relation) in the sense that the induced relation x < y defined by is a [well-founded](https://bliptext.com/articles/well-founded-relation) relation.\n\n# Prewellordering on a set\nA **prewellordering** on a [set](https://bliptext.com/articles/set-mathematics) X is a [homogeneous binary relation](https://bliptext.com/articles/homogeneous-binary-relation) \\,\\leq\\, on X that satisfies the following conditions:\n

[Reflexivity](https://bliptext.com/articles/reflexive-relation): x \\leq x for all x \\in X.
[Transitivity](https://bliptext.com/articles/transitive-relation): if x < y and y < z then x < z for all
[Total/Strongly connected](https://bliptext.com/articles/strongly-connected-relation): x \\leq y or y \\leq x for all x, y \\in X.
for every non-empty subset there exists some m \\in S such that m \\leq s for all s \\in S.

\nA [homogeneous binary relation](https://bliptext.com/articles/homogeneous-binary-relation) \\,\\leq\\, on X is a prewellordering if and only if there exists a [surjection](https://bliptext.com/articles/surjection) into a [well-ordered set](https://bliptext.com/articles/well-ordered-set) such that for all x, y \\in X, x \\leq y if and only if\n\n## Examples\nGiven a set A, the binary relation on the set of all finite subsets of A defined by S \\leq T if and only if (where |\\cdot| denotes the set's [cardinality](https://bliptext.com/articles/cardinality)) is a prewellordering.\n# [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. | upload.wikimedia.org/wikipedia/commons/8/87/Prewellordering///example///svg.svg]\n\n## Properties\nIf \\leq is a prewellordering on X, then the relation \\sim defined by\nis an [equivalence relation](https://bliptext.com/articles/equivalence-relation) on X, and \\leq induces a [wellordering](https://bliptext.com/articles/wellordering) on the [quotient](https://bliptext.com/articles/quotient-set) X / {\\sim}.\nThe [order-type](https://bliptext.com/articles/order-type) of this induced wellordering is an [ordinal](https://bliptext.com/articles/ordinal-number), referred to as the **length** of the prewellordering.\nA **norm** on a set X is a map from X into the ordinals.\nEvery norm induces a prewellordering; if is a norm, the associated prewellordering is given by\nConversely, every prewellordering is induced by a unique **regular norm** (a norm is regular if, for any x \\in X and any there is y \\in X such that ).\n\n# Prewellordering property\nIf is a [pointclass](https://bliptext.com/articles/pointclass) of subsets of some collection \\mathcal{F} of [Polish spaces](https://bliptext.com/articles/polish-space), \\mathcal{F} closed under [Cartesian product](https://bliptext.com/articles/cartesian-product), and if \\leq is a **prewellordering** of some subset P of some element X of then \\leq is said to be a -**prewellordering** of P if the relations <^* and \\leq^* are elements of where for x, y \\in X,\nis said to have the **prewellordering property** if every set in admits a -prewellordering.\nThe prewellordering property is related to the stronger [scale property](https://bliptext.com/articles/scale-property); in practice, many pointclasses having the prewellordering property also have the [scale property](https://bliptext.com/articles/scale-property), which allows drawing stronger conclusions.\n\n## Examples\nand both have the prewellordering property; this is provable in [ZFC](https://bliptext.com/articles/zermelo-fraenkel-set-theory) alone.\nAssuming sufficient [large cardinals](https://bliptext.com/articles/large-cardinal), for every and\nhave the prewellordering property.\n\n## Consequences\n\n### Reduction\nIf is an [adequate pointclass](https://bliptext.com/articles/adequate-pointclass) with the prewellordering property, then it also has the **reduction property**: For any space and any sets A and B both in the union A \\cup B may be partitioned into sets A^*, B^*, both in such that and\n\n### Separation\nIf is an [adequate pointclass](https://bliptext.com/articles/adequate-pointclass) whose [dual pointclass](https://bliptext.com/articles/dual-pointclass) has the prewellordering property, then has the **separation property**: For any space and any sets A and B disjoint sets both in there is a set such that both C and its [complement](https://bliptext.com/articles/complement-set-theory) are in with and\nFor example, has the prewellordering property, so has the separation property.\nThis means that if A and B are disjoint [analytic](https://bliptext.com/articles/analytic-set) subsets of some Polish space X, then there is a [Borel](https://bliptext.com/articles/borel-set) subset C of X such that C includes A and is disjoint from B.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:44:08.519Z","updated_at":"2025-01-25T21:44:08.519Z","search_vector":"'prewellord':1","search_content":" \n \n\n# \nIn [[set](https://bliptext.com/articles/set-mathematics) theory](https://bliptext.com/articles/[set](https://bliptext.com/articles/set-mathematics)-theory), a **prewellordering** on a [set](https://bliptext.com/articles/set-mathematics) X is a [preorder](https://bliptext.com/articles/preorder) \\leq on X (a [transitive](https://bliptext.com/articles/transitive-relation) and [reflexive](https://bliptext.com/articles/reflexive-relation) relation on X) that is [strongly connected](https://bliptext.com/articles/strongly-connected-relation) (meaning that any two points are comparable) and [well-founded](https://bliptext.com/articles/well-founded-relation) in the sense that the induced relation x \n [Reflexivity](https://bliptext.com/articles/reflexive-relation): x \\leq x for all x \\in X. \n [Transitivity](https://bliptext.com/articles/transitive-relation): if x \n [Total/Strongly connected](https://bliptext.com/articles/strongly-connected-relation): x \\leq y or y \\leq x for all x, y \\in X. \n for every non-empty subset there exists some m \\in S such that m \\leq s for all s \\in S. \nA [homogeneous binary relation](https://bliptext.com/articles/homogeneous-binary-relation) \\,\\leq\\, on X is a prewellordering if and only if there exists a [surjection](https://bliptext.com/articles/surjection) into a [well-ordered set](https://bliptext.com/articles/well-ordered-set) such that for all x, y \\in X, x \\leq y if and only if\n\n## Examples\nGiven a set A, the binary relation on the set of all finite subsets of A defined by S \\leq T if and only if (where |\\cdot| denotes the set's [cardinality](https://bliptext.com/articles/cardinality)) is a prewellordering.\n# [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. | upload.wikimedia.org/wikipedia/commons/8/87/Prewellordering///example///svg.svg]\n\n## Properties\nIf \\leq is a prewellordering on X, then the relation \\sim defined by\nis an [equivalence relation](https://bliptext.com/articles/equivalence-relation) on X, and \\leq induces a [wellordering](https://bliptext.com/articles/wellordering) on the [quotient](https://bliptext.com/articles/quotient-set) X / {\\sim}.\nThe [order-type](https://bliptext.com/articles/order-type) of this induced wellordering is an [ordinal](https://bliptext.com/articles/ordinal-number), referred to as the **length** of the prewellordering.\nA **norm** on a set X is a map from X into the ordinals.\nEvery norm induces a prewellordering; if is a norm, the associated prewellordering is given by\nConversely, every prewellordering is induced by a unique **regular norm** (a norm is regular if, for any x \\in X and any there is y \\in X such that ).\n\n# Prewellordering property\nIf is a [pointclass](https://bliptext.com/articles/pointclass) of subsets of some collection \\mathcal{F} of [Polish spaces](https://bliptext.com/articles/polish-space), \\mathcal{F} closed under [Cartesian product](https://bliptext.com/articles/cartesian-product), and if \\leq is a **prewellordering** of some subset P of some element X of then \\leq is said to be a -**prewellordering** of P if the relations <^* and \\leq^* are elements of where for x, y \\in X,\nis said to have the **prewellordering property** if every set in admits a -prewellordering.\nThe prewellordering property is related to the stronger [scale property](https://bliptext.com/articles/scale-property); in practice, many pointclasses having the prewellordering property also have the [scale property](https://bliptext.com/articles/scale-property), which allows drawing stronger conclusions.\n\n## Examples\nand both have the prewellordering property; this is provable in [ZFC](https://bliptext.com/articles/zermelo-fraenkel-set-theory) alone.\nAssuming sufficient [large cardinals](https://bliptext.com/articles/large-cardinal), for every and\nhave the prewellordering property.\n\n## Consequences\n\n### Reduction\nIf is an [adequate pointclass](https://bliptext.com/articles/adequate-pointclass) with the prewellordering property, then it also has the **reduction property**: For any space and any sets A and B both in the union A \\cup B may be partitioned into sets A^*, B^*, both in such that and\n\n### Separation\nIf is an [adequate pointclass](https://bliptext.com/articles/adequate-pointclass) whose [dual pointclass](https://bliptext.com/articles/dual-pointclass) has the prewellordering property, then has the **separation property**: For any space and any sets A and B disjoint sets both in there is a set such that both C and its [complement](https://bliptext.com/articles/complement-set-theory) are in with and\nFor example, has the prewellordering property, so has the separation property.\nThis means that if A and B are disjoint [analytic](https://bliptext.com/articles/analytic-set) subsets of some Polish space X, then there is a [Borel](https://bliptext.com/articles/borel-set) subset C of X such that C includes A and is disjoint from B.","revisionCount":0},"hasMore":false,"nextCursor":null}

History