Analytic Sets - Descriptive Set Theory

We will later see that the analytic sets correspond to the sets definable by means of $\Sigma^1_1$ formulas, that is formulas in the language of second order arithmetic that have one existential function quantifier.

Therefore, we will denote the analytic subsets of $X$ also by

\PS{1}(X).

(1)

Here are some simple properties of analytic sets.

Proof

(i): This follows directly from Corollary 1 of the previous section.

(ii): The composition of continuous mappings is continuous.

(iii): Let $A_n$ be analytic and $f_n:\Baire \to X$ such that $f_n(\Baire) = A_n$ . Define $f: \Baire \to X$ by

f(m,\alpha) = f_n(\alpha).

(2)

Then $f$ is continuous and $f(\Baire) = \bigcup_n A_n$ .

We can use our previous results about Borel sets to give various equivalent characterizations of analytic sets.

Proof

(i) $\Leftrightarrow$ (ii): Follows from the Lusin-Souslin Theorem and Proposition 1 (ii).

(ii) $\Leftrightarrow$ (iii): Follows from the corollary to the Lusin-Souslin Theorem and Proposition 1 (ii).

(i) $\Rightarrow$ (iv): Let $f:\Baire \to X$ be continuous, $f(\Baire) = A$ . Then

x \in A \iff \exists \alpha \; (\alpha,x) \in \Op{Graph}(f),

(3)

hence $A$ is the projection of the closed set $\Op{Graph}(f)$ along $\Baire$ .

(iv) $\Rightarrow$ (iii): Clear, since projections are continuous.

(iv) $\Rightarrow$ (v): $\Baire$ is homeomorphic to a $\BP{2}$ subset of $\Cant$ . (Exercise!)

(v) $\Rightarrow$ (vi), (vi) $\Rightarrow$ (iii): Obvious.

The Lusin Separation Theorem¶

In a course on computability theory one learns that there are effectively inseparable disjoint computably enumerable sets. i.e. disjoint c.e. sets $W,Z \subseteq \Nat$ for which no recursive set $A$ exists with $W \subseteq A$ and $A \cap Z = \emptyset$ .

In contrast to this, disjoint analytic sets can always be separated by a Borel set - they are Borel separable.

Proof

Let $f:\Baire \to A$ and $g:\Baire \to B$ be continuous surjections.

We argue by contradiction. The key idea is: if $A$ and $B$ are Borel inseparable, then, for some $i,j \in \Nat$ , $A_{\Tup{i}} = f(\Cyl{\Tup{i}})$ and $B_{\Tup{j}} = g(\Cyl{\Tup{j}})$ are Borel inseparable.

This follows from the following observation:

If the sets $R_{m,n}$ separate the sets $P_m, \, Q_n$ (for each $m,n$ ), then $R = \bigcup_m \bigcap_n R_{m,n}$ separates the sets $P = \bigcup_m P_m, \, Q = \bigcup_n Q_n.$

By using this repeatedly, we can construct sequences $\alpha, \beta \in \Baire$ such that for all $n$ , $A_{\alpha\Rest{n}}$ and $B_{\beta\Rest{n}}$ are Borel inseparable, where

A_{\sigma} = f(\Cyl{\sigma}) \quad \text{ and } \quad B_{\sigma} = g(\Cyl{\sigma}).

(5)

Then we have $f(\alpha) \in A$ and $g(\beta) \in B$ , and since $A$ and $B$ are disjoint, $f(\alpha) \neq g(\beta)$ . Let $U,V$ be disjoint open sets such that $f(\alpha) \in U$ , $g(\beta) \in V$ . Since $f$ and $g$ are continuous, there exists $N$ such that $f(\Cyl{\alpha\Rest{N}}) \subseteq U$ , $g(\Cyl{\beta\Rest{N}}) \subseteq V$ , hence $U$ separates $A_{\alpha\Rest{N}}$ and $B_{\beta\Rest{N}}$ , contradiction.

The Separation Theorem yields a nice characterization of the Borel sets.

Proof

In Theorem 1, chose $A = A$ and $B = \Co{A}$ .

It follows from Souslin’s Theorem and the Lusin separation theorem that the analytic sets are not closed under complements.

Sets whose complement is analytic are called co-analytic. Analogous to the levels of the Borel hierarchy, the co-analytic subsets of a Polish space $X$ are denoted by

\PP{1}(X).

(6)

If we define, again analogy to the Borel hierarchy,

\bDelta^1_1(X) = \PS{1}(X) \cap \PP{1}(X),

(7)

then Souslin’s Theorem states that

\Op{Borel}(X) = \bDelta^1_1(X).

(8)

The Souslin operation¶

Souslin schemes give an alternative presentation of analytic sets which will be useful later.

The analytic sets are precisely the sets that can be obtained by Souslin operations on closed sets. If a $\Gamma$ is a family of subsets of a set $X$ , we let

\mathcal{A}\Gamma = \{\mathcal{A}P \colon \text{ $P = (P_\sigma)$ is a Souslin scheme with $P_\sigma \in \Gamma$ for all $\sigma$} \}.

(10)

Proof

Suppose $f: \Baire \to X$ is continuous with $f(\Baire) = A$ . Then

x \in A \iff \exists \alpha \in \Baire \; \forall n \in \Nat \; x \in \Cl{f(\Cyl{\alpha\Rest{n}})}.

Hence if we let $P_\sigma = \Cl{f(\Cyl{\sigma})}$ , then

A = \mathcal{A} \,P,

for the Souslin scheme $P = (P_\sigma)$ .

To see that any set $A$ in $\mathcal{A}\,\BP{1}(X)$ is analytic, consider ( $**$ ). If the $P_\sigma$ are closed, the condition

(\alpha,x) \in F \iff \forall n \in \Nat \; x \in P_{\alpha\Rest{n}}

(12)

defines a closed subset of $\Baire \times X$ such that $A$ is the projection of $F$ along $\Baire$ .

Note that the Souslin scheme $(P_\sigma)$ used in the previous proof has the additional property that

\sigma \Sleq \tau \quad \Rightarrow \quad P_\sigma \supseteq P_\tau.

(13)

Such Souslin schemes are called regular. By replacing any Souslin scheme $P_\sigma$ with

Q_\sigma = \bigcap_{\tau \Sleq \sigma} P_\tau,

(14)

we obtain a regular Souslin scheme $Q = (Q_\sigma)$ with $\mathcal{A} \, Q = \mathcal{A}\, P$ . Moreover, if the $P_\sigma$ are from a class $\Gamma$ , and $\Gamma$ is closed under finite intersections, then the $Q_\sigma$ are also from $\Gamma$ . In particular, any analytic set can be obtained from a regular Souslin scheme of closed sets via the Souslin operation.

The Borel hierarchy

Continuous Images of Borel sets

Projective sets

Regularity Properties of Analytic sets