Prewellordering
In-game article clicks load inline without leaving the challenge.
| Transitive binary relations vte | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| SymmetricAntisymmetricConnectedWell-foundedHas joinsHas meetsReflexiveIrreflexiveAsymmetricTotal, SemiconnexAnti- reflexiveEquivalence relationY✗✗✗✗✗Y✗✗Preorder (Quasiorder)✗✗✗✗✗✗Y✗✗Partial order✗Y✗✗✗✗Y✗✗Total preorder✗✗Y✗✗✗Y✗✗Total order✗YY✗✗✗Y✗✗Prewellordering✗✗YY✗✗Y✗✗Well-quasi-ordering✗✗✗Y✗✗Y✗✗Well-ordering✗YYY✗✗Y✗✗Lattice✗Y✗✗YYY✗✗Join-semilattice✗Y✗✗Y✗Y✗✗Meet-semilattice✗Y✗✗✗YY✗✗Strict partial order✗Y✗✗✗✗✗YYStrict weak order✗Y✗✗✗✗✗YYStrict total order✗YY✗✗✗✗YYSymmetricAntisymmetricConnectedWell-foundedHas joinsHas meetsReflexiveIrreflexiveAsymmetricDefinitions, for all a , b {\displaystyle a,b} and S ≠ ∅ : {\displaystyle S\neq \varnothing :}a R b ⇒ b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}a R b and b R a ⇒ a = b {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}a ≠ b ⇒ a R b or b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}min S exists {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}a ∨ b exists {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}a ∧ b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}a R a {\displaystyle aRa}not a R a {\displaystyle {\text{not }}aRa}a R b ⇒ not b R a {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}} | |||||||||
| Symmetric | Antisymmetric | Connected | Well-founded | Has joins | Has meets | Reflexive | Irreflexive | Asymmetric | |
| Total, Semiconnex | Anti- reflexive | ||||||||
| Equivalence relation | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Preorder (Quasiorder) | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Partial order | ✗ | Y | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Total preorder | ✗ | ✗ | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Total order | ✗ | Y | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Prewellordering | ✗ | ✗ | Y | Y | ✗ | ✗ | Y | ✗ | ✗ |
| Well-quasi-ordering | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Y | ✗ | ✗ |
| Well-ordering | ✗ | Y | Y | Y | ✗ | ✗ | Y | ✗ | ✗ |
| Lattice | ✗ | Y | ✗ | ✗ | Y | Y | Y | ✗ | ✗ |
| Join-semilattice | ✗ | Y | ✗ | ✗ | Y | ✗ | Y | ✗ | ✗ |
| Meet-semilattice | ✗ | Y | ✗ | ✗ | ✗ | Y | Y | ✗ | ✗ |
| Strict partial order | ✗ | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y |
| Strict weak order | ✗ | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y |
| Strict total order | ✗ | Y | Y | ✗ | ✗ | ✗ | ✗ | Y | Y |
| Symmetric | Antisymmetric | Connected | Well-founded | Has joins | Has meets | Reflexive | Irreflexive | Asymmetric | |
| Definitions, for all a , b {\displaystyle a,b} and S ≠ ∅ : {\displaystyle S\neq \varnothing :} | a R b ⇒ b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} | a R b and b R a ⇒ a = b {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}} | a ≠ b ⇒ a R b or b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}} | min S exists {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}} | a ∨ b exists {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} | a ∧ b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} | a R a {\displaystyle aRa} | not a R a {\displaystyle {\text{not }}aRa} | a R b ⇒ not b R a {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}} |
| Y indicates that the column's property is always true for the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation R {\displaystyle R} be transitive: for all a , b , c , {\displaystyle a,b,c,} if a R b {\displaystyle aRb} and b R c {\displaystyle bRc} then a R c . {\displaystyle aRc.} A term's definition may require additional properties that are not listed in this table. |
In set theory, a prewellordering on a set X {\displaystyle X} is a preorder ≤ {\displaystyle \leq } on X {\displaystyle X} (a transitive and reflexive relation on X {\displaystyle X}) that is strongly connected (meaning that any two points are comparable) and well-founded in the sense that the induced relation x < y {\displaystyle x<y} defined by x ≤ y and y ≰ x {\displaystyle x\leq y{\text{ and }}y\nleq x} is a well-founded relation.
Prewellordering on a set
A prewellordering on a set X {\displaystyle X} is a homogeneous binary relation ≤ {\displaystyle \,\leq \,} on X {\displaystyle X} that satisfies the following conditions:
- Reflexivity: x ≤ x {\displaystyle x\leq x} for all x ∈ X . {\displaystyle x\in X.}
- Transitivity: if x < y {\displaystyle x<y} and y < z {\displaystyle y<z} then x < z {\displaystyle x<z} for all x , y , z ∈ X . {\displaystyle x,y,z\in X.}
- Total/Strongly connected: x ≤ y {\displaystyle x\leq y} or y ≤ x {\displaystyle y\leq x} for all x , y ∈ X . {\displaystyle x,y\in X.}
- for every non-empty subset S ⊆ X , {\displaystyle S\subseteq X,} there exists some m ∈ S {\displaystyle m\in S} such that m ≤ s {\displaystyle m\leq s} for all s ∈ S . {\displaystyle s\in S.} This condition is equivalent to the induced strict preorder x < y {\displaystyle x<y} defined by x ≤ y {\displaystyle x\leq y} and y ≰ x {\displaystyle y\nleq x} being a well-founded relation.
A homogeneous binary relation ≤ {\displaystyle \,\leq \,} on X {\displaystyle X} is a prewellordering if and only if there exists a surjection π : X → Y {\displaystyle \pi :X\to Y} into a well-ordered set ( Y , ≲ ) {\displaystyle (Y,\lesssim )} such that for all x , y ∈ X , {\displaystyle x,y\in X,} x ≤ y {\textstyle x\leq y} if and only if π ( x ) ≲ π ( y ) . {\displaystyle \pi (x)\lesssim \pi (y).}
Examples
Given a set A , {\displaystyle A,} the binary relation on the set X := Finite ( A ) {\displaystyle X:=\operatorname {Finite} (A)} of all finite subsets of A {\displaystyle A} defined by S ≤ T {\displaystyle S\leq T} if and only if | S | ≤ | T | {\displaystyle |S|\leq |T|} (where | ⋅ | {\displaystyle |\cdot |} denotes the set's cardinality) is a prewellordering.
Properties
If ≤ {\displaystyle \leq } is a prewellordering on X , {\displaystyle X,} then the relation ∼ {\displaystyle \sim } defined by x ∼ y if and only if x ≤ y ∧ y ≤ x {\displaystyle x\sim y{\text{ if and only if }}x\leq y\land y\leq x} is an equivalence relation on X , {\displaystyle X,} and ≤ {\displaystyle \leq } induces a wellordering on the quotient X / ∼ . {\displaystyle 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 {\displaystyle X} is a map from X {\displaystyle X} into the ordinals. Every norm induces a prewellordering; if ϕ : X → O r d {\displaystyle \phi :X\to Ord} is a norm, the associated prewellordering is given by x ≤ y if and only if ϕ ( x ) ≤ ϕ ( y ) {\displaystyle 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 ϕ : X → O r d {\displaystyle \phi :X\to Ord} is regular if, for any x ∈ X {\displaystyle x\in X} and any α < ϕ ( x ) , {\displaystyle \alpha <\phi (x),} there is y ∈ X {\displaystyle y\in X} such that ϕ ( y ) = α {\displaystyle \phi (y)=\alpha }).
Prewellordering property
If Γ {\displaystyle {\boldsymbol {\Gamma }}} is a pointclass of subsets of some collection F {\displaystyle {\mathcal {F}}} of Polish spaces, F {\displaystyle {\mathcal {F}}} closed under Cartesian product, and if ≤ {\displaystyle \leq } is a prewellordering of some subset P {\displaystyle P} of some element X {\displaystyle X} of F , {\displaystyle {\mathcal {F}},} then ≤ {\displaystyle \leq } is said to be a Γ {\displaystyle {\boldsymbol {\Gamma }}}-prewellordering of P {\displaystyle P} if the relations < ∗ {\displaystyle <^{*}} and ≤ ∗ {\displaystyle \leq ^{*}} are elements of Γ , {\displaystyle {\boldsymbol {\Gamma }},} where for x , y ∈ X , {\displaystyle x,y\in X,}
- x < ∗ y if and only if x ∈ P ∧ ( y ∉ P ∨ ( x ≤ y ∧ y ≰ x ) ) {\displaystyle x<^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))}
- x ≤ ∗ y if and only if x ∈ P ∧ ( y ∉ P ∨ x ≤ y ) {\displaystyle x\leq ^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor x\leq y)}
Γ {\displaystyle {\boldsymbol {\Gamma }}} is said to have the prewellordering property if every set in Γ {\displaystyle {\boldsymbol {\Gamma }}} admits a Γ {\displaystyle {\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
Π 1 1 {\displaystyle {\boldsymbol {\Pi }}_{1}^{1}} and Σ 2 1 {\displaystyle {\boldsymbol {\Sigma }}_{2}^{1}} both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every n ∈ ω , {\displaystyle n\in \omega ,} Π 2 n + 1 1 {\displaystyle {\boldsymbol {\Pi }}_{2n+1}^{1}} and Σ 2 n + 2 1 {\displaystyle {\boldsymbol {\Sigma }}_{2n+2}^{1}} have the prewellordering property.
Consequences
Reduction
If Γ {\displaystyle {\boldsymbol {\Gamma }}} is an adequate pointclass with the prewellordering property, then it also has the reduction property: For any space X ∈ F {\displaystyle X\in {\mathcal {F}}} and any sets A , B ⊆ X , {\displaystyle A,B\subseteq X,} A {\displaystyle A} and B {\displaystyle B} both in Γ , {\displaystyle {\boldsymbol {\Gamma }},} the union A ∪ B {\displaystyle A\cup B} may be partitioned into sets A ∗ , B ∗ , {\displaystyle A^{*},B^{*},} both in Γ , {\displaystyle {\boldsymbol {\Gamma }},} such that A ∗ ⊆ A {\displaystyle A^{*}\subseteq A} and B ∗ ⊆ B . {\displaystyle B^{*}\subseteq B.}
Separation
If Γ {\displaystyle {\boldsymbol {\Gamma }}} is an adequate pointclass whose dual pointclass has the prewellordering property, then Γ {\displaystyle {\boldsymbol {\Gamma }}} has the separation property: For any space X ∈ F {\displaystyle X\in {\mathcal {F}}} and any sets A , B ⊆ X , {\displaystyle A,B\subseteq X,} A {\displaystyle A} and B {\displaystyle B} disjoint sets both in Γ , {\displaystyle {\boldsymbol {\Gamma }},} there is a set C ⊆ X {\displaystyle C\subseteq X} such that both C {\displaystyle C} and its complement X ∖ C {\displaystyle X\setminus C} are in Γ , {\displaystyle {\boldsymbol {\Gamma }},} with A ⊆ C {\displaystyle A\subseteq C} and B ∩ C = ∅ . {\displaystyle B\cap C=\varnothing .}
For example, Π 1 1 {\displaystyle {\boldsymbol {\Pi }}_{1}^{1}} has the prewellordering property, so Σ 1 1 {\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}} has the separation property. This means that if A {\displaystyle A} and B {\displaystyle B} are disjoint analytic subsets of some Polish space X , {\displaystyle X,} then there is a Borel subset C {\displaystyle C} of X {\displaystyle X} such that C {\displaystyle C} includes A {\displaystyle A} and is disjoint from B . {\displaystyle B.}
See also
- Descriptive set theory – Subfield of mathematical logic
- Graded poset – Partially ordered set equipped with a rank function – a graded poset is analogous to a prewellordering with a norm, replacing a map to the ordinals with a map to the natural numbers
- Scale property
- Moschovakis, Yiannis N. (1980). . Amsterdam: North Holland. ISBN 978-0-08-096319-8. OCLC .
- Moschovakis, Yiannis N. (2006). Notes on set theory. New York: Springer. ISBN 978-0-387-31609-3. OCLC .