\tutorial{10}{2023-12-19}{Sheet 9} \subsection{Sheet 9} \nr 1 $(X, \tau') \xrightarrow{x \mapsto x} (X, \tau)$ is Borel (by one of the equivalent definitions of being Borel). Thus $\cB(X, \tau) \subseteq \cB(X, \tau')$ (by the other equivalent definition of being Borel). Let $U \subseteq (X, \tau')$ be Borel. $\id\defon{U}$ is injective, hence $U$ is Borel in $(X, \tau)$ by Lusin-Suslin. \paragraph{Related stuff} \begin{fact} Let $X,Y$ be Polish. $f\colon X \to Y$ is Borel iff its graph $\Gamma_f$ is Borel. \end{fact} \begin{proof} Take a countable open base $V_0, V_1, \ldots$ of $Y$. Then $\Gamma_f = \{(x,y) : \forall n < \omega.~f(x) \in V_n \implies y \in V_n\}$ (because the space is Hausdorff). If $f$ is Borel, then clearly the RHS is Borel since \begin{IEEEeqnarray*}{rCl} &&\{(x,y) : \forall n < \omega.~f(x) \in V_n \implies y \in V_n\}\\ &=& \bigcap_{n < \omega} (f^{-1}(V_n)^{c}Y \cup f^{-1}(V_n) \times V_n\}\\ \end{IEEEeqnarray*} On the other hand suppose that $\Gamma_f$ is Borel. Then \[ f^{-1}(B) = \pi_X(X \times B \cap \Gamma_f) \] is analytic.\footnote{Note that the projection of a Borel set is not necessarily Borel. Moreover note that we only used that $\Gamma_f$ is analytic.} On the other hand \[ f^{-1}(B)^c = f^{-1}(B^c) \] is analytic and we know that $\Sigma_1^1 \cap \Pi_1^1 = \cB$ by the \yaref{cor:lusinseparation}. \end{proof} In fact we have shown \begin{fact} The following are equivalent \begin{itemize} \item $f$ is Borel, \item $\Gamma_f$ is Borel, \item $\Gamma_f$ is analytic. \end{itemize} \end{fact} \nr 2 \begin{definition} Let $X$ be a topological space. Let $K(X)$ be the set of all compact subspaces of $X$. The \vocab{Vietoris Topology}, $\tau_V$, on $K(X)$ is the topology with basic open sets \[ [U_0; U_1, \ldots, U_n] = \{K \in K(X) : K \subseteq U_0 \land \forall 1 \le i \le n .~K \cap U_i \neq \emptyset\} \] for $U_i \overset{\text{open}}{\subseteq} X$. \end{definition} \begin{definition} Let $(X,d)$ be a matric space with $d \le 1$. We define a metric $d_H$ on $K(X)$ as follows: $d_H(\emptyset, \emptyset) \coloneqq 0$, $d_H(K, \emptyset) \coloneqq 1$ for $K \neq \emptyset$ and \[ d_H(K_0, K_1) \coloneqq \max \{\max_{x \in K_0} d(x,K_1), \max_{x \in K_1} d(x,K_0)\} \] for $K_0, K_1 \neq \emptyset$. \end{definition} \begin{fact} $d_H$ is indeed a metric. \end{fact} \begin{proof} Let $\delta(K, L) \coloneqq \max_{x \in K} d(x,L)$. It suffices to show $\delta(X,Z) \le \delta(X,Y) + \delta(Y,Z)$, since then \begin{IEEEeqnarray*}{rCl} d_H(X,Z) &\le & \max \{\delta(X,Y) + \delta(Y,Z), \delta(Z,Y) + \delta(Y,X)\}\\ &\le & d_H(X,Y) + d_H(Y,Z). \end{IEEEeqnarray*} Using the fact that $d(\cdot , Z)$ is uniformly continuous, specifically \[ |d(x,Z) - d(y,Z)| \le d(x,y), % TODO REF SHEET 1 \] we get \begin{IEEEeqnarray*}{lrCl} &d(x,Z) &\le & d(x,y) + d(y, Z)\\ & &\le & d(x,y) + \delta(Y,Z)\\ \implies& d(x,Z) - \delta(Y,Z) &\le & d(x,Y)\\ \implies& d(x,Z) &\le & \delta(X,Y) + \delta(Y,Z)\\ \implies & \delta(X,Z) &\le & \delta(X,Y) + \delta(Y,Z). \end{IEEEeqnarray*} \end{proof} \begin{itemize} \item We have \begin{IEEEeqnarray*}{rCl} d_H(K_0, K_1) < \epsilon & \iff & \max \{\max_{x \in K_0}d(x, K_1), \max_{x \in K_1} d(x,K_0)\} < \epsilon\\ &\iff& \max_{x \in K_0} d(x, K_1) < \epsilon \land \max_{x \in K_1} d(x, K_0) < \epsilon\\ &\iff& K_0 \subseteq B_{\epsilon}(K_1) \land K_1 \subseteq B_\epsilon(K_0). \end{IEEEeqnarray*} \item Note that a subbase of $\tau_V$ is given by $[U]$ and $\langle U \rangle \coloneqq [X;U]$ for $U \overset{\text{open}}{\subseteq} X$. Let $K \in [U]$. Then $d(\cdot , U^c)\colon U \to \R_{\ge 0}$ is always non-zero and continuous. So $d(K,U^c)$ attains a minimum $\epsilon > 0$. Then $B_{\epsilon}^H(K) \subseteq U$, so $[U]$ is open in $\tau_V$. Let $K \in \langle U \rangle$. Take some $k \in K \cap U$. Then there is some $\epsilon > 0$ such that $B_\epsilon(k) \subseteq U$. Then $K \in B_{\epsilon}^H(K) \subseteq \langle U \rangle$. \todo{Other direction} % $\tau_H \subseteq \tau_V$ \item Consider a countable dense subset of $X$. Let $\cK$ be the set of finite subsets of that countable dense subset. Then $\cK \subseteq K(X)$ is dense: Take $K \in K(X)$ an let $\epsilon > 0$. $K$ can be covered with finitely many $\epsilon$-balls with centers from the countable dense subsets. Let $K' \in \cK$ be the set of the centers. Then $d_H(K, K') \le \epsilon$. \end{itemize} \nr 3 \begin{itemize} \item By transfinite induction we get that $\alpha$ is an ordinal, since $\prec$ is well-founded and the supremum of a sets of ordinals is an ordinal. Since $\rho_{\prec}\colon X \to \alpha$ is a surjection, it follows that $\alpha \le |X|$, i.e.~$\alpha < |X|^+$. \item By induction on $\rho_{\prec_X}(x)$ we show that $\rho_{\prec_{X}}(x) \le \rho_{\prec_Y}(f(x))$. For $0$ this is trivial. Suppose that $\rho_{\prec_{X}}(x) = \alpha$ and the statement was shown for all $\beta < \alpha$. Then \begin{IEEEeqnarray*}{rCl} \rho_{\prec_Y}(f(x)) &=& \sup \{\rho_{\prec_Y}(y') + 1 | y' \prec f(x)\}\\ &\ge& \sup \{\rho_{\prec_Y}(f(x')) + 1 | f(x') \prec f(x)\}\\ &\ge & \sup \{\rho_{\prec_Y}(f(x')) + 1 | x' \prec x\}\\ &\ge & \sup \{\rho_{\prec_X}(x') + 1 | x' \prec x\}\\ &=& \rho_{\prec_X}(x). \end{IEEEeqnarray*} \item Infinite branches of $T_\prec$ correspond to infinite descending chain of $\prec$, hence $T_{\prec}$ is well-founded iff $\prec$ is well-founded. % Unwarp$^{\text{tm}}$ definitions. Suppose that $\prec$ is well-founded. Note that $\rho_T(s)$ depends only on the last element of $s$, as for $s, s' \in T$ with the same last element, we have $s \concat x \in T \iff s' \concat x \in T$. Let $s = (s_0, \ldots, s_n)$. Let us show that $\rho_T(s) = \rho_{\prec}(s_n)$. We use induction on $\rho_T(s)$. For leaves this is immediate. From the last exercise sheet we know that \[ \rho_T(s) = \sup \{\rho_T(s \concat a) + 1 | s \concat a \in T\}. \] Hence \begin{IEEEeqnarray*}{rCl} \rho_T(s) &=& \sup \{\rho_T(s \concat a) + 1 | s \concat a \in T\}\\ &=& \sup \{\rho_{\prec}(a) + 1 | s \concat a \in T\}\\ &=& \sup \{\rho_{\prec}(a) + 1 | a \prec s_n\}\\ &=& \rho_\prec(s_n). \end{IEEEeqnarray*} \end{itemize} \nr 4 A solution can be found in \cite{coanalyticranks}. % TODO Copy relevant points