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.

Posted in Uncategorized | Leave a comment

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.

For more information about these kinds of games, you may refer to this wikipedia entry:

Posted in Descriptive Set Theory | Leave a comment

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.

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

Posted in Descriptive Set Theory, Kechris | Leave a comment

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.

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

Posted in Analysis, Descriptive Set Theory, Kechris, Topology | Leave a comment

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

Posted in Analysis, Descriptive Set Theory, Kechris | Leave a comment

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

Posted in Analysis, Definition, Descriptive Set Theory, Kechris, Topology | Leave a comment

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

Kechris, p. 24
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.

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

Posted in Analysis, Descriptive Set Theory, Kechris | Leave a comment