In set theory, a prewellordering is a binary relation
≤
that is transitive, total, and wellfounded (more precisely, the relation
x
≤
y
∧
y
≰
x
is wellfounded). In other words, if
≤
is a prewellordering on a set
X
, and if we define
∼
by
x
∼
y
⟺
x
≤
y
∧
y
≤
x
then
∼
is an equivalence relation on
X
, and
≤
induces a wellordering on the quotient
X
/
∼
. The order-type of this induced wellordering is an ordinal, referred to as the length of the prewellordering.
A norm on a set
X
is a map from
X
into the ordinals. Every norm induces a prewellordering; if
ϕ
:
X
→
O
r
d
is a norm, the associated prewellordering is given by
x
≤
y
⟺
ϕ
(
x
)
≤
ϕ
(
y
)
Conversely, every prewellordering is induced by a unique regular norm (a norm
ϕ
:
X
→
O
r
d
is regular if, for any
x
∈
X
and any
α
<
ϕ
(
x
)
, there is
y
∈
X
such that
ϕ
(
y
)
=
α
).
If
Γ
is a pointclass of subsets of some collection
F
of Polish spaces,
F
closed under Cartesian product, and if
≤
is a prewellordering of some subset
P
of some element
X
of
F
, then
≤
is said to be a
Γ
-prewellordering of
P
if the relations
<
∗
and
≤
∗
are elements of
Γ
, where for
x
,
y
∈
X
,
-
x
<
∗
y
⟺
x
∈
P
∧
[
y
∉
P
∨
{
x
≤
y
∧
y
≰
x
}
]
-
x
≤
∗
y
⟺
x
∈
P
∧
[
y
∉
P
∨
x
≤
y
]
Γ
is said to have the prewellordering property if every set in
Γ
admits a
Γ
-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.
Π
1
1
and
Σ
2
1
both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every
n
∈
ω
,
Π
2
n
+
1
1
and
Σ
2
n
+
2
1
have the prewellordering property.
If
Γ
is an adequate pointclass with the prewellordering property, then it also has the reduction property: For any space
X
∈
F
and any sets
A
,
B
⊆
X
,
A
and
B
both in
Γ
, the union
A
∪
B
may be partitioned into sets
A
∗
,
B
∗
, both in
Γ
, such that
A
∗
⊆
A
and
B
∗
⊆
B
.
If
Γ
is an adequate pointclass whose dual pointclass has the prewellordering property, then
Γ
has the separation property: For any space
X
∈
F
and any sets
A
,
B
⊆
X
,
A
and
B
disjoint sets both in
Γ
, there is a set
C
⊆
X
such that both
C
and its complement
X
∖
C
are in
Γ
, with
A
⊆
C
and
B
∩
C
=
∅
.
For example,
Π
1
1
has the prewellordering property, so
Σ
1
1
has the separation property. This means that if
A
and
B
are disjoint analytic subsets of some Polish space
X
, then there is a Borel subset
C
of
X
such that
C
includes
A
and is disjoint from
B
.
