• Source: Prewellordering

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
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
and



y
<
z


{\displaystyle y
then



x
<
z


{\displaystyle x
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
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 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

Kata Kunci Pencarian:

• Prewellordering
• Norm
• Well-order
• Total order
• Inductive set
• List of set theory topics
• List of order theory topics
• Lattice (order)
• Weak ordering
• Well-founded relation