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)}
… excerpt ends here. Continue reading the full article.
