Aronszajn木(Aronszajn tree)とは、高さが $\omega_1$ で各レベルが高々可算だが、非可算の鎖をもたない集合論の木である。より一般に、正則基数 $\kappa$ について高さ $\kappa$、各レベルの濃度が $\kappa$ 未満で、濃度 $\kappa$ の鎖をもたない木を $\kappa$-Aronszajn 木という。$\omega$ には König の補題により存在しないが、$\omega_1$ には ZFC で存在し、非可算の高さでは König の補題の類似が成り立たない例になっている。可算個の反鎖で覆える特殊な Aronszajn 木も ZFC で存在する。
各段が有限個の点からなる無限の木には、どこまでも伸びる枝がある。これが König の補題である。では、段の番号を $\omega$ から最初の非可算順序数 $\omega_1$ に上げて、「各段が高々可算で高さが $\omega_1$ の木には、$\omega_1$ の長さの枝がある」と言えるだろうか。
答えは否であり、しかも ZFC だけで否定できる。高さが $\omega_1$ で、どの段も高々可算で、非可算の鎖を 1 本ももたない木が存在する。これを $\omega_1$-Aronszajn 木(Aronszajn tree)という。König の補題は有限と可算の間では成り立つが、可算と非可算の間では成り立たない。極限の段を通るときに、それまで選んできた鎖の上に点が残っている保証がないからである。
この記事では、$\omega_1$-Aronszajn 木の存在を単射の木と有理数列の木の 2 通りで証明し、有理数への狭義単調写像をもつ「特殊」な木を調べ、Martin の公理のもとではすべての Aronszajn 木が特殊になることを示す。最後に、枝がない木の反対の極にある Kurepa 木を扱う。反鎖の条件を足した Suslin木 は別の記事で扱う。
ここでいう木は、集合論の順序構造であって、グラフとしての木とは別の概念である。
木とは、半順序集合 $(T,\le)$ で、各 $x\in T$ について $\{y\in T\mid y< x\}$ が $<$ で整列されているものをいう。
典型例は、$I$ の元の長さ $\delta$ 未満の列の全体 ${}^{<\delta}I:=\bigcup_{\alpha< \delta}{}^\alpha I$ を、延長の関係で順序づけたものである。$s\le t$ は $t$ が $s$ の延長であることを意味し、$\operatorname{ht}(s)=\operatorname{dom}(s)$ である。
$\kappa$ を正則基数とする。
単に Aronszajn 木といえば $\omega_1$-Aronszajn 木を指す。
$\kappa$ を正則基数、$T$ を $\kappa$-木とする。$T$ が濃度 $\kappa$ の鎖をもつことと、枝をもつことは同値である。
枝は $\kappa$ 個のレベルのそれぞれから 1 点ずつ含むので、濃度 $\kappa$ の鎖である。逆に $C$ を濃度 $\kappa$ の鎖とする。ある $\beta< \kappa$ で $C\subset\bigcup_{\alpha< \beta}\operatorname{Lev}_\alpha(T)$ となるなら、$\kappa$ の正則性とレベルの濃度の仮定から $|C|< \kappa$ となって矛盾する。よって $C$ の元の高さは $\kappa$ の中で非有界である。$C$ の下への閉包 $\{y\mid\exists x\in C\ y\le x\}$ は、$\{y\mid y\le x\}$ が鎖で $C$ が鎖であることから鎖であり、すべてのレベルと交わる。$\square$
$\omega$ は木性質をもつ。これが Königの補題 である(Kun80 Ch. II Lemma 5.7)。
$\alpha< \omega_1$ について、$s,t\colon\alpha\to\omega$ が有限個の点でしか違わないことを $s\sim t$ と書く。$\sim$ は同値関係である。単射 $\alpha\to\omega$ を全部集めた木は非可算の鎖をもたないが、レベルが非可算になる。そこで、互いにほぼ一致する単射の列を 1 本固定し、その有限の修正だけを残す。
次を満たす $s_\alpha\colon\alpha\to\omega$($\alpha< \omega_1$)が存在する。
$\alpha$ についての超限帰納法で作る。$s_0=\emptyset$ とする。$s_{\alpha+1}$ は、$n\notin\operatorname{ran}(s_\alpha)$ を選び $s_\alpha\cup\{(\alpha,n)\}$ とする。3 により $n$ は選べて、余白はなお無限である。
$\gamma$ を極限順序数とし、$s_\alpha$($\alpha< \gamma$)ができているとする。$\gamma$ に収束する狭義増加列 $\alpha_0< \alpha_1< \cdots$ をとる。単射 $t_n\colon\alpha_n\to\omega$ を、$t_n\sim s_{\alpha_n}$、$t_{n+1}\restriction\alpha_n=t_n$ となるように順に作る。$t_0:=s_{\alpha_0}$ とする。
$t_n$ ができたとして、$v:=s_{\alpha_{n+1}}$ とおく。2 と $t_n\sim s_{\alpha_n}$ から $t_n\sim v\restriction\alpha_n$ である。$v$ は単射なので、$\operatorname{ran}(t_n)\setminus\operatorname{ran}(v\restriction\alpha_n)$ は有限集合である。したがって $F:=\{\xi\in[\alpha_n,\alpha_{n+1})\mid v(\xi)\in\operatorname{ran}(t_n)\}$ は有限集合である。また 3 により、$\operatorname{ran}(t_n)\cup\operatorname{ran}(v)$ の外に無限個の自然数が残る。$t_{n+1}$ を、$\alpha_n$ の上では $t_n$、$[\alpha_n,\alpha_{n+1})\setminus F$ の上では $v$ と等しく、$F$ の上ではその残りの自然数への単射とする。これは単射で、$v$ と有限個の点でしか違わない。
$t:=\bigcup_nt_n\colon\gamma\to\omega$ は単射である。$\alpha< \gamma$ なら、$\alpha\le\alpha_n$ となる $n$ について $t\restriction\alpha=t_n\restriction\alpha\sim s_{\alpha_n}\restriction\alpha\sim s_\alpha$ である。ただし $t$ の値域の補集合は有限かもしれない。そこで
$$
s_\gamma(\alpha_n):=t(\alpha_{2n}),\qquad s_\gamma(\xi):=t(\xi)\quad(\xi\notin\{\alpha_n\mid n\in\omega\})
$$
と定める。$s_\gamma$ は単射で、$\{t(\alpha_{2n+1})\mid n\in\omega\}$ を値にとらないので 3 を満たす。$\alpha< \gamma$ のとき $\alpha_n< \alpha$ となる $n$ は有限個なので、$s_\gamma\restriction\alpha\sim t\restriction\alpha\sim s_\alpha$ である。$\square$
ZFC で $\omega_1$-Aronszajn 木が存在する(Kun80 Ch. II Thm 5.9)。
$T$ を、すべての $\alpha< \omega_1$ についての単射 $\alpha\to\omega$ の全体とし、延長で順序づける。lem-at-coherent の列について
$$
T^*:=\{t\in T\mid t\sim s_{\operatorname{dom}(t)}\}
$$
とおく。$t\in T^*$、$\beta< \operatorname{dom}(t)=\alpha$ なら $t\restriction\beta\sim s_\alpha\restriction\beta\sim s_\beta$ だから、$T^*$ は部分木である。$s_\alpha\in T^*$ なので $T^*$ の高さは $\omega_1$ である。第 $\alpha$ レベルの元は $s_\alpha$ の有限個の値を書き換えたものであり、有限個の点と有限個の値の取り方は高々可算なので、レベルは高々可算である。よって $T^*$ は $\omega_1$-木である。
$C\subset T^*$ が非可算の鎖なら、prop-at-branch の証明のとおり定義域は $\omega_1$ で非有界であり、$\bigcup C$ は単射 $\omega_1\to\omega$ となる。これは不可能である。$\square$
証明が使っているのは、$\omega_1$ が $\omega$ に単射されないことと、$\omega_1$ 未満の順序数は $\omega$ に単射されることの落差である。余白の条件 3 は極限の段を通過するための帳尻合わせであり、これがないと次の段に進めなくなる。
上の $T^*$ は、「非可算の鎖をもたない $\omega_1$-木は非可算の反鎖ももたない」という含意の反例である(Kun80 Ch. II Exercise 39)。
極限のレベルも含めて木全体を可算個の反鎖で覆えるとき、鎖の非存在は一目で分かる。
$\omega_1$-木 $T$ が特殊(special)であるとは、$T$ が可算個の反鎖の和集合であることをいう。
鎖は 1 つの反鎖と高々 1 点でしか交わらないので、特殊な $\omega_1$-木の鎖は高々可算であり、特殊な $\omega_1$-木は Aronszajn 木である。上の $T^*$ で覆えたのは後続のレベルだけである。実際、$\diamondsuit$ のもとでは単射の木の Aronszajn 部分木で特殊でないものが存在する(Kun80 Ch. II Exercise 40 の注記)。
$\omega_1$-木 $T$ が特殊であることと、$x< y$ ならば $f(x)< f(y)$ となる写像 $f\colon T\to\mathbb Q$ が存在することは同値である。
$f$ があれば、各 $f^{-1}(q)$ は反鎖なので $T$ は特殊である。
逆に、$T$ が互いに素な反鎖 $A_n$($n\in\omega$)の和であるとする。$x\in A_{n(x)}$ となる番号を $n(x)$ とし、$S(x):=\{n(y)\mid y\le x\}$ とおき、
$$
f(x):=\sum_{k\in S(x),\ k\le n(x)}2^{-k-1}\in\mathbb Q
$$
と定める。$x< y$ とする。$A_{n(x)}$ は反鎖だから $n(x)\ne n(y)$ であり、$S(x)\subset S(y)$ である。
$n(x)< n(y)$ なら、$f(y)$ の和は $f(x)$ の和の項をすべて含み、さらに項 $2^{-n(y)-1}$ を含むので $f(x)< f(y)$ である。
$n(y)< n(x)$ とする。$n(y)\in S(x)$ なら $n(z)=n(y)$ となる $z\le x< y$ があり、$z$ と $y$ は同じ反鎖の比較可能な相異なる 2 点となって矛盾する。よって $n(y)\notin S(x)$ である。$m:=n(y)$、$a:=\sum_{k\in S(x),k< m}2^{-k-1}$ とおくと、$f(y)\ge a+2^{-m-1}$ であり、
$$
f(x)\le a+\sum_{k=m+1}^{n(x)}2^{-k-1}< a+2^{-m-1}
$$
である。よって $f(x)< f(y)$ である。$\square$
この言い換えから、特殊な木を有理数の狭義増加列で直接作る第 2 の証明が得られる。
ZFC で特殊な $\omega_1$-Aronszajn 木が存在する(Kun80 Ch. II Exercise 40)。
狭義増加列 $s\colon\alpha+1\to\mathbb Q$ の集合 $U_\alpha$($\alpha< \omega_1$)を、次を満たすように帰納的に作る。
(a)(b) の仕組みは、lem-at-coherent の余白と同じ役割を果たす。極限の段を通るためには、どの点の上にも「まだ上に伸びられる余地」を $\mathbb Q$ の中に残しておく必要がある。
特殊でない Aronszajn 木の存在は ZFC では決まらない。Martinの公理 の $\aleph_1$ 個の稠密集合についての形を $\mathrm{MA}_{\aleph_1}$ と書く。
$\mathrm{MA}_{\aleph_1}$ を仮定する。すべての $\omega_1$-Aronszajn 木は特殊である。
$T$ を $\omega_1$-Aronszajn 木とする。$\mathbb P$ を、$T$ の有限部分集合で定義された $\mathbb Q$ への狭義単調な部分写像の全体とし、延長が強い条件であるように順序づける。
$\mathbb P$ が ccc であることを示す。$\{p_\xi\mid\xi< \omega_1\}\subset\mathbb P$ とする。Δ-システム の補題と、$r$ から $\mathbb Q$ への写像が高々可算個であることから、非可算の部分族に移って、定義域が根 $r$ をもつ $\Delta$-システムをなし、$p_\xi\restriction r$ はすべて等しく、尾 $\operatorname{dom}(p_\xi)\setminus r=\{x^\xi_1,\dots,x^\xi_k\}$ の個数 $k$ は一定としてよい。$k=0$ なら $p_\xi$ はすべて等しいので $k\ge1$ とする。各レベルは可算なので、さらに部分族に移って、$\xi< \eta$ なら $\operatorname{dom}(p_\xi)$ の元の高さがすべて $\eta$ の尾の元の高さより小さいとしてよい。
$\xi< \eta$ で、どの $i,j$ についても $x^\xi_i\not< x^\eta_j$ となるものがあることを示す。そうすれば $p_\xi\cup p_\eta$ は写像であり、高さの条件から尾の間に順序関係がないので狭義単調で、$p_\xi,p_\eta$ は両立する。
そのような組がないとする。$\omega_1$ 上の、可算集合を含まない超フィルター $U$ を固定する。各 $\xi$ について、$\eta>\xi$ のすべてにある $(i,j)$ で $x^\xi_i< x^\eta_j$ となるから、ある $(i(\xi),j(\xi))$ で $\{\eta\mid x^\xi_{i(\xi)}< x^\eta_{j(\xi)}\}\in U$ となる。非可算な $S$ の上で $(i(\xi),j(\xi))$ は一定値 $(i,j)$ をとる。$\xi,\xi'\in S$ なら、$U$ の 2 元の共通部分から $\eta$ をとれて、$x^\xi_i$ と $x^{\xi'}_i$ はともに $x^\eta_j$ より下にあるので比較可能である。よって $\{x^\xi_i\mid\xi\in S\}$ は非可算の鎖となり、$T$ が Aronszajn 木であることに反する。
$x\in T$ について $D_x:=\{p\mid x\in\operatorname{dom}(p)\}$ は稠密である。実際、$x\notin\operatorname{dom}(p)$ のとき、$\operatorname{dom}(p)$ の中で $x$ の下にある元の値はどれも $x$ の上にある元の値より小さいので、その間の有理数を $x$ の値にできる。$|T|=\aleph_1$ なので、$\mathrm{MA}_{\aleph_1}$ により、すべての $D_x$ と交わるフィルター $G$ がある。$\bigcup G\colon T\to\mathbb Q$ は狭義単調であり、prop-at-rational により $T$ は特殊である。$\square$
これは Baumgartner の結果で、Kun80 Ch. II Exercise 41 に MA + $\neg$CH の形で挙げられている。上の ccc の議論は、$T$ に非可算の鎖がないことを本質的に使う。
$\kappa$ が大きくなると、存在は集合論の仮定に左右される(Kun80 Ch. II pp. 70–71)。
| $\kappa$ | $\kappa$-Aronszajn 木 |
|---|---|
| $\omega$ | 存在しない(König の補題) |
| $\omega_1$ | ZFC で存在する(thm-at-existence) |
| $\lambda^+$($\lambda$ は正則で $2^{< \lambda}=\lambda$) | 存在する(thm-at-successor)。CH のもとで $\omega_2$ の場合を含む |
| $\omega_2$(CH を仮定しない) | 存在することは $2^{\aleph_0}=\aleph_2$ と両立する。存在しないことも、弱コンパクト基数 の存在の無矛盾性のもとで両立する(Mitchell 1972) |
| 強到達不能基数 | 存在しないことが 弱コンパクト基数 の特徴づけになる |
$\lambda$ を非可算の正則基数で $2^{< \lambda}=\lambda$ を満たすものとする。$\lambda^+$-Aronszajn 木が存在する。
要点:thm-at-existence の証明の $\omega$ を $\lambda$ に、「有限個」を「$\lambda$ 未満個」に、余白の条件を「値域が $\lambda$ の非定常集合」に置き換える。
仮定から $\lambda^{< \lambda}=\lambda$ である。$\alpha< \lambda^+$ について、$s,t\colon\alpha\to\lambda$ が $\lambda$ 未満個の点でしか違わないことを $s\sim t$ と書く。単射 $s_\alpha\colon\alpha\to\lambda$ で、$\alpha< \beta$ なら $s_\alpha\sim s_\beta\restriction\alpha$、値域が $\lambda$ で非定常なものを帰納的に作る。後続の段は余白の値を 1 つ足す。
$\gamma$ を極限順序数、$\mu=\operatorname{cf}(\gamma)\le\lambda$、$(\alpha_\xi)_{\xi< \mu}$ を $\gamma$ に収束する狭義増加の連続な列とする。単射 $t_\xi\colon\alpha_\xi\to\lambda$ と順序数 $\gamma_\xi< \lambda$ を、$t_\xi\sim s_{\alpha_\xi}$、$\zeta< \xi$ なら $t_\xi$ は $t_\zeta$ の延長、値域は $\{\gamma_\zeta\mid\zeta< \xi\}$ を避ける、という形で順に作る。極限の $\xi$ では $t_\xi=\bigcup_{\zeta< \xi}t_\zeta$ とする。$\xi< \lambda$ なので書き換えた点は $\lambda$ 未満個であり、$t_\xi\sim s_{\alpha_\xi}$ で値域は非定常である。後続の段は、$t_\xi$ と $s_{\alpha_{\xi+1}}$ を $[\alpha_\xi,\alpha_{\xi+1})$ でつなぎ、値の衝突が起こる点と $\{\gamma_\zeta\}$ を値にとる点(どちらも $\lambda$ 未満個)を余白の値に書き換える。余白は濃度 $\lambda$ である。各 $\xi$ で $t_\xi$ の値域と交わらない閉非有界集合 $D_\xi$ をとり、$\gamma_\xi$ を、それ以前の $\gamma_\zeta$ より大きく $\bigcap_{\zeta\le\xi}D_\zeta$ に属するものとし、極限の $\xi$ では上限をとる。上限は各 $D_\zeta$ に属するから $t_\xi$ の値域にない。
$\mu< \lambda$ なら $s_\gamma:=\bigcup_\xi t_\xi$ は書き換えが $\lambda$ 未満個で、値域は $\lambda$ 未満個の非定常集合の和に含まれるので非定常である。$\mu=\lambda$ なら $s_\gamma:=\bigcup_\xi t_\xi$ の値域は閉非有界集合 $\{\gamma_\xi\mid\xi< \lambda\}$ を避ける。各 $\alpha< \gamma$ について $s_\gamma\restriction\alpha\sim s_\alpha$ である。
$T^*$ を、$t\sim s_{\operatorname{dom}(t)}$ となる単射 $t$ の全体とする。部分木である。第 $\alpha$ レベルの元について、$s_\alpha$ と値が違う点の集合の取り方は $|\alpha|^{< \lambda}\le\lambda^{< \lambda}=\lambda$ 通り以下で、それらの点の値の取り方も $\lambda^{< \lambda}=\lambda$ 通り以下である。よって各レベルの濃度は $\lambda$ 以下である。濃度 $\lambda^+$ の鎖があれば単射 $\lambda^+\to\lambda$ ができる。よって $T^*$ は $\lambda^+$-Aronszajn 木である。$\square$
これは Kun80 Ch. II Exercise 37 の主張である(Exercise の $\lambda$ は $\omega$ も含み、その場合が thm-at-existence である)。
Aronszajn 木は枝が 1 本もない $\kappa$-木である。反対の極は、枝が多すぎる $\kappa$-木である。
$\kappa$ を正則基数とする。$\kappa^+$ 本以上の枝をもつ $\kappa$-木を $\kappa$-Kurepa 木という。$\omega_1$-Kurepa 木が存在するという主張を Kurepa 仮説(KH)という。
$\kappa$ の部分集合の族 $\mathcal F$ で、$|\mathcal F|\ge\kappa^+$ かつすべての $\alpha< \kappa$ について $|\{A\cap\alpha\mid A\in\mathcal F\}|< \kappa$ を満たすものを $\kappa$-Kurepa 族という。
$\kappa=\omega$ や強到達不能基数の $\kappa$ では、完全 2 分木 ${}^{<\kappa}2$ が $2^\kappa>\kappa$ 本の枝をもつので $\kappa$-Kurepa 木である。問題になるのは $\kappa=\omega_1$ のような場合である。${}^{<\omega_1}2$ は第 $\omega$ レベルが非可算なので $\omega_1$-木ではない。
$\kappa$ を正則基数とする。$\kappa$-Kurepa 木が存在することと、$\kappa$-Kurepa 族が存在することは同値である(Kun80 Ch. II Thm 5.18)。
$\mathcal F\subset\mathcal P(\kappa)$ を Kurepa 族とする。$\alpha< \kappa$ と $B\in\{A\cap\alpha\mid A\in\mathcal F\}$ について、$B$ の特性関数 $\chi_B\colon\alpha\to2$ を考え、その全体を $T\subset{}^{<\kappa}2$ とする。$T$ は部分木で、第 $\alpha$ レベルの濃度は $\kappa$ 未満である。$A\in\mathcal F$ の特性関数の制限の全体は枝であり、$A$ が違えば枝も違う。よって $T$ は $\kappa$-Kurepa 木である。
$T$ を $\kappa$-Kurepa 木とする。$\kappa$ の正則性から $|T|=\kappa$ である。全単射 $e\colon T\to\kappa$ を固定し、$\mathcal F$ を、枝 $C$ の像 $e[C]$ の全体とする。$|\mathcal F|\ge\kappa^+$ である。$\alpha< \kappa$ について $X:=e^{-1}[\alpha]$ とおくと、$|X|< \kappa$ であり、$\kappa$ の正則性からある $\beta< \kappa$ で $X$ の元の高さはすべて $\beta$ 未満である。枝 $C$ は $\operatorname{Lev}_\beta(T)$ のちょうど 1 点 $z$ を含み、$C\cap X=\{x\in X\mid x< z\}$ である。$C\cap X$ は $z$ で決まるので、$e[C]\cap\alpha=e[C\cap X]$ の取り方は $|\operatorname{Lev}_\beta(T)|< \kappa$ 通り以下である。$\square$
台が有限な $0,1$ 列の木 $T:=\{s\in{}^{<\omega_1}2\mid\{\alpha\mid s(\alpha)=1\}\text{ は有限}\}$ は、Aronszajn 木でも Kurepa 木でもない $\omega_1$-木である。
Kurepa 仮説は、強到達不能基数の存在の無矛盾性のもとで ZFC から独立である。組合せ原理 $\diamondsuit^+$ から $\omega_1$-Kurepa 木の存在が従い、$V=L$ のもとで $\diamondsuit^+$ が成り立つ(ダイヤモンド原理、Kun80 Ch. II Cor. 7.11、Ch. VI Thm 5.2)。逆に Silver は、強到達不能基数の存在の無矛盾性から KH の否定の無矛盾性を導いた。到達不能基数は必要であり、ZFC + $\neg$KH の無矛盾性は ZFC + 「強到達不能基数が存在する」の無矛盾性と同値である(Kun80 Ch. VIII §3、p. 259)。この記事ではこれらを証明しない。
| 外す条件 | 木 | 成り立たなくなること |
|---|---|---|
| レベルが有限($\omega$ の場合) | 長さ $n$ の鎖を $n\in\omega$ ごとに根を分けて並べた木 | レベル $0$ が無限で、無限鎖がない |
| レベルが $\kappa$ 未満 | 単射 $\alpha\to\omega$($\alpha< \omega_1$)の全体 | 高さ $\omega_1$ で非可算の鎖がないが、第 $\omega$ レベルが非可算なので $\omega_1$-木ではない |
| 鎖がないこと | 順序数 $\omega_1$ そのもの | $\omega_1$-木で、枝をもつ |
| 高さが $\kappa$ | 順序数 $\omega$ | レベルは有限で非可算の鎖はないが、高さが足りない |
| $\kappa$ が正則 | $\aleph_n$($n\in\omega$)の非交和、$\kappa=\aleph_\omega$ | 高さ $\kappa$、レベルは可算、鎖の濃度は $\kappa$ 未満。特異基数では自明に起こる |
| Aronszajn 性(thm-at-ma の仮定) | 順序数 $\omega_1$ | $\mathbb Q$ への狭義単調写像がない |
最後の行は、$\omega_1$ から $\mathbb Q$ への狭義単調写像があれば $\mathbb Q$ の中に長さ $\omega_1$ の増加列ができて、$\mathbb Q$ の可算性に反することによる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する