Aronszajn木

同義語:Aronszajn tree

概要

Aronszajn木(Aronszajn tree)とは、高さが $\omega_1$ で各レベルが高々可算だが、非可算の鎖をもたない集合論の木である。より一般に、正則基数 $\kappa$ について高さ $\kappa$、各レベルの濃度が $\kappa$ 未満で、濃度 $\kappa$ の鎖をもたない木を $\kappa$-Aronszajn 木という。$\omega$ には König の補題により存在しないが、$\omega_1$ には ZFC で存在し、非可算の高さでは König の補題の類似が成り立たない例になっている。可算個の反鎖で覆える特殊な Aronszajn 木も ZFC で存在する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 順序数, 基数, 正則基数, Königの補題

各段が有限個の点からなる無限の木には、どこまでも伸びる枝がある。これが 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\}$ が $<$ で整列されているものをいう。

  • $x$ の高さ $\operatorname{ht}(x)$ は、整列集合 $\{y\mid y< x\}$ の順序型である。
  • 高さが $\alpha$ の元の全体を $T$ の第 $\alpha$ レベル $\operatorname{Lev}_\alpha(T)$ という。
  • $\operatorname{Lev}_\alpha(T)$ が空になる最小の $\alpha$ を $T$ の高さ $\operatorname{ht}(T)$ という。
  • 下に閉じた部分集合 $T'\subset T$ を部分木という。
  • どの 2 元も比較できる部分集合を鎖、どの相異なる 2 元も比較できない部分集合を反鎖という。各レベルは反鎖である。

典型例は、$I$ の元の長さ $\delta$ 未満の列の全体 ${}^{<\delta}I:=\bigcup_{\alpha< \delta}{}^\alpha I$ を、延長の関係で順序づけたものである。$s\le t$ は $t$ が $s$ の延長であることを意味し、$\operatorname{ht}(s)=\operatorname{dom}(s)$ である。

$\kappa$-木と $\kappa$-Aronszajn 木

$\kappa$ を正則基数とする。

  • $\kappa$-木とは、高さが $\kappa$ で、どのレベルも濃度が $\kappa$ 未満の木である。
  • $\kappa$-木 $T$ の枝とは、すべてのレベルと交わる鎖である。
  • $\kappa$-Aronszajn 木とは、濃度 $\kappa$ の鎖をもたない $\kappa$-木である。
  • $\kappa$-Aronszajn 木が存在しないとき、$\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$)が存在する。

  1. $s_\alpha$ は単射である。
  2. $\alpha< \beta$ なら $s_\alpha\sim s_\beta\restriction\alpha$ である。
  3. $\omega\setminus\operatorname{ran}(s_\alpha)$ は無限集合である。

$\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 は極限の段を通過するための帳尻合わせであり、これがないと次の段に進めなくなる。

反例:単射の木は Suslin 木にならない

上の $T^*$ は、「非可算の鎖をもたない $\omega_1$-木は非可算の反鎖ももたない」という含意の反例である(Kun80 Ch. II Exercise 39)。

  • 満たすこと:$\omega_1$-木であり、非可算の鎖をもたない。
  • 満たさないこと:非可算の反鎖をもたないこと。
  • 理由:$n\in\omega$ について $A_n:=\{s\in T^*\mid\exists\alpha\ (\operatorname{dom}(s)=\alpha+1,\ s(\alpha)=n)\}$ は反鎖である。$s< t$ がともに $A_n$ に入れば、$t$ が 2 点で値 $n$ をとり、単射に反するからである。後続のレベルの全体は非可算で、$\bigcup_nA_n$ に等しいので、ある $A_n$ が非可算である。

特殊 Aronszajn 木

極限のレベルも含めて木全体を可算個の反鎖で覆えるとき、鎖の非存在は一目で分かる。

特殊

$\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 の証明が得られる。

特殊 Aronszajn 木の存在

ZFC で特殊な $\omega_1$-Aronszajn 木が存在する(Kun80 Ch. II Exercise 40)。

狭義増加列 $s\colon\alpha+1\to\mathbb Q$ の集合 $U_\alpha$($\alpha< \omega_1$)を、次を満たすように帰納的に作る。

  • (a) $U_\alpha$ は高々可算で、空でない。$s\in U_\alpha$、$\beta< \alpha$ なら $s\restriction(\beta+1)\in U_\beta$ である。
  • (b) $\beta< \alpha$、$s\in U_\beta$、$q\in\mathbb Q$、$q>s(\beta)$ なら、$s$ の延長 $t\in U_\alpha$ で $t(\alpha)< q$ となるものがある。
    $U_0$ は長さ $1$ の列の全体とする。後続の段は $U_{\alpha+1}:=\{s\cup\{(\alpha+1,r)\}\mid s\in U_\alpha,\ r\in\mathbb Q,\ r>s(\alpha)\}$ とする。(b) は、$\beta=\alpha$ のとき $s(\alpha)< r< q$ となる $r$ を付け足せばよい。$\beta< \alpha$ のとき、$s(\beta)< r< q$ をとり、(b) により $s$ の延長 $t'\in U_\alpha$ で $t'(\alpha)< r$ となるものをとって、$r$ を付け足せばよい。
    $\alpha$ を極限順序数とする。(b) に現れる組 $(s,q)$ は高々可算個である。各組について $t_{s,q}$ を次のように作り、$U_\alpha$ をそれらの全体とする。$s\in U_\beta$ とし、$\beta=\alpha_0< \alpha_1< \cdots$ を $\alpha$ に収束する列とする。有理数 $q^*$ を $s(\beta)< q^*< q$ からとり、$q_n\nearrow q^*$ となる有理数の狭義増加列を $s(\beta)< q_0$ となるようにとる。$s_0=s$ から始めて、(b) により $s_n$ の延長 $s_{n+1}\in U_{\alpha_{n+1}}$ で $s_{n+1}(\alpha_{n+1})< q_{n+1}$ となるものを順にとる。$s_n$ の最後の値は $q_n$ 未満なので、次の $q_{n+1}$ は (b) の仮定を満たす。$t_{s,q}:=\bigcup_ns_n\cup\{(\alpha,q^*)\}$ とすれば、これは狭義増加で、$s_n$ の値は $q^*$ 未満である。(a)(b) は作り方から成り立つ。
    $T:=\bigcup_\alpha U_\alpha$ を延長で順序づける。$s\in U_\alpha$ の高さは $\alpha$ であり、$T$ は $\omega_1$-木である。$s\in U_\alpha$ について $f(s):=s(\alpha)$(最後の値)とおくと、$s< t$ なら $f(s)< f(t)$ である。prop-at-rational により $T$ は特殊である。$\square$

(a)(b) の仕組みは、lem-at-coherent の余白と同じ役割を果たす。極限の段を通るためには、どの点の上にも「まだ上に伸びられる余地」を $\mathbb Q$ の中に残しておく必要がある。

Martin の公理のもとで

特殊でない 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 である)。

Kurepa 木

Aronszajn 木は枝が 1 本もない $\kappa$-木である。反対の極は、枝が多すぎる $\kappa$-木である。

$\kappa$-Kurepa 木と Kurepa 族

$\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$-木である。

  • レベルは $\alpha$ の有限部分集合の全体と対応するので高々可算である。
  • 枝は台が有限な $\omega_1\to2$ と対応する。その濃度はちょうど $\aleph_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$ の可算性に反することによる。

関連項目

参考文献

[1]
Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, North-Holland (Studies in Logic and the Foundations of Mathematics 102), 1980, Ch. II §5(Lemma 5.7、pp. 69–71、Thm 5.9、Def. 5.15–5.17、Thm 5.18)、§7(Cor. 7.11)、Exercises 37, 39, 40, 41(pp. 90–91)、Ch. VI Thm 5.2、Ch. VIII §3(p. 259)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する