Δ-システム補題
$\Delta$-システム補題とは、組合せ集合論における基本的な命題のひとつである。大量に有限集合が与えられたとき、後述する $\Delta$-システムが存在することを保証する(構成する)命題であり、ZFC 上での組合せ論的な議論を行う際にしばしば用いられる。
$\Delta$-システム補題
定義 1 ($\Delta$-システム)
集合族 $\mathcal{D}$ が $\Delta$-システムであるとは、ある集合 $r$ が存在して、任意の $\mathcal{D}$ の要素 $x$, $y$ について $x\cap y=r$ が成り立つことをいう。またこのような $r$ を $\mathcal{D}$ の根とよぶ。
命題 2 ($\Delta$-システム補題)
非可算個の有限集合族 $\mathcal{A}$ に対して、ある $\mathcal{D}\subset \mathcal{A}$ であって $\Delta$-システムであるようなものが存在する。
一般化
$\Delta$-システム補題については、次のような一般化が存在する。
定理 3 (一般 $\Delta$-システム補題)
$\kappa$ を無限基数、$\theta$ を $\forall \lambda \lt \theta (|\lambda^{\lt\kappa}|\lt\theta)$ が成り立つ正則基数とする。このとき、集合族 $\mathcal{A}$ が次の条件
- $|\mathcal{A}| \gt \theta$
- $x \in \mathcal{A}$ について $|x| \lt \kappa$
を充たすとき、$\mathcal{D}\subset \mathcal{A}$ であって $|\mathcal{D}|=\theta$ を充たす $\Delta$-システムが存在する。
証明
$\kappa \geq \theta$ ならば、$2^{\lt\kappa}=\mathrm{sup}_{\mu\lt\kappa}(2^\mu)\geq \theta$ より仮定に反するため、$\kappa \lt \theta$ が成り立つ。
$\mathcal{A}=\theta$ と仮定してよい。また、このとき $\bigcup \mathcal{A}$ は濃度 $\theta$ 以下であるため、$x \in \mathcal{A}$ について $x\subset \theta$ を仮定してよい。このとき、$x$ の順序型を $\mathrm{o}_x$ とおくと、$\theta$ の正則性より、ある濃度 $\kappa$ 以下の順序数 $\alpha$ について、$\mathcal{A}_\alpha=\{x \in \mathcal{A}|\mathrm{o}_x=\alpha\}$ は濃度 $\theta$ を持つ。
このとき、$x \in \mathcal{A}_\alpha$ と $\gamma \in \alpha$ について、$x$ の $\gamma$ 番目に大きい要素を $x_\gamma$ とおくことにする。このとき、$\gamma \in \alpha$ について $s_\gamma$ を $\mathrm{sup}_{x \in \mathcal{A}_\alpha}(x_\gamma)$ と定めると、$\gamma \leq \gamma'$ ならば $s_\gamma \leq s_{\gamma'}$ が成り立つ。このとき、$\theta$ は正則基数であるため、$s_\gamma = \theta$ なる $\gamma$ が存在するか、もしくはある $\theta'\lt \theta$ が存在し任意の $\gamma \in \alpha$ について $s_\gamma \leq \theta'$ が成り立つ。
ある $\theta'\lt \theta$ が存在し任意の $\gamma \in \alpha$ について $s_\gamma \leq \theta'$ が成り立つ場合、$\bigcup \mathcal{A}_\alpha$ の濃度 $\lambda$ は $\theta$ 未満である。したがって、$\mathcal{A}$ は高々 $\lambda^{\lt\kappa}$ 未満でなくてはならないため、これは仮定に反する。
従って、$s_\gamma = \theta$ なる $\gamma$ が存在する。このとき、$\gamma \lt \kappa$ である。また、$s=\mathrm{sup}_{\delta\lt\gamma}(s_\delta)$ は $\theta$ 以下である。このとき、$s_\gamma=\theta$ であるため、$x_\gamma$ が $s$ 以上であるような $x$ 全体のなす $\mathcal{A}_\alpha$ の部分集合を $\mathcal{B}$ とおくと $\mathcal{B}$ は濃度 $\theta$ を持つ。
このとき、$x \in \mathcal{B}$ について、$s\cup x$ は高々 $|s|^\gamma$ 個の値を取るため、ある $r \subset s$ が存在し、$s\cup x =r$ をみたすような $x \in \mathcal{B}$ よりなる $\mathcal{B}$ の部分集合 $\mathcal{C}$ であって、$\mathrm{sup}_{x \in \mathcal{C}}(x_\gamma)=\theta$ なるものが存在する。このとき $\mathcal{C}$ の濃度は $\theta$ である。
最後に、超限帰納的に $\mathcal{C}$ の $\theta$ 個の異なる元を選ぶ。$y_0$ として $\mathcal{C}$ の任意の元を選ぶ。$\beta\lt \theta$ について、$\delta \lt \beta$ までの $\delta$ について $y_\delta$ が選ばれているとする。このとき、$\bigcup_{\delta\lt\beta}y_\delta$ は $\theta$ の正則性より有界である。従って $\mathrm{sup}_{x \in \mathcal{C}}(x_\gamma)=\theta$ であったため、ある $x \in \mathcal{C}$ であって $\bigcup_{\delta\lt\beta}y_\delta \subset x_\gamma$ なるものが存在する。これを $y_\beta$ として選ぶ。
こうして $\beta\lt \gamma$ によって $y_\beta$ として選ばれた $\mathcal{C}$ の元全体を $\mathcal{D}$ とおくと、$\mathcal{D}$ は $r$ を根とする $\Delta$-システムである。□一般 $\Delta$-システム補題の $\kappa = \aleph_0$, $\theta = \aleph_1$ の場合により $\Delta$-システム補題は示される。
information
関連項目
参考文献
- Kunen K., "Set Theory, An Introduction to Independence Proofs", 1980
