Prewellordering

Transitivebinary relations
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$and$S\neq \varnothing:$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Yindicates 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 byYin the "Symmetric" column and✗in the "Antisymmetric" column, respectively. All definitions tacitly require thehomogeneous relation$R$betransitive:for all$a,b,c,$if$aRb$and$bRc$then$aRc.$ A term's definition may require additional properties that are not listed in this table.

Inset theory,aprewellorderingon aset$X$is apreorder$\leq$on$X$(atransitiveandreflexiverelation on$X$) that isstrongly connected(meaning that any two points are comparable) andwell-foundedin the sense that the induced relation$x<y$defined by$x\leq y{\text{ and }}y\nleq x$is awell-founded relation.

Prewellordering on a set

Aprewellorderingon aset$X$is ahomogeneous binary relation$\,\leq \,$on$X$that satisfies the following conditions:

1. Reflexivity:$x\leq x$for all$x\in X.$
2. Transitivity:if$x<y$and$y<z$then$x<z$for all$x,y,z\in X.$
3. Total/Strongly connected:$x\leq y$or$y\leq x$for all$x,y\in X.$
4. 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<y$defined by$x\leq y$and$y\nleq x$being awell-founded relation.

Ahomogeneous binary relation$\,\leq \,$on$X$is a prewellordering if and only if there exists asurjection$\pi:X\to Y$into awell-ordered set$(Y,\lesssim )$such that for all$x,y\in X,$${\textstyle x\leq y}$if and only if$\pi (x)\lesssim \pi (y).$

Examples

Hasse diagramof 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 thefloor function.

Hasse diagramof 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'scardinality) 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 anequivalence relationon$X,$and$\leq$induces awellorderingon thequotient$X/{\sim }.$Theorder-typeof this induced wellordering is anordinal,referred to as thelengthof the prewellordering.

Anormon 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 uniqueregular norm(a norm$\phi:X\to Ord$is regular if, for any$x\in X$and any$\alpha <\phi (x),$there is$y\in X$such that$\phi (y)=\alpha$).

Prewellordering property

If${\boldsymbol {\Gamma }}$is apointclassof subsets of some collection${\mathcal {F}}$ofPolish spaces,${\mathcal {F}}$closed underCartesian 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 }}$-prewellorderingof$P$if the relations$<^{*}$and$\leq ^{*}$are elements of${\boldsymbol {\Gamma }},$where for$x,y\in X,$

1. $x<^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))$
2. $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 theprewellordering propertyif every set in${\boldsymbol {\Gamma }}$admits a${\boldsymbol {\Gamma }}$-prewellordering.

The prewellordering property is related to the strongerscale 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 }}_{2}^{1}$both have the prewellordering property; this is provable inZFCalone. Assuming sufficientlarge cardinals,for every$n\in \omega,$${\boldsymbol {\Pi }}_{2n+1}^{1}$and${\boldsymbol {\Sigma }}_{2n+2}^{1}$ have the prewellordering property.

Consequences

Reduction

If${\boldsymbol {\Gamma }}$is anadequate pointclasswith the prewellordering property, then it also has thereduction 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 anadequate pointclasswhosedual pointclasshas the prewellordering property, then${\boldsymbol {\Gamma }}$has theseparation property:For any space$X\in {\mathcal {F}}$and any sets$A,B\subseteq X,$$A$and$B$disjointsets both in${\boldsymbol {\Gamma }},$there is a set$C\subseteq X$such that both$C$and itscomplement$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 disjointanalyticsubsets of some Polish space$X,$then there is aBorelsubset$C$of$X$such that$C$includes$A$and is disjoint from$B.$

See also

• Descriptive set theory– Subfield of mathematical logic
• Graded poset– partially ordered set equipped with a rank functionPages displaying wikidata descriptions as a fallback– 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– kind of object in descriptive set theoryPages displaying wikidata descriptions as a fallback

References

• Moschovakis, Yiannis N.(1980).Descriptive Set Theory.Amsterdam: North Holland.ISBN978-0-08-096319-8.OCLC499778252.
• Moschovakis, Yiannis N.(2006).Notes on set theory.New York: Springer.ISBN978-0-387-31609-3.OCLC209913560.