まず, \(\omega\) の部分集合 \(a_\alpha,b_\alpha\) ( \(a < \omega_1\) ) が, 以下の条件
- \(\forall \alpha < \omega_1 [ a_\alpha \subset^* b_\alpha ]\)
- \(\forall \alpha,\beta < \omega_1 [ \alpha < \beta \to a_\alpha \subset^* a_\beta \land b_\beta \subset^* b_\alpha ]\)
- \(\forall \alpha < \omega_1 \forall n < \omega [ |\{\gamma < \alpha \,:\, a_\alpha \setminus b_\gamma \subset n\}| < \omega ]\)
を全て満たすならば, これらは \(\neg\exists c \in \mathcal{P}(\omega) \forall \alpha < \omega_1 [ a_\alpha \subset^* c \subset^* b_\alpha ]\) も満たし, 従って主張が成り立つことを示す. ある \(c \in \mathcal{P}(\omega)\) について \(\forall \alpha < \omega_1 [ a_\alpha \subset^* c \subset^* b_\alpha ]\) が成り立つと仮定して矛盾を導く. このとき各 \(a_\alpha \setminus c\) は有限集合であり, また \(\omega\) の有限部分集合の個数は高々 \(|{}^{< \omega} \omega| = \omega\) であるから, ある不可算な \(I_1 \subset \omega_1\) が存在して \(\forall \alpha,\beta \in I_1 [ a_\alpha \setminus c = a_\beta \setminus c ]\) が成り立つ. この共通な \(a_\alpha \setminus c\) を \(d\) と置く. 同様に, 各 \(c \setminus b_\alpha\) は有限集合なので, ある不可算な \(I_2 \subset I_1\) が存在して \(\forall \alpha,\beta \in I_2 [ c \setminus b_\alpha = c \setminus b_\beta ]\) が成り立つ. この共通な \(c \setminus b_\alpha\) を \(d'\) と置く. ここで, \(|\alpha \cap I_2| = \omega\) となる \(\alpha \in I_2\) が存在するのでそれを一つ取ると, 任意の \(\beta \in \alpha \cap I_2\) について \(a_\alpha \setminus b_\beta \subset (a_\alpha \setminus c) \cup (c \setminus b_\beta) = d \cup d'\) となる. \(d \cup d'\) は有限集合なので ある \(n < \omega\) に含まれるが, このとき無限個ある \(\beta \in \alpha \cap I_2\) について \(a_\alpha \setminus b_\beta \subset n\) となり, 上の条件3に矛盾する. よってこの段落の主張が成り立つ.
あとは \(\alpha\) に関する超限帰納法を用いて冒頭の三つの条件を満たす部分集合たちを構成すればよい. \(\alpha = n < \omega\) の範囲については, 二進数表示で下 \(1\) 桁が \(0\) でありかつ下 \((n+1)\) 桁のどれかが \(1\) である自然数全体の集合を \(a_n\), 二進数表示で下 \(1\) 桁が \(0\) であるかまたは下 \((n+1)\) 桁の全てが \(1\) である自然数全体の集合を \(b_n\) と置くと, これらは冒頭の三つの条件を満たす. 実際, \(a_n \subset b_n\) であり, また下 \((n+1)\) 桁が全て \(0\) である無限個の自然数が \(b_n \setminus a_n\) に属するので, 条件1が成り立つ. \(n < m\) ならば \(a_n \subset a_m\) かつ \(b_m \subset b_n\) であり, 下 \((n+2)\) 桁が \(100 \cdots 0\) である無限個の自然数が \(a_m \setminus a_n\) に属し, また下 \((n+2)\) 桁が \(011 \cdots 1\) である無限個の自然数が \(b_n \setminus b_m\) に属するので, 条件2が成り立つ. 条件3はこの範囲の \(\alpha\) については自明である.
以下, \(\omega \leq \alpha < \omega_1\) とし, \(\alpha\) より小さい範囲の添字については対応する部分集合が既に構成されているものとする. 各 \(\beta,\gamma < \alpha\) について, 条件1と条件2より \(a_\beta \subset^* b_\gamma\) であることを注意しておく ( \(\beta < \gamma\) であれば \(a_\beta \subset^* a_\gamma \subset^* b_\gamma\), また \(\beta > \gamma\) であれば \(a_\beta \subset^* b_\beta \subset^* b_\gamma\) である).
ここで以下の補題を示しておく:
補題 \(\alpha\) の有限個の元 \(\lambda_1,\dots,\lambda_\ell\), \(\mu_1,\dots,\mu_m\), \(\nu_1,\dots,\nu_n\) が, \(\ell \geq 1\), \(n+m \geq 1\) かつ \(\forall i,j [ \lambda_i < \mu_j ]\) を満たすならば, \((\bigcap_{i=1}^{\ell} b_{\lambda_i}) \setminus (\bigcup_{j=1}^{m} b_{\mu_j} \cup \bigcup_{k=1}^{n} a_{\nu_k})\) は無限集合である.
証明. 必要であれば元を並べ替えることで, \(\lambda_\ell = \min_{1 \leq i \leq \ell} \lambda_i\) と仮定してよい. 上の条件1と条件2より, \(\{b_{\mu_1},\dots,b_{\mu_m},a_{\nu_1},\dots,a_{\nu_n}\}\) は \(\subset^*\) に関して全順序なので, これらを \(\subset^*\) に関して降順に \(c_1,\dots,c_{m+n}\) と置く (つまり \(c_{i+1} \subset^* c_i\) ). このとき仮定より \(c_1 \subset^* b_{\lambda_\ell}\) である. すると, 件の集合は \(b_{\lambda_\ell} \setminus c_1\) から全ての集合 \(b_{\lambda_\ell} \setminus b_{\lambda_i}\) ( \(1 \leq i \leq \ell - 1\) ) と \(c_j \setminus c_1\) ( \(2 \leq j \leq n+m\) ) を除いた集合であるが, \(b_{\lambda_\ell} \setminus c_1\) は無限集合で残りの集合たちは有限集合なので, 件の集合は無限集合となる. \(\square\)
以下, \(\alpha\) が後続型順序数の場合と極限順序数の場合に分けて考える.
まず, \(\alpha = \alpha_0 + 1\) が後続型順序数であるとする. このとき, 条件1より \(|b_{\alpha_0} \setminus a_{\alpha_0}| = \omega\) である. \(b_{\alpha_0} \setminus a_{\alpha_0}\) の元を \(\gamma_i\) ( \(i < \omega\) ) と番号付けしておき, \(a_\alpha = a_{\alpha_0} \cup \{\gamma_{3 \cdot i} \,:\, i < \omega\}\), \(b_\alpha = a_\alpha \cup \{\gamma_{3 \cdot i + 1} \,:\, i < \omega\}\) と定める. すると, \(a_{\alpha_0} \subset a_\alpha \subset b_\alpha\), \(|a_\alpha \setminus a_{\alpha_0}| = |b_\alpha \setminus a_\alpha| = \omega\) より, \(a_{\alpha_0} \subset^* a_\alpha \subset^* b_\alpha\) となる. また, \(b_\alpha \setminus b_{\alpha_0} = a_{\alpha_0} \setminus b_{\alpha_0}\) なので \(|b_\alpha \setminus b_{\alpha_0}| < \omega\) であり, \(\{\gamma_{3 \cdot i + 2} \,:\, i < \omega\} \subset b_{\alpha_0} \setminus b_\alpha\) なので \(|b_{\alpha_0} \setminus b_\alpha| = \omega\) である. よって \(b_\alpha \subset^* b_{\alpha_0}\) となり, 条件1と条件2が成り立つ. 条件3については, 各 \(n < \omega\) について \(\{\gamma < \alpha \,:\, a_\alpha \setminus b_\gamma \subset n\} \subset \{\gamma < \alpha_0 \,:\, a_{\alpha_0} \setminus b_\gamma \subset n\} \cup \{\alpha_0\}\) ( \(a_{\alpha_0} \subset a_\alpha\) に注意) であり, \(\alpha_0\) までの範囲での条件3より \(\{\gamma < \alpha_0 \,:\, a_{\alpha_0} \setminus b_\gamma \subset n\}\) は有限集合なので, \(\{\gamma < \alpha \,:\, a_\alpha \setminus b_\gamma \subset n\}\) も有限集合である. よって条件3も成り立つ.
次に \(\alpha\) が極限順序数であるとする. このとき \(\mathrm{cf}(\alpha) = \omega\) であり, 第I章補題10.31より狭義増加な共終写像 \(f \,:\, \omega \to \alpha\) が存在する. また, 全単射 \(g \,:\, \omega \to \alpha\) を一つ選んでおく. 各 \(n < \omega\) について, \(c_n = a_{g(n)} \cap \bigcap_{i \leq n} b_{g(i)}\) と置く. このとき \(a_{g(n)} \setminus c_n = \bigcup_{i \leq n} (a_{g(n)} \setminus b_{g(i)})\) であり, \(a_{g(n)} \subset^* b_{g(i)}\) より各 \(a_{g(n)} \setminus b_{g(i)}\) は有限集合なので, \(a_{g(n)} \setminus c_n\) も有限集合である. また, \(i \leq n\) のとき \(c_n \subset b_{g(i)}\) であり, \(n < i < \omega\) のとき \(a_{g(n)} \subset^* b_{g(i)}\) なので \(|a_{g(n)} \setminus b_{g(i)}| < \omega\), 従って \(|c_n \setminus b_{g(i)}| < \omega\) である. 次に, 上の補題より各 \(n < \omega\) に対する集合 \((\bigcap_{i \leq n} b_{g(i)}) \setminus (\bigcup_{i \leq n} a_{g(n)})\) は全て無限集合なので, それらから相異なる元 \(x_{n,0},x_{n,1},x_{n,2}\) を (帰納的に) 選ぶことができる. さらに, 各 \(1 \leq n < \omega\) について, \(a_{f(n)} \setminus b_{f(i)}\) ( \(i \leq n\) ) は全て有限集合である. また, \(i \geq g^{-1}(f(n))\) ならば \(x_{i,0},x_{i,1},x_{i,2} \not\in a_{f(n)}\) であるから, \(a_{f(n)}\) に属する \(x_{i,j}\) たちは有限個しかない. これより, ある \(m_n < \omega\) が存在して \(a_{f(n)} \setminus m_n \subset \bigcap_{i \leq n} b_{f(i)}\) かつ \(\forall i,j [ x_{i,j} \not\in a_{f(n)} \setminus m_n ]\) となる. このとき \(m_n > m_{n-1}\) であるように \(m_n\) を選んでおく. ここで条件3より \(\{\gamma \,:\, f(n-1) < \gamma \leq f(n) \land a_{f(n)} \setminus b_\gamma \subset m_n\}\) は有限集合なので, その元を \(\gamma_{n,1},\dots,\gamma_{n,\ell_n}\) ( \(\ell_n < \omega\) ) と置く. 各 \(1 \leq j \leq \ell_n\) について, 上の補題より \((\bigcap_{i < n} b_{f(i)}) \setminus b_{\gamma_{n,j}}\) は無限集合である. そして \(i' \geq g^{-1}(\gamma_{n,j})\) であれば \(x_{i',j'} \in b_{\gamma_{n,j}}\) なので, \((\bigcap_{i < n} b_{f(i)}) \setminus b_{\gamma_{n,j}}\) に属する \(x_{i',j'}\) たちは有限個しかない. よって, \(((\bigcap_{i < n} b_{f(i)}) \setminus b_{\gamma_{n,j}}) \setminus (m_n \cup \{x_{i',j'} \,:\, i' < \omega \land 0 \leq j' \leq 2\})\) の元 \(y_{n,j}\) を取ることができる. 以上の状況で, \[ b'_\alpha = \bigcup_{n < \omega} (c_n \cup \{x_{n,0},x_{n,1},x_{n,2}\}) \cup \bigcup_{1 \leq n < \omega} ((a_{f(n)} \setminus m_n) \cup \{y_{n,j} \,:\, 1 \leq j \leq \ell_n\}) \] と置き, \[ b_\alpha = b'_\alpha \setminus \{x_{n,2} \,:\, n < \omega\}, a_\alpha = b_\alpha \setminus \{x_{n,1} \,:\, n < \omega\} \] と定める. このとき \(a_\alpha \subset b_\alpha\) かつ \(|b_\alpha \setminus a_\alpha| = \omega\) なので条件1が成り立つ. 以下, これらが条件2と条件3を満たすことを示す.
条件2について, \(n < \omega\) とする. \(c_n\) の選び方より \(a_{g(n)} \setminus c_n\) は有限集合なので, \(|a_{g(n)} \setminus b'_\alpha| < \omega\) である. また \(x_{i,j}\) たちの選び方より, \(i \geq n\) ならば \(x_{i,j} \not\in a_{g(n)}\) であるから, \(a_{g(n)}\) に属する \(x_{i,j}\) は有限個しかない. これより \(a_{g(n)} \setminus a_\alpha\) も有限集合である. 一方, \(i \geq n\) ならば \(x_{n,0} \in a_\alpha \setminus a_{g(n)}\) なので, \(a_\alpha \setminus a_{g(n)}\) は無限集合である. よって \(a_{g(n)} \subset^* a_\alpha\) が成り立つ. 次に, \(x_{i,j}\) たちの選び方より \(i \geq n\) ならば \(x_{i,2} \in b_{g(n)} \setminus b_\alpha\) なので, \(|b_{g(n)} \setminus b_\alpha| = \omega\) である. 一方, 上の議論より \((\bigcup_{i < \omega} c_i) \setminus b_{g(n)} = \bigcup_{i < n} (c_i \setminus b_{g(n)})\) は有限集合である. \(x_{i,j}\) たちの選び方より \(i \geq n\) ならば \(x_{i,j} \in b_{g(n)}\) であるから, \(b_{g(n)}\) に属さない \(x_{i,j}\) は有限個しかない. また, \(f\) は共終なので \(f(n') > g(n)\) となる \(n' < \omega\) が存在する. このとき, 上の議論より \(i \geq n'\) ならば \(a_{f(i)} \setminus m_i \subset b_{f(n')}\) であり, \(i < n'\) ならば \((a_{f(i)} \setminus m_i) \setminus b_{f(n')} \subset a_{f(i)} \setminus b_{f(n')}\) と \(a_{f(i)} \subset^* b_{f(n')}\) より \((a_{f(i)} \setminus m_i) \setminus b_{f(n')}\) は有限集合である. また \(y_{i,j}\) たちの選び方より, \(i > n'\) ならば \(y_{i,j} \in b_{f(n')}\) である. よって \(d = \bigcup_{1 \leq n < \omega} ((a_{f(n)} \setminus m_n) \cup \{y_{n,j} \,:\, 1 \leq j \leq \ell_n\})\) と置けば \(|d \setminus b_{f(n')}| < \omega\) であり, 一方 \(b_{f(n')} \subset^* b_{g(n)}\) より \(|b_{f(n')} \setminus b_{g(n)}| < \omega\) なので, \(|d \setminus b_{g(n)}| < \omega\) となる. 以上より \(|b_\alpha \setminus b_{g(n)}| < \omega\) となり, \(b_\alpha \subset^* b_{g(n)}\) が成り立つ. \(g \,:\, \omega \to \alpha\) は全射なので, 条件2が成り立つ.
次に条件3について, \(n < \omega\) とする. \(m_i\) たちは狭義単調増加なので, \(n < m_{n'}\) となる \(1 \leq n' < \omega\) が取れる. ここで, \(i < \omega\) かつ \(a_\alpha \setminus b_{g(i)} \subset m_{n'}\) と仮定する. さらに \(f(n'-1) < g(i)\) と仮定し, \(f(k-1) < g(i) \leq f(k)\) となる \(k < \omega\) を取ると, \(k \geq n'\) である. このとき \(a_\alpha \setminus b_{g(i)} \subset m_{n'} \subset m_k\) 即ち \(a_\alpha \setminus m_k \subset b_{g(i)}\) であり, また上で示したように \(\forall i,j [ x_{i,j} \not\in a_{f(k)} \setminus m_k]\) であるから, \(a_{f(k)} \setminus m_k \subset a_\alpha \setminus m_k \subset b_{g(i)}\) 即ち \(a_{f(k)} \setminus b_{g(i)} \subset m_k\) となる. よって, \(g(i)\) はある \(\gamma_{k,j}\) と一致する. すると \(y_{k,j}\) の選び方より, \(y_{k,j} \in a_\alpha\), \(y_{k,j} \not\in b_{\gamma_{k,j}} = b_{g(i)}\), \(y_{k,j} \not\in m_k\) が成り立つが, これは上で示した性質 \(a_\alpha \setminus b_{g(i)} \subset m_k\) と矛盾する. よって \(g(i) \leq f(n'-1) < f(n')\) となる. 今, \(a_\alpha \setminus b_{g(i)} \subset m_{n'}\) より \(a_\alpha \setminus m_{n'} \subset b_{g(i)}\) であり, 上と同様の議論により \(a_{f(n')} \setminus m_{n'} \subset a_\alpha \setminus m_{n'}\) であるから, \(a_{f(n')} \setminus m_{n'} \subset b_{g(i)}\) 即ち \(a_{f(n')} \setminus b_{g(i)} \subset m_{n'}\) が成り立つ. 従って \(g(i) \in \{\gamma < f(n') \,:\, a_{f(n')} \setminus b_\gamma \subset m_{n'}\}\) であり, \(g \,:\, \omega \to \alpha\) は全単射なので, \(\{\gamma < \alpha \,:\, a_\alpha \setminus b_\gamma \subset n\} \subset \{\gamma < f(n') \,:\, a_{f(n')} \setminus b_\gamma \subset m_{n'}\}\) となる. \(\alpha = f(n')\) の場合の条件3より右辺は有限集合なので, 左辺も有限集合となる. よって条件3も成り立つ. 以上より主張が成り立つ.