記述集合論覚え書き

author: fujidig, created at: 2019/12/13

記述集合論を勉強していて気付いたことをメモしていこうと思います．

記号など

recursiveな全射$f: \scrC \to \scrN$はない

recursiveな写像は連続だった．よってそのような$f$は$\scrC$から$\scrN$への連続全射になる． $\scrC$はコンパクトなのでその$f$による像もコンパクト．$\scrN$はコンパクトでないので矛盾である．

recursiveな全射$f: \R \to \scrN$はない

これは$\R$が連結で，$\scrN$が不連結であるから．

$\scrN$のコンパクト集合はmeager

$\scrN$のコンパクト集合はmeagerである． 実際，$K$を$\scrN$のコンパクト集合とする． 各第$i$成分への射影$\operatorname{pr}_i(K)$は$\omega$のコンパクト集合なので$\operatorname{pr}_i(K) \subset n_i$となる自然数$n_i$がある． よって，$K \subset \prod_{i\in\omega} n_i$となる． $\prod_{i\in\omega} n_i$がmeagerを言えばよいが，これは明らかに閉集合でかつ内部が空である．よって言えた．

$\R$はコンパクト集合の可算和で書けるという性質があるが，$\scrN$にはこの性質はないことが分かる．コンパクト集合の可算和は上の事実よりmeagerであり，全体空間$\scrN$はmeagerでないことはBaireの範疇定理からの帰結だからである．

$\scrN$のコンパクト集合はLebesgue測度$0$とは限らない

$\omega$の確率測度$\mu_\omega(\{n\}) = 2^{-(n+1)}$としてその無限直積として$\scrN$に確率空間の構造が入っている．$\scrN$のルベーグ測度を$\mu$としよう．

$\scrN$のコンパクト集合$K = \prod_{i\in\omega} n_i$の測度を考えよう． 計算により \[ \mu(K) = \prod_{i\in\omega} (1 - (1/2)^{n_i}) \tag{1} \] が分かる． 解析学の事実 (Rudin "Real and Complex Analysis (3rd edition)"のTheorem 15.5など)より， \[ \sum_{i\in\omega} (1/2)^{n_i} \] が収束すれば(1)は$0$でない値に収束する． よって，たとえば$n_i = i + 1$とすれば$\mu(K)$は正の値をとる． 実際Wolframalphaによるとこの値は$0.288788\dots$となるそうだ． (product (1-(1/2)^(n+1)) from n=0 to infty - Wolfram|Alpha)

recursive presentationのとれるPolish spaceは同型を除いて可算個

Polish space $(X,d)$について$D = \{ r_i : i \in \omega \} \subset X$が$(X,d)$のrecursive presentationであるとは$D$が$X$の可算稠密集合であり， \begin{align*} P(i, j, m, n) &\iff d(r_i, r_j) \le \frac{m}{n+1} \\ Q(i, j, m, n) &\iff d(r_i, r_j) \lt \frac{m}{n+1} \end{align*} がともにrecursiveであること．

recursive presentationのとれるPolish spaceは同型 (等長同型)を除いて可算個しかない． なぜなら，$P, Q$からもとのPolish spaceと同型なものが復元できるからである． 実際，$P, Q$から各$r_i$と$r_j$の間の正確な距離が分かる． 集合$\omega$の元$i$と$j$に$r_i$と$r_j$の距離を入れ，完備化するともとの$(X, d)$と同型な空間が得られるからだ． recursiveな述語は可算個しかないので，結局recursive presentationのとれるPolish spaceは同型 (等長同型)を除いて可算個しかない．

recursive presentationのとれないperfect Polish spaceの具体例

補集合がrecursively enumerableでない$\omega$の部分集合$K$をとり，$\R$の閉部分集合として \[ A = \bigcup_{x∈(\omega\setminus K)\cup\{0\}} [x-0.1, x+0.1] \] を考える． $A$にrecursive presentationがとれたらそこから$K$をcomputeできてしまう．

$\{(\alpha, \beta) \in \scrN^2 : \alpha = \beta \}$は$\Pi^0_1$だが$\Sigma^0_1$ではない

$\Sigma^0_1$なら，特に開集合であることを思い出そう． \[ A = \{(\alpha, \beta) \in \scrN^2 : \alpha = \beta \} \] について$(0, 0) \in A$ (ここで$0$は常に$0$の列)だが，$(0, 0)$の近傍を持ってくるとそれが常に$A$に含まれているかというともちろんそんなわけはない． よって$A$は開集合ではなく，特に$\Sigma^0_1$ではない．

$f: \scrN \to \scrN$について$f$がrecursiveであっても$\operatorname{Graph}(f)$はrecursiveとは限らない

$f(\alpha) = \alpha$はrecursiveだが，そのグラフは一つ上の項目の$A$なのでrecursiveでない．

そもそも，どんな関数$f: \scrN \to \scrN$についても$G = \operatorname{Graph}(f)$はrecursiveとはなりえない． $G$がrecursiveで$(\alpha, \beta) \in G$だったら，$G$が開集合なので$\beta$の十分近くの点$\beta'$についても$(\alpha, \beta') \in G$とならなければならないが，これは$G$が関数のグラフであることに反するからである．