Königの補題

同義語：König's lemmaKőnigの補題Königの無限補題

概要

前提知識: 木(グラフ), 有限集合, コンパクト性定理(命題論理)

König の補題（König's lemma）は、無限に大きい木で、どの頂点からも有限本の枝しか出ていないものには、根から終わりなく続く枝が必ずある、という主張である。各頂点の先が有限通りしかないので、「その先に無限に多くの頂点が続く」という性質を保ったまま一歩ずつ進める、というのが証明の核心である。ハンガリーの数学者 Dénes Kőnig（ハンガリー語の綴りは ő）がグラフ理論の最初の教科書（1936 年）に収めた補題で、日本語・英語では König とも書かれる。
この補題は、有限の場合に成り立つことを無限の場合へ移す「コンパクト性」の議論の最も基本的な形である。この記事では、補題を直接の論法とコンパクト性定理の 2 通りで証明し、有限分岐の仮定が外せないこと、グラフの言葉での形、証明に要る選択公理の強さ、二階算術での強さを述べる。
同じ名を冠する別の定理に、基数の和と積の不等式である Königの定理、二部グラフで最大マッチングと最小頂点被覆の大きさが等しいという König の定理（マッチング(グラフ理論) の定理「二部グラフの最大マッチングと最小頂点被覆」）、Königの辺彩色定理がある。この記事の補題はそのどれとも別の主張である。

定義

集合 $X$ の元の有限列 $\sigma=(a_0,\dots,a_{n-1})$ の全体を $X^{<\omega}$ と書き、$n$ を長さ $|\sigma|$ という（空列 $()$ も含める）。$m\le|\sigma|$ について、最初の $m$ 項からなる列を $\sigma|m$ と書き、$\sigma$ の 始切片 という。$\tau|\,|\sigma|=\sigma$ となる $\tau$ を $\sigma$ の延長という（$\sigma$ 自身も含める）。

列の木

$X^{<\omega}$ の空でない部分集合 $T$ が始切片で閉じているとき、$T$ を（$X$ 上の）木という。$T_n:=\{\sigma\in T\mid|\sigma|=n\}$ を第 $n$ 層という。

$\sigma\in T_n$ について、$\tau|n=\sigma$ となる $\tau\in T_{n+1}$ を $\sigma$ の子という。どの $\sigma\in T$ も有限個の子しかもたないとき、$T$ は 有限分岐 であるという。
無限列 $(a_0,a_1,\dots)$ で、すべての $n$ について $(a_0,\dots,a_{n-1})\in T$ となるものを $T$ の 無限の枝 という。

木が有限分岐であることと、すべての層が有限集合であることは同値である。有限分岐なら $T_0=\{()\}$ と「$T_{n+1}$ は $T_n$ の各元の子の和」から帰納法で各層が有限になり、逆に各層が有限なら、$T_n$ の元の子は $T_{n+1}$ の元なので有限個である。
空列 $()$ を根とし、各列をその子と辺で結ぶと根付きの木（グラフ）になり、層は根からの距離、無限の枝は根から出る終わりのない道にあたる。

直感

根から歩き始め、分かれ道に来るたびにどちらへ進むかを決めるとする。無限に多くの頂点があっても、選び方を誤ると行き止まりに着くことがある（有限の枝に入ってしまう）。そこで「この先にまだ無限に多くの頂点がある」という目印を頼りに進む。分かれ道の数が有限なら、無限に多くの頂点を有限個の行き先に配ると、どれか 1 つの行き先には無限に多く残る（鳩の巣原理）。だから目印の付いた行き先が必ずあり、目印をたどれば行き止まりに着かない。分かれ道が無限にあると、無限に多くの頂点が「長さの限られた枝」に 1 つずつ散らばって、どの行き先にも無限には残らないことがある（ex-konig-infinite-branching）。

主定理

König の補題

無限集合である有限分岐の木 $T$ は、無限の枝をもつ。

先が無限に続く頂点をたどる

要点：延長を無限に多くもつ列の全体 $T'$ を考えると、$T'$ の列は $T'$ に属する子を必ずもつ。根から $T'$ の中を一歩ずつ進めばよい。
$T$ の列のうち、$T$ の中に延長を無限に多くもつものの全体を $T'$ とする。$T$ のすべての列は空列の延長なので、$T$ が無限集合であることから $()\in T'$ である。
$\sigma\in T'$ とし、その子を $\tau_1,\dots,\tau_k$ とする（有限分岐）。$\sigma$ の延長は、$\sigma$ 自身か、どれかの $\tau_i$ の延長である。$\tau_i$ の延長がどれも有限個なら、$\sigma$ の延長は有限個の有限集合の和に $\sigma$ を加えたもので有限になり、$\sigma\in T'$ に反する（鳩の巣原理）。よって $\sigma$ の子で $T'$ に属するものがあり、そのような子の集合 $C(\sigma)$ は空でない有限集合である。
各 $\sigma\in T'$ について $C(\sigma)$ の元を 1 つ選ぶ関数 $g$ をとり（選択公理。どれだけの選択で足りるかは後の thm-konig-choice で述べる）、$\sigma_0:=()$、$\sigma_{n+1}:=g(\sigma_n)$ と再帰で定める。$\sigma_n\in T'$、$|\sigma_n|=n$ で、$\sigma_{n+1}$ は $\sigma_n$ の子なので $\sigma_{n+1}|n=\sigma_n$ であり、帰納法で $m\ge n$ なら $\sigma_m|n=\sigma_n$ である。$a_n$ を $\sigma_{n+1}$ の最後の項とすると $(a_0,\dots,a_{n-1})=\sigma_n\in T$ なので、$(a_0,a_1,\dots)$ は $T$ の無限の枝である。$\square$

目印が必要な木

$X=\{0,1\}$ とし、$T$ を $0$ だけからなる列 $(0,\dots,0)$（長さは任意）と、列 $(1,0,\dots,0)$（$0$ が $5$ 個以下）の全体とする。$T$ は無限集合で、各列の子は $2$ 個以下である。根から「最後の項が大きい子」を選んで進むと、$(1)$ から長さ $6$ の列 $(1,0,0,0,0,0)$ で行き止まりになる。延長を無限に多くもつ列の全体 $T'$ は $0$ だけからなる列の全体で、証明のとおり $T'$ の中を進めば無限の枝 $(0,0,0,\dots)$ が得られる。各段で見るべきなのは子の値ではなく、その先に無限に多くの列が続くかどうかである。

$X$ が自然数の集合のように整列されていれば、$g(\sigma)$ として $C(\sigma)$ の中で最後の項が最小のものをとればよく、選択公理は要らない。

コンパクト性定理から

要点：「各層からちょうど 1 つ選び、選んだ列の親も選ぶ」を命題論理の論理式で書くと、有限個の論理式は浅い層しか話題にしないので満たせる。

証明を開く

各層 $T_n$ は有限集合である（$T_0=\{()\}$ で、$T_{n+1}$ は $T_n$ の各元の有限個の子の和）。ある $T_N$ が空なら $T_m$（$m\ge N$）もすべて空で、$T$ は有限になるので、どの層も空でない。$\sigma\in T$ ごとに命題変数 $q_\sigma$ を用意し、$\Sigma$ を次の論理式全体とする。(i) 各 $n$ について $T_n$ の元すべての $q_\sigma$ の選言。(ii) 各 $n$ と $T_n$ の相異なる $\sigma,\tau$ について $\lnot(q_\sigma\land q_\tau)$。(iii) 各 $\sigma\in T_{n+1}$ について $q_\sigma\to q_{\sigma|n}$。$T_n$ が有限なので (i) は論理式である。$\Sigma$ の有限部分集合 $F$ に現れる列の長さの最大値を $N$ とし、$\tau\in T_N$ をとって「$q_\sigma$ が真 $\iff$ $\sigma=\tau|\,|\sigma|$ かつ $|\sigma|\le N$」と付値を定めると、$F$ は充足される。コンパクト性定理(命題論理) の定理「命題論理のコンパクト性定理」により $\Sigma$ 全体を充足する付値があり、真になる $q_\sigma$ は各層にちょうど 1 つで、(iii) によりそれらは始切片の関係で並ぶので、無限の枝を与える。$\square$

この別証明では、各段の選択がコンパクト性定理の中に押し込められている。直接の証明は延長の個数を数える議論と各段の選択だけで済み、どれだけの選択が要るかも正確に分かる（thm-konig-choice）。一階論理のコンパクト性定理などの一般のコンパクト性の原理は、König の補題より強い原理である（Die25 p. 294 の注。この記事では証明しない）。

グラフの形

木(グラフ) の記事のとおり、木は閉路をもたない連結グラフである。各頂点の次数が有限のグラフを 局所有限 といい、頂点の列 $v_0v_1v_2\cdots$ で相異なり隣り合う 2 頂点が隣接するものを 半無限道 という。

局所有限な無限の木

局所有限な無限の木（グラフ）は、任意の頂点から始まる半無限道を含む。

頂点 $r$ を固定する。木では $r$ から各頂点 $v$ への道がただ 1 つあるので、それを頂点の列 $(r,\dots,v)$ と見て、$r$ から出る道全体を頂点集合 $V$ 上の列の木 $T$ とする（$r$ だけの道を空列にあたるものとみなし、各道から最初の頂点 $r$ を除いた列をとる）。始切片で閉じており、道と頂点が 1 対 1 に対応するので $T$ は無限集合である。$v$ への道の子は $v$ の隣接頂点のうち $r$ から遠い側のものへ延ばした道なので、局所有限なら $T$ は有限分岐である。thm-konig-lemma の無限の枝 $(a_0,a_1,\dots)$ について、$r,a_0,a_1,\dots$ は各始切片が道なので相異なり、半無限道である。$\square$

無限グラフの記事の補題「König の無限補題」は、互いに交わらない空でない有限集合 $V_0,V_1,\dots$ で、$V_n$ の各頂点が $V_{n-1}$ のある頂点と隣接するとき、$v_n\in V_n$ となる半無限道があると述べる。$V_n$ を層、隣接する $V_{n-1}$ の頂点を親とみれば、これも同じ補題の言い換えである。この層の形は Die25 Lemma 8.1.2（p. 233）にあり、同書は Kőnig の 1936 年の教科書がこれを含むことを記している（p. 294）。

応用：無限から有限へ

König の補題の典型的な使い方は、「無限の対象についての主張」から「十分大きい有限の対象についての主張」を取り出すことである。

色分けの主張の有限化

$C$ を有限集合（色の集合）、$\mathcal B$ を $\mathbb N$ の有限部分集合の族とする。どの写像 $\chi\colon\mathbb N\to C$ についても、$\chi$ が定数になる $B\in\mathcal B$ があるとする。このとき、ある $n$ があって、どの写像 $\chi\colon\{0,\dots,n-1\}\to C$ についても、$B\subset\{0,\dots,n-1\}$ で $\chi$ が $B$ の上で定数になる $B\in\mathcal B$ がある。

長さ $m$ の列 $(c_0,\dots,c_{m-1})\in C^{<\omega}$ を $\{0,\dots,m-1\}$ の色分け $i\mapsto c_i$ とみなし、$B\subset\{0,\dots,m-1\}$ で色が一定になる $B\in\mathcal B$ がない列の全体を $T$ とする。始切片の色分けは元の色分けの制限なので、$T$ は始切片で閉じた木であり、各列の子は $|C|$ 個以下なので有限分岐である。結論が成り立たないとすると、どの $n$ にも $T$ に属する長さ $n$ の列があり、$T$ は無限集合である。thm-konig-lemma の無限の枝 $(c_0,c_1,\dots)$ で $\chi(i):=c_i$ と定めると、$B\in\mathcal B$ は有限なので $B\subset\{0,\dots,m-1\}$ となる $m$ があり、$(c_0,\dots,c_{m-1})\in T$ だから $\chi$ は $B$ の上で定数でない。これは仮定に反する。$C$ は有限で整列できるので、この証明は選択公理を使わない。$\square$

たとえば $\mathcal B$ を長さ $k$ の等差数列の全体とすると、仮定は「$\mathbb N$ をどう有限色に塗っても同じ色の長さ $k$ の等差数列がある」という van der Waerden の定理の無限の形であり、結論はその有限の形である（この記事では van der Waerden の定理自体は証明しない）。

仮定を外した場合

外す条件	反例	成り立たなくなること
有限分岐	下の例の木	無限集合で、任意に長い有限の列を含むが、無限の枝がない
無限集合	有限の木 $\{()\}$	無限の枝がない（自明）
選択公理（$\mathsf{ZF}$ だけで考える）	選択関数のない対の列から作る 2 分岐の木	$\mathsf{ZF}$ だけでは無限の枝の存在を証明できない

反例：有限分岐でない木

$X=\mathbb N$ とし、$T$ を空列と、列 $(n,0,\dots,0)$（$n\in\mathbb N$、$0$ が $k$ 個、$0\le k\le n$）の全体とする。始切片で閉じているので木であり、無限集合で、$n$ で始まる長さ $n+1$ の列があるので任意に長い列を含む。しかし無限の枝 $(a_0,a_1,\dots)$ があれば、$a_0=n$ として長さ $n+2$ の列 $(a_0,\dots,a_{n+1})$ が $T$ に属するが、$n$ で始まる $T$ の列の長さは $n+1$ 以下なので矛盾する。根の子 $(n)$ が無限個あるので有限分岐でない。証明では、$T'$ に属する子を見つける段で、子が有限個であることを使っている。

3 行目の木は、次の定理の証明の後半で作るものである。

選択公理の強さ

可算個の空でない有限集合の列 $(F_n)_{n\in\mathbb N}$ に対して、すべての $n$ で $h(n)\in F_n$ となる関数 $h$ が存在するという主張を、有限集合の可算選択公理 といい、$\mathsf{AC}_\omega(\mathrm{fin})$ と書く。

König の補題と有限集合の可算選択

$\mathsf{ZF}$ において、König の補題（任意の集合 $X$ 上の木について）と $\mathsf{AC}_\omega(\mathrm{fin})$ は同値である。

$\mathsf{AC}_\omega(\mathrm{fin})$ から König の補題：$T$ を無限集合である有限分岐の木とする。各層 $T_n$ は空でない有限集合である。実際、$T_0=\{()\}$ で、$T_{n+1}$ は $T_n$ の各元の有限個の子の和なので有限であり、ある $T_N$ が空なら以後の層もすべて空で $T$ が有限になるからである。この議論は選択を使わない。有限集合 $T_n$ の上の線形順序全体の集合は空でない有限集合なので、$\mathsf{AC}_\omega(\mathrm{fin})$ により、各 $n$ について $T_n$ の線形順序 $<_n$ を 1 つずつ選べる。prf-konig-lemma の $T'$ と $C(\sigma)$ は選択なしに定まり、$g(\sigma)$ を $C(\sigma)$ の $<_{|\sigma|+1}$ に関する最小元とすれば、あとの議論はそのまま選択なしに進む。
König の補題から $\mathsf{AC}_\omega(\mathrm{fin})$：空でない有限集合の列 $(F_n)$ に対し、$X:=\bigcup_nF_n$ 上の木 $T$ を、$a_i\in F_i$（$i< n$）となる列 $(a_0,\dots,a_{n-1})$ 全体とする。始切片で閉じており、長さ $n$ の列の子は $F_n$ の元で 1 対 1 に対応するので有限分岐である。各 $T_n$ は空でない（有限個の空でない集合の積は、個数に関する帰納法で空でない）ので、$T$ は無限集合である。König の補題による無限の枝 $(a_0,a_1,\dots)$ について $h(n):=a_n$ とおけば $h(n)\in F_n$ である。$\square$

従属選択公理 $\mathsf{DC}$ からは可算選択公理が従い、それは $\mathsf{AC}_\omega(\mathrm{fin})$ を含むので、König の補題は $\mathsf{DC}$ から従う。一方、2 元集合の可算列で選択関数をもたないものがある $\mathsf{ZF}$ のモデルが知られている（Jec73 Theorem 5.20、p. 71。この記事では証明しない）。そのような列 $(F_n)$ から上の証明で作った木は、各層が空でない 2 分岐の無限の木で、そのモデルでは無限の枝をもたない。したがって König の補題は $\mathsf{ZF}$ だけでは証明できない。$X$ が整列可能なら選択は要らないので、反例の木は必ず整列できない集合の上にある。

二階算術での強さ

自然数の有限列の木 $T\subset\mathbb N^{<\omega}$ に限ると、選択の問題はなくなるが、無限の枝を「計算」できるかという別の問題が現れる。逆数学の基本体系 $\mathsf{RCA}_0$ の上で、König の補題（$\mathbb N^{<\omega}$ の有限分岐の無限の木は無限の枝をもつ）は算術的内包公理の体系 $\mathsf{ACA}_0$ と同値である（Sim06 Theorem I.9.3、p. 35。この記事では証明しない）。$\mathsf{RCA}_0$ では証明できないことは、計算可能な有限分岐の無限の木で計算可能な無限の枝をもたないものがあることによる（Sim06 Example I.8.8、pp. 31–32）。
0 と 1 の列の木 $T\subset\{0,1\}^{<\omega}$ に限った形を 弱 König の補題 という。これを $\mathsf{RCA}_0$ に加えた体系が $\mathsf{WKL}_0$ であり（Sim06 Definition I.10.1、p. 37）、König の補題よりずっと弱い（同書 p. 48）。弱 König の補題が $\mathsf{ACA}_0$ で証明できることは、逆数学の記事の命題「算術的内包から弱König補題を導く」で証明されている。