射影階層

$\boldsymbol\Pi^1_n$ の主張は $\boldsymbol\Sigma^1_n$ の主張の補集合をとったもの（ド・モルガンの法則と $\forall^{\mathcal N}B=X\setminus\exists^{\mathcal N}(X\times\mathcal N\setminus B)$）であり、$\boldsymbol\Delta^1_n$ の主張はその両方から従う。以下、$\boldsymbol\Sigma^1_n$ について示す。

$\mathcal N^k$ の部分集合のクラス $\mathcal K$ が次の 3 条件を満たすとき、$\mathcal K$ はよいと呼ぶことにする：(a) 連続写像による逆像で閉じる、(b) 可算共通部分で閉じる、(c) 互いに交わらない開かつ閉な集合 $C_0,C_1,\ldots$ で全体を覆うものと $K_j\in\mathcal K$ に対し、張り合わせ $\bigcup_j(C_j\cap K_j)$ が $\mathcal K$ に属する。

閉集合全体はよい（(c) は、補集合 $\bigcup_j(C_j\setminus K_j)$ が開集合であることから）。そこで、$\mathcal K$ がよいとき、$\mathcal K$ の集合の射影全体 $\exists^{\mathcal N}\mathcal K$ が、逆像・射影・可算和・可算共通部分・張り合わせで閉じ、その補集合全体もよいことを示す。$\boldsymbol\Sigma^1_1=\exists^{\mathcal N}(\text{閉集合})$、$\boldsymbol\Sigma^1_{n+1}=\exists^{\mathcal N}\boldsymbol\Pi^1_n$ なので、これで $n$ についての帰納法が進む。以下 $A_j=\exists^{\mathcal N}K_j$（$K_j\in\mathcal K$）などと書く。

逆像。 $f\colon X\to Y$ が連続で $A=\exists^{\mathcal N}K$（$K\subseteq Y\times\mathcal N$）なら、$f^{-1}(A)=\exists^{\mathcal N}\{(x,y)\mid(f(x),y)\in K\}$ で、括弧の中は連続写像 $(x,y)\mapsto(f(x),y)$ による $K$ の逆像である。

射影。 $A\subseteq X\times\mathcal N$ が $A=\exists^{\mathcal N}K$（$K\subseteq X\times\mathcal N\times\mathcal N$）なら、
$$ \exists^{\mathcal N}A=\{x\mid\exists y\,\exists z\ (x,y,z)\in K\}=\exists^{\mathcal N}\{(x,w)\mid(x,\pi^{-1}(w))\in K\} $$
であり、2 つの量化が $\pi$ で 1 つにまとまる。

可算和。 $y^\star(t):=y(t+1)$（先頭を落とす写像）とおくと
$$ \bigcup_jA_j=\exists^{\mathcal N}\bigcup_j\bigl(\{y(0)=j\}\cap\{(x,y)\mid(x,y^\star)\in K_j\}\bigr) $$
である（先頭の値 $y(0)$ でどの $A_j$ に入るかを指定する）。右辺の括弧の中は、開かつ閉な集合 $\{y(0)=j\}$ による、(a) で得られる $\mathcal K$ の集合の張り合わせなので、(c) により $\mathcal K$ に属する。

張り合わせ。 $\bigcup_j(C_j\cap A_j)=\exists^{\mathcal N}\bigcup_j\bigl((C_j\times\mathcal N)\cap K_j\bigr)$ であり、$C_j\times\mathcal N$ は開かつ閉で全体を覆うので、(c) から従う。

可算共通部分。 $A_j=\exists^{\mathcal N}K_j$ とすると、
$$ \bigcap_jA_j=\exists^{\mathcal N}\bigcap_j\{(x,y)\mid(x,(y)_j)\in K_j\} $$
である。$\supseteq$ は明らかで、$\subseteq$ は、$x\in\bigcap_jA_j$ なら各 $j$ で証人 $y_j$ を選び（可算選択）、$(y)_j=y_j$ となる $y$ をとればよい。

補集合のクラスもよい。 $\exists^{\mathcal N}\mathcal K$ の集合の補集合全体を $\mathcal K'$ とする。(a) は逆像が補集合と可換なことから、(b) は $\exists^{\mathcal N}\mathcal K$ の可算和の閉包性の補集合をとって得られる。(c) は、$\bigcup_j(C_j\cap P_j)$ の補集合が $\bigcup_j(C_j\setminus P_j)$、すなわち $\exists^{\mathcal N}\mathcal K$ の集合 $X\setminus P_j$ の張り合わせになることから従う。

閉集合・開集合。 閉集合 $F\subseteq X$ は $F=\exists^{\mathcal N}(F\times\mathcal N)$ なので $\boldsymbol\Sigma^1_1$ である。開集合は可算個の開かつ閉な基本集合の和であり、基本集合は閉集合なので、可算和の閉包性から $\boldsymbol\Sigma^1_1$ である。$\square$

$\boldsymbol\Pi^1_n\subseteq\boldsymbol\Sigma^1_{n+1}$。 $B\in\boldsymbol\Pi^1_n$ なら、$B\times\mathcal N$ は射影 $(x,y)\mapsto x$ による逆像として $\boldsymbol\Pi^1_n$ であり、$B=\exists^{\mathcal N}(B\times\mathcal N)$ は $\boldsymbol\Sigma^1_{n+1}$ である（使わない変数の量化を付け足す）。

$\boldsymbol\Sigma^1_n\subseteq\boldsymbol\Sigma^1_{n+1}$。 $n$ についての帰納法で示す。$n=1$：$A=\exists^{\mathcal N}F$（$F$ 閉）とする。$F$ の補集合は開集合なので $\boldsymbol\Sigma^1_1$（prop-projective-closure）であり、$F\in\boldsymbol\Pi^1_1$。よって $A\in\boldsymbol\Sigma^1_2$。$n\to n+1$：$A=\exists^{\mathcal N}B$、$B\in\boldsymbol\Pi^1_n$ とする。帰納法の仮定 $\boldsymbol\Sigma^1_n\subseteq\boldsymbol\Sigma^1_{n+1}$ の補集合をとると $\boldsymbol\Pi^1_n\subseteq\boldsymbol\Pi^1_{n+1}$ なので、$A\in\exists^{\mathcal N}\boldsymbol\Pi^1_{n+1}=\boldsymbol\Sigma^1_{n+2}$。

以上の 2 つの包含の補集合をとると $\boldsymbol\Sigma^1_n\subseteq\boldsymbol\Pi^1_{n+1}$ と $\boldsymbol\Pi^1_n\subseteq\boldsymbol\Pi^1_{n+1}$ が得られ、あわせて $\boldsymbol\Sigma^1_n\cup\boldsymbol\Pi^1_n\subseteq\boldsymbol\Sigma^1_{n+1}\cap\boldsymbol\Pi^1_{n+1}=\boldsymbol\Delta^1_{n+1}$ となる。$\square$

prop-projective-closureにより、$\boldsymbol\Delta^1_1$ は補集合と可算和で閉じ、開集合を含む（開集合は $\boldsymbol\Sigma^1_1$、その補集合の閉集合も $\boldsymbol\Sigma^1_1$ なので、開集合は $\boldsymbol\Pi^1_1$ でもある）。Borel 集合全体は開集合を含む最小の $\sigma$-代数なので、$\boldsymbol\Delta^1_1$ に含まれる。$\square$

要点：まず、開集合をすべて切り口として並べた開集合 $G\subseteq\mathcal N^2$ を作り、その補集合 $F$ で閉集合を並べる。次に「$\exists y$」と「補集合」を切り口ごとに施して、$U_1:=\{(a,x)\mid\exists y\ (a,\pi(x,y))\in F\}$、$U_{n+1}:=\{(a,x)\mid\exists y\ (a,\pi(x,y))\notin U_n\}$ とおけばよい。

lem-projective-universalの $U_n$ をとり、$D:=\{x\in\mathcal N\mid(x,x)\in U_n\}$ とおく。$D$ は連続写像 $x\mapsto(x,x)$ による $U_n$ の逆像なので $\boldsymbol\Sigma^1_n$ である。

$D$ が $\boldsymbol\Pi^1_n$ だと仮定する。すると $\mathcal N\setminus D$ は $\boldsymbol\Sigma^1_n$ であり、普遍性からある $a$ について $\mathcal N\setminus D=(U_n)_a$ となる。$x=a$ を代入すると
$$ a\notin D\iff(a,a)\in U_n\iff a\in D $$
となって矛盾する。よって $D\in\boldsymbol\Sigma^1_n\setminus\boldsymbol\Pi^1_n$ である。

この $D$ は $\boldsymbol\Delta^1_n$ に属さないので $\boldsymbol\Delta^1_n\subsetneq\boldsymbol\Sigma^1_n$。補集合 $\mathcal N\setminus D$ は $\boldsymbol\Pi^1_n\setminus\boldsymbol\Sigma^1_n$ に属するので $\boldsymbol\Delta^1_n\subsetneq\boldsymbol\Pi^1_n$。最後に、$D$ と $\mathcal N\setminus D$ はどちらも prop-projective-inclusionsにより $\boldsymbol\Delta^1_{n+1}$ に属する。$E:=\{0^\frown x\mid x\in D\}\cup\{1^\frown x\mid x\notin D\}$（先頭に $0$ または $1$ を付けた列）とおく。先頭を落とす写像 $y\mapsto y^\star$ を使うと $E=\bigl(N_{\langle0\rangle}\cap\{y\mid y^\star\in D\}\bigr)\cup\bigl(N_{\langle1\rangle}\cap\{y\mid y^\star\notin D\}\bigr)$ であり、開かつ閉な $N_{\langle i\rangle}$ は Borel なので $\boldsymbol\Delta^1_1\subseteq\boldsymbol\Delta^1_{n+1}$ に属する（cor-projective-borel）。$\boldsymbol\Delta^1_{n+1}$ は逆像・共通部分・和で閉じるので $E\in\boldsymbol\Delta^1_{n+1}$ である。$E$ が $\boldsymbol\Sigma^1_n$ なら、連続写像 $x\mapsto1^\frown x$ による逆像 $\mathcal N\setminus D$ も $\boldsymbol\Sigma^1_n$ になり、$E$ が $\boldsymbol\Pi^1_n$ なら、$x\mapsto0^\frown x$ による逆像 $D$ も $\boldsymbol\Pi^1_n$ になる。どちらも上で否定したので、$E\notin\boldsymbol\Sigma^1_n\cup\boldsymbol\Pi^1_n$ である。$\square$

$n=1$ のthm-projective-properにより、$\boldsymbol\Sigma^1_1$ で $\boldsymbol\Pi^1_1$ でない集合 $D$ がある。$D$ は $\boldsymbol\Delta^1_1$ に属さないので、cor-projective-borelにより Borel 集合ではない。$\square$