## Classification of smooth equivalence relations

The classification of smooth equivalence relations is accomplished by two exercises from Su Gao’s book, Invariant Descriptive Set Theory.

Exercise 5.4.1, Su Gao, p 132.
Show that for any equivalence relation $E$ on a Polish space $X$, $\text{id}( \omega ) \le_B E$ iff there are infinitely many $E$-equivalence classes.

Suppose $\text{id}( \omega ) \le_B E$.  So there exists Borel $f: \omega \to X$ such that $f(x) E f(y)$ iff $x = y$. Since for each $x$, the element $f(x)$ lies in a different $E$ class, there are infinitely many classes.

Suppose there are infinitely many $E$-classes; enumerate a countable subset: $\{ C_n : n \in \omega \}$.  By the Axiom of Choice, for each $n$ pick a $y_n \in C_n$, and define $f: \omega \to X$  by $f(n) = y_n$.  Since $\omega$ has the discrete topology, $f$ is cts, and so $latex \text{id}(\omega) \le_B E$.

Exercise 5.4.2, Su Gao, p 132
Show that if an equivalence relation $E$ is smooth then either $E \sim_B \text{id}(2^\omega)$, or $E \sim_B \text{id}\omega$, or for some finite $n \in \omega$, $E \sim_B \text{id}(n)$.

By Theorem 5.4.2, if $E$ is smooth, either (1) $E \sim_B \text{id}( 2^\omega )$ or (2) $E \le_B \text{id }( \omega )$.

So assume (2).  Then either $E$ has infinitely many classes or it does not.
If it does, by Exercise 5.4.1, $\text{id}(\omega) \le_B E$, hence $\text{id}(\omega) \sim_B E$.

If it does not, suppose $E$ has $n$ classes. List the classes: $C_1, \ldots, C_n$. Since $E$ is smooth, each $C_i$ is Borel.

Then define $f: X \to n$ by $f(x) = i$ iff $x \in C_i$.  Then $f$ is Borel. Also $\text{id}(n) \le E$, since $n$ has discrete topology and we can pick
a point in each equivalence class to map $i$ to $E_i$.

## The Axiom of Choice and indeterminacy

It’s been a while since my last post — I apologize to any devoted fans who have been disappointed.

I’m taking a class on Descriptive Set Theory now.  Here is the proof of an interesting theorem from class: Assuming the Axiom of Choice, there exists an undetermined game.

Here, a game consists of two players, a pruned tree, and a payoff set $A$.  The players move alternately by picking an immediate extension of the last move.  Player I wins if, after infinitely many moves, they have created an element of $A$.  Player II wins otherwise.

## Cantor-Bendixson decompositions. Kechris, Exercise (6.6)

Kechris, p. 32, Exercise (6.6) (A)
Let $X$ be a Polish space. Decompose $X$ uniquely into $P \dot{\cup} C$, where $P$ is perfect, $C$ is countable open. This decomposition is possible by Cantor-Bendixson Theorem.

Exercise  (6.6): $P$ is the largest perfect subset of $X$.

Proof.
Suppose $Q \subset X$ is perfect (so closed and perfect in its relative topology).  From the proof of Theorem (6.4), and in the notation defined there, we have $Q^* = Q$, hence $Q \subset P$.  Now suppose $Q \supset P$, and further that $Q \cap C \neq \emptyset$; notice that $Q \cap C$, being a $G_\delta$ set, is also a Polish space.

Claim: $Q \cap C$ is a perfect space.
Let $x \in Q \cap C$.  Let $V$ be an open nbhd of $x \in Q \cap C$.  That is, there exists $V'$ open in $X$ such that $V = V' \cap Q \cap C$.  Then $V$ is also open in $Q$, since $C \cap V'$ is open in $X$.  Since $Q$ is perfect, there exists $y \neq x \in V$. Therefore, $Q \cap C$ is perfect and nonempty, hence uncountable by Theorem (6.2).

But this contradicts that $C$ is countable.  Hence, $Q \cap C = \emptyset$, and thus $Q = P$. $\blacksquare$

## Hausdorff metric compatible with Vietoris topology / Kechris p25 B Ex 4.21

Kechris, p. 25
(B) Exercise (4.21).
Show that the Hausdorff metric is compatible with the Vietoris topology.

Proof.
Let $(X, d)$ be a metric space with $d \le 1$. Let $\tau_H$ denote the topology from the Hausdorff metric on $K(X)$, with basis $\mathcal{B}_H = \{ B^H(K, \epsilon) : K \in K(X), \epsilon > 0 \}$, $\tau_V$ denote the Vietoris topology on $K(X)$, with basis
$\mathcal{B}_V = \{ V_{U_i}^{0,n} = \{ K \in K(X) : K \subseteq U_0 \ \& \ K \cap U_1 \neq \emptyset \ \& \ \ldots \ \& \ K \cap U_n \neq \emptyset \} : U_i \text{ open in } X, 0 \le i \le n \}$.

If $K \subset X$, $B^X(K, \epsilon) = \{ x \in X : d(x, K) < \epsilon \}$.

(i) $\tau_H \subseteq \tau_V$.
Proof.
Let $B = B(K, \epsilon) \in \mathcal{B}_H$.  Suppose $K = \emptyset$.  Then, since $\{ \emptyset \} \in \mathcal{B}_V$ and $\{ \emptyset \} \subset B$, we’re done.

So, suppose now that $K \neq \emptyset$. Cover $K$ with finitely many balls $U_i$, $1 \le i \le n$, of radius $\epsilon$, such that, for all $i$, $U_i \cap K \neq \emptyset$.  Let $U_0 = \bigcup_{i = 1}^n U_i$.

I will show that $V = V_{U_i}^{0,n} \in \mathcal{B}_V$ satisfies $V \subseteq B$.

Let $L \in V$.  That is $L \subseteq U_0$, and for all $i$, $L \cap U_i \neq \emptyset$.  To see that $d_H(L,K) < \epsilon$, I check that $L \subseteq B^X(K, \epsilon)$ and $K \subseteq B^X(L, \epsilon)$.  Let $l \in L$.  Then $l \in U_0$, so $l \in U_i$ for some $i \in \{ 1, \ldots, n \}$, so $d(l, K) < \epsilon$.  Similarly, if $k \in K$, $d(k, L) < \epsilon$.

So $V \subseteq B$. $\blacksquare$

(ii) $\tau_V \subseteq \tau_H$.
Proof.
Let $V = V_{U_i}^{0,n} \in \mathcal{B}_V$, $K \in V$.  If $K = \emptyset$, then $B^H( \emptyset, 1/2) \subset V$. So suppose that $K \neq \emptyset$.  I have that $K \subseteq U_0$, and $K \cap U_i \neq \emptyset$, $i \in \{1, \ldots, n\}$.

Claim 1: $\inf \{ d(x, K) : x \in X \backslash U_0 \} = \epsilon_0 > 0$.
Proof.
Suppose $\epsilon_0 = 0$.  Then, I can pick $(x_n) \subset X \backslash U_0$ such that $\lim_n d(x_n, K) = 0$.  Let $(k_n) \subseteq K$ such that $d(x_n, k_n) \to 0$.  Then, $(k_n)$ has a convergent subsequence, $k_{n_i} \to k$.  But then $x_{n_i} \to k$, which is a contradiction since $X \backslash U_0$ is closed. $\blacksquare$

Let $i \in \{1, \ldots, n \}$.  Let $x_i \in K \cap U_i$.  Then $\exists \, \epsilon_i$ such that $B^X(x_i, \epsilon_i) \subseteq U_i$. Then let $\epsilon = \min \{ \epsilon_0, \ldots, \epsilon_n \}$.

Claim 2: $B = B^H(K, \epsilon) \subseteq V$.
Proof.
Let $L \in B$.  That is, $d_H(K,L) < \epsilon$.  Then, $L \subseteq B^X(K, \epsilon)$, $K \subseteq B^X(L, \epsilon)$. Then, for each $i \in \{1, \ldots, n \}$, $d(x_i, L) < \epsilon$.  So there exists $l_i \in L$ such that $d(x_i, l_i) < \epsilon$.  Hence $l_i \in U_i$, and $L \cap U_i \neq \emptyset$. $\blacksquare$

Finally, let $l \in L$.  Then $d( l, K) < \epsilon$, so $l \notin X \backslash U_0$ (see Claim 1).  So $L \subseteq U_0$, and $L \in V$. $\blacksquare$

So $\tau_V \subseteq \tau_H$. $\blacksquare$

And hence $\tau_V = \tau_H$. $\blacksquare$

## Topological limits / Kechris p26, Ex 4.23

See here for definitions.

Kechris, p. 26
(B) Exercise (4.23).  Let $(X, d)$ be metric space with $d \le 1$. Show that for nonempty $K, K_n \in K(X)$,
(i) $\delta(K, K_n) \to 0 \Rightarrow K \subseteq \underline{\text{Tlim}}_n K_n$.
Proof.
Suppose $\delta(K, K_n) \to 0$.

Thus, for all $\epsilon > 0$, there exists $N$, such that $n \ge N$ implies $\delta(K, K_n) < \epsilon$.
That is, $\max_{x \in K} d(x, K_n) < \epsilon$.

Let $x \in K$.  Now, choose $M_1 < M_2 < \ldots < M_m < \ldots$ such that $n \ge M_i$ implies $d(x, K_n) < 1/ i$.
Now, choose a sequence $(x_n)$ in $X$, such that $x_n \in K_n$, in the following way:  For $n \in \mathbb{N}$,
$M_i \le n < M_{i + 1}$, for some $i \in \mathbb{N}$.  Pick any $x_n \in K_n$ such that $d(x, x_n) < 1 /i$.

Then $x_n \to x$, so $x \in \underline{\text{Tlim}}_n K_n$. $\blacksquare$

(ii) $\delta(K_n, K) \to 0 \Rightarrow K \supseteq \overline{\text{Tlim}}_n K_n$.
Proof.
Assume $\delta(K_n,K) \to 0$.  Let $x \in \overline{\text{Tlim}}_n K_n \cap K^c$.  Since $x \notin K$
and since $K$ is compact, hence closed, $d(x,K) = \epsilon > 0$.
$x \in \overline{\text{Tlim}}_n K_n \Rightarrow \exists(x_n)[ x_n \in K_n \text{, for all n, and for some subsequence } (x_{n_i}), x_{n_i} \to x]$.
$\exists$ some $N$ such that $n_i \ge N \Rightarrow d(x_{n_i}, x) < \epsilon / 2$, and $\delta(K_{n_i}, K) < \epsilon / 2$.
Therefore, $d(x_{n_i}, K) < \epsilon / 2$.  Therefore $\exists (y \in K)[d(x_{n_i}, y) < \epsilon / 2]$.
Therefore $d(x,y) \le d(x, x_{n_i}) + d(x_{n_i}, y) < \epsilon$, which is a contradiction.
Thus, $\overline{\text{Tlim}}_n K_n \subseteq K$. $\blacksquare$

(i) and (ii) show that $d_H(K_n, K) \to 0 \Rightarrow K = \text{Tlim} K_n$.
To show that the converse fails, consider the real numbers $\mathbb{R}$ with the trivial metric.
Let $K_n = \{ 1/n, 1 \}$, which is clearly compact.  Then $\text{Tlim} K_n = \{ x : \text{every open neighborhood of x meets } K_n \text{ for infinitely many n} \} = \{ 1 \}$
And $\delta(K_n, K) = \max_{x \in K_n} d(x, K) = 1 - 1/n = \frac{n - 1}{n} \to 1$.

## Vietoris topology and Hausdorff metric

From Kechris:

Let $X$ be a topological space.  We denote by $K(X)$ the space of all compact subsets of $X$ equipped with the Vietoris topology.

Let $(X,d)$ be a metric space with $d \le 1$.  We define the Hausdorff metric on $K(X)$, $d_H$, as follows:

$d_H(K,L) = 0$, if $K = L = \emptyset$,

$= 1$, if exactly one of $K, L$ is $\emptyset$,

$= \max \{ \delta(K,L), \delta(L,K) \}$, if $K, L \neq \emptyset$,

where $\delta (K, L) = \max_{ x \in K } d(x, L)$.

## Uniform metrics define same topology on C(X,Y)

Kechris, p. 24
(B)
Let $X$ be a compact metrizable space and $Y$ a metrizable space. We denote by $C(X,Y)$ the space of continuous functions from $X$ into $Y$ with the topology induced by the uniform metric: $d_u(f, g) = \sup_{x \in X} d_Y( f(x), g(x) ),$ where $d_Y$ is a compatible metric for $Y$. A simple compactness argument shows that this topology is independent of the choice of $d_Y$.

Proof.
Let $d^1, d^2$ be two compatible metrics for $Y$. I will show that the two corresponding uniform metrics, $d^1_u, d^2_u$ give the same topology.

Suppose that $d^1_u, d^2_u$ did not give the same topology.  That is, without loss of generality, there exists $f$, $\epsilon$, such that for all $\eta$, $B^2(f, \eta) \nsubseteq B^1(f, \epsilon)$. (Here $B^i(h, \nu) = \{ e \in C(X,Y) : d_u^i(h, e) < \nu \}$.)  That is $\forall \eta \exists g ( d^2_u(f,g) < \eta \text{ and } d_u^1(f,g) \ge \epsilon)$; that is, $\sup_{x \in X} d^2( f(x), g(x) ) < \eta \text{ and } \sup_{x \in X} d^1(f(x),g(x)) \ge \epsilon$, which is the same as

$\sup_{x \in X} d^2( f(x), g(x) ) < \eta$ and there exists $x$ such that$d^1(f(x),g(x)) \ge \epsilon$.

Now, let $n \in \mathbb{N}$.  Let $\eta_n = 1/n$.  Then there exists $g_n, x_n$ such that $d^2(f(x_n), g_n(x_n)) < \eta_n$ and $d^1(f(x_n),g_n(x_n)) \ge \epsilon$.  Since $f(X)$ is compact, the sequence $(f(x_n))$ must have a convergent subsequence $(f(x_k))$.  So $f(x_k) \to \gamma \in f(X)$.

Let $\delta > 0$.  Choose $K$ such that $k \ge K$ implies $d^2(f(x_k), \gamma ) < \delta / 2$ and $1 / K < \delta / 2$. Then $k \ge K$ implies $d^2(g_k(x_k), \gamma) \le d^2(g_k(x_k), f(x_k)) + d^2(f(x_k), \gamma) < \delta$. So $g_k(x_k) \to_{d^2} \gamma$.

Therefore, $(f(x_k), g_k(x_k))$ converges to $\gamma$ under $d^2$.  Thus, it must also do so under $d^1$.  But for all $k$, $d^1(f(x_k),g_k(x_k)) \ge \epsilon$.  So this is a contradiction.

Hence, both metrics give the same topology.