Co-Analytic sets

We will see that, in many ways, $\PP{1}$ sets form the frontier between classical descriptive set theory and metamathematics. This chapter can be seen as the start of our transition to metamathematics. We will detail the distinguished role well-founded relations play in the analysis of $\PP{1}$ sets.

Normal forms¶

Analytic sets are projections of closed sets. Closed sets are in $\Baire\times \Baire$ are infinite paths through trees on $\Nat \times \Nat$ , i.e. two-dimensional trees.

As in the one-dimensional case, we use $[T]$ to denote the set of all infinite paths through $T$ . It follows that $A \subseteq \Baire$ is analytic if and only if there exists a two-dimensional tree $T$ on $\Nat \times \Nat$ such that

\begin{align*} \alpha \in A & \iff \exists \beta \: (\alpha,\beta) \in [T]\\ & \iff \exists \beta \, \forall n \: (\alpha\Rest{n},\beta\Rest{n}) \in T. \end{align*}

(1)

Another way to write this is to put, for given $T$ and $\alpha \in \Baire$ ,

T(\alpha) = \{ \tau \colon (\alpha\Rest{|\tau|}, \tau) \in T \}.

(2)

Then we have, with $T$ witnessing that $A$ is analytic,

\alpha \in A \iff T(\alpha) \text{ has an infinite path } \iff T(\alpha) \text{ is not well-founded}.

(3)

We obtain the following normal form for co-analytic sets.

If $A$ is (lightface) $\Pi^1_1$ , then there exists a computable such $T$ , and the mapping $\alpha \mapsto T(\alpha)$ is computable, as a mapping between reals and trees (which can be coded by reals). This relativizes, i.e. for a $\Pi^1_1(\gamma)$ set, the mapping $\alpha \mapsto T(\alpha)$ is computable in ${}\gamma$ . Since computable mappings are continuous, we obtain that the in the above proposition, the mapping $\alpha \mapsto T(\alpha)$ is continuous.

$\mathbf{\Pi}^1_1$ -complete sets¶

How does one show that a specific set is not Borel? A related question is: Given a definition of a set in second order arithmetic, how can we tell that there is not an easier definition (in the sense that it uses less quantifier changes, no function quantifiers etc.)? The notion of completeness for classes in Polish spaces provides a general method to answer such questions.

The important fact about Wadge reducibility is that it preserves classes closed under continuous preimages.

Proof

If $A \leq_{\W} B$ via $f$ , then $A = f^{-1}(B)$ .

${}\Gamma$ -complete sets can be seen as the most complicated members of ${}\Gamma$ . In particular, for the $\bSigma/\bPi$ classes complete sets cannot be members of the dual class. For instance, a $\PP{1}$ -complete set cannot be $\PS{1}$ , since this would mean it is Borel, and hence every $\PP{1}$ set would be Borel, which we have seen is not true.

If $A \subseteq \Baire \times \Baire$ is $\Baire$ -universal for some class ${}\Gamma$ in the Borel or projective hierarchy, then the set

\{ \alpha \oplus \beta \colon (\alpha,\beta) \in A \}

(6)

is ${}\Gamma$ -complete, where $\oplus$ here denotes the pairing function for reals

\alpha\oplus\beta(n) = \begin{cases} \alpha(k) & n = 2k, \\ \beta(k) & n = 2k+1. \end{cases}

(7)

Since $\oplus$ is continuous, and $B \in \Gamma$ if and only if $B = A_{\gamma}$ for some $\gamma\in \Baire$ , we have in that case that $B \leq_{\W} A$ via the mapping

f(\beta) = \gamma\oplus\beta.

(8)

It follows that complete sets exist for all levels of the Borel and projective hierarchy. However, the universal sets they are based on are rather abstract objects. Complete sets are most useful when we can show that a specific property implies completeness. We will encounter next an important example for the class of co-analytic sets.

Well-founded relations and well-orderings¶

Given a real in $\beta \in \Baire$ , we can associate with $\beta$ a binary relation $E_\beta$ on $\Nat$ :

E_\beta(m,n) :\iff \beta(\Tup{m,n}) = 0.

(9)

A binary relation $E$ on a set $X$ is well-founded if every non-empty $Y \subseteq X$ has an $E$ -minimal element $y_0$ , that is, there is no $z \in Y$ with $E(z,y)$ .

Let

\WF = \{\beta \in \Baire \colon \text{$E_\beta$ is well-founded} \}.

(10)

Using $\DC$ , having a minimal element is equivalent to the non-existence of an infinite descending sequence. So we can rewrite:

\beta \in \WF \iff \forall \gamma \in \Baire \: \exists n \; [ \neg \gamma(n+1) E_\beta \gamma(n) ],

(11)

and hence $\WF$ is $\Pi^1_1$ .

A closely related set is

\WOrd = \{\beta \in \Baire \colon \text{$E_\beta$ is a well-ordering} \}.

(12)

Then

\beta \in \WOrd \iff \beta \in \WF \text{ and $E_\beta$ is a linear ordering}.

(13)

Coding a linear order is easily seen to be $\Pi^0_1$ , hence $\WOrd$ is $\Pi^1_1$ , too.

Proof

We have seen in the chapter on Trees that a tree has an infinite path if and only if the inverse prefix ordering is ill-founded. Trees can be coded as reals, and hence Proposition 1 yields immediately that $\WF$ is $\PP{1}$ -complete.

For $\WOrd$ we use the Kleene-Brouwer ordering and refer to Proposition 2.

The theorem lets us gain further insights in the structure of co-analytic sets. If $\alpha \in \Baire$ codes a well-ordering on $\Nat$ , let

\Norm{\alpha} = \text{ order type of well-ordering coded by $\alpha$}.

It is clear that $\Norm{\alpha} < \omega_1$ . For a fixed ordinal $\xi < \omega_1$ , we let

\WOrd_\xi = \{ \alpha \in \WOrd \colon \Norm{\alpha} \leq \xi \}.

Proof

Let $\alpha \in \Baire$ . We say $m \in \Nat$ is in the domain of $E_\alpha$ , $m \in \Op{dom}(E_\alpha)$ , if

\exists n \: [ m E_\alpha n \; \vee \; n E_\alpha m].

It is clear from the definition of $E_\alpha$ that $\Op{dom}(E_\alpha)$ is Borel. For $\xi < \omega_1$ , let

B_\xi = \{ (\alpha,n) \colon E_\alpha \Rest{\{m \colon m E_\alpha n\}} \text{ is a well-ordering of order type $\leq \xi$} \}

We show by transfinite induction that every $B_\xi$ is Borel. Suppose $B_\zeta$ is Borel for all $\zeta < \xi$ . Then, since $\xi$ is countable, $\bigcup_{\zeta < \xi} B_\zeta$ is Borel, too. But

(\alpha,n) \in B_\xi \iff \forall m \: [m E_\alpha n \: \Rightarrow \: (\alpha,m) \in \bigcup_{\zeta < \xi} B_\zeta],

and from this it follows that $B_\xi$ is Borel. Finally, note that

\alpha \in \WOrd_\xi \iff \forall n \; [n \in \Op{dom}(E_\alpha) \: \Rightarrow \: (\alpha,n) \in B_\xi],

which implies that $\WOrd_\xi$ is Borel.

Proof

Since $\WOrd$ is $\PP{1}$ -complete, every co-analytic set $A$ is the preimage of $\WOrd$ for some continuous function $f$ . We have

\WOrd = \bigcup_{\xi < \omega_1} \WOrd_\xi,

and hence

A = \bigcup_{\xi < \omega_1} f^{-1}(\WOrd_\xi).

Since continuous preimages of Borel sets are Borel, the result follows.

If we work instead with the set

\begin{align*} C_\xi = & \{ \alpha \colon \alpha \in \WOrd_\xi \text{ or } \\ & \qquad \exists n\in \Op{dom}(E_\alpha) [E_\alpha \Rest{ \{m : m E_\alpha n\} } \text{ is a well-ordering of order type $\xi$}] \}, \end{align*}

(14)

then we get that $\WOrd = \bigcap_{\xi < \omega_1} C_\xi$ , and hence

The previous results allow us to solve the cardinality problem of co-analytic sets at least partially.

We conclude the chapter with another application of Lemma 1 – a useful tool for analyzing $\bSigma^1_1$ sets:

Proof

If such a ${}\nu$ did not exist, then

\alpha \in \WOrd \iff \exists \nu \: [\alpha \in A \; \wedge \; \WOrd_\nu].

(16)

The right-hand side is $\bSigma^1_1$ , and hence $\WOrd$ would be $\bSigma^1_1$ , contradiction.

An analogous statement holds for $\WF$ , with respect to the rank function $\rho$ of a well-founded relation.

Projective sets

The Projective Hierarchy

Axiomatic set theory

The Axioms of Set Theory

Normal forms¶

Π11\mathbf{\Pi}^1_1Π11​-complete sets¶

Well-founded relations and well-orderings¶

$\mathbf{\Pi}^1_1$ -complete sets¶