Prewellordering

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In set theory, a prewellordering is a binary relation \le that is transitive, total, and wellfounded (more precisely, the relation x\le y\land y\nleq x is wellfounded). In other words, if \leq is a prewellordering on a set X, and if we define \sim by

x\sim y\iff x\leq y \land y\leq x

then \sim is an equivalence relation on X, and \leq induces a wellordering on the quotient 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 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\iff\phi(x)\leq\phi(y)

Conversely, every prewellordering is induced by a unique regular 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[edit]

If \boldsymbol{\Gamma} is a pointclass of subsets of some collection \mathcal{F} of Polish spaces, \mathcal{F} closed under Cartesian 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}-prewellordering of P if the relations <^*\, and \leq^* are elements of \boldsymbol{\Gamma}, where for x,y\in X,

  1. x<^*y\iff x\in P\land[y\notin P\lor\{x\leq y\land y\not\leq x\}]
  2. x\leq^* y\iff x\in P\land[y\notin P\lor x\leq y]

\boldsymbol{\Gamma} is said to have the prewellordering property if every set in \boldsymbol{\Gamma} admits a \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[edit]

\boldsymbol{\Pi}^1_1\, and \boldsymbol{\Sigma}^1_2 both have the prewellordering property; this is provable in ZFC alone. Assuming sufficient large cardinals, for every n\in\omega, \boldsymbol{\Pi}^1_{2n+1} and \boldsymbol{\Sigma}^1_{2n+2} have the prewellordering property.

Consequences[edit]

Reduction[edit]

If \boldsymbol{\Gamma} is an adequate pointclass with the prewellordering property, then it also has the reduction 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[edit]

If \boldsymbol{\Gamma} is an adequate pointclass whose dual pointclass has the prewellordering property, then \boldsymbol{\Gamma} has the separation property: For any space X\in\mathcal{F} and any sets A,B\subseteq X, A and B disjoint sets both in \boldsymbol{\Gamma}, there is a set C\subseteq X such that both C and its complement X\setminus C are in \boldsymbol{\Gamma}, with A\subseteq C and B\cap C=\emptyset.

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

See also[edit]

References[edit]

  • Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland. ISBN 0-444-70199-0.