ケーニッヒの補題

ケーニッヒの補題、またはケーニッヒの無限補題は、ハンガリーの数学者デネス・ケーニッヒが1927年に発表したグラフ理論の定理です。 ^{[ 1 ]}この定理は、無限グラフが無限に長いパスを持つための十分条件を与えます。この定理の計算可能性の側面は、数理論理学、特に計算可能性理論の研究者によって徹底的に研究されてきました。この定理は、構成的数学や証明論においても重要な役割を果たしています。

させて${\displaystyle G}$連結で局所的に有限な無限グラフである。これは、任意の2つの頂点が有限の経路で接続でき、各頂点は有限個の他の頂点にのみ隣接し、グラフは無限個の頂点を持つことを意味する。${\displaystyle G}$光線が含まれています。光線とは、1 つの頂点から始まり、そこから無限に多くの頂点を通って続く単純な経路（重複する頂点のない経路）です。この定理を別の言い方で表現すると、「人類が絶滅しないならば、現在生きている誰かの子孫の系譜が絶えることはない」となります。^{[ 2 ]}

この補題の有用な特殊ケースとして、すべての無限木には無限次数を持つ頂点、または無限単純パスが含まれるという点が挙げられる。局所的に有限であれば、この補題の条件を満たし、半直線を持つ。局所的に有限でなければ、無限次数を持つ頂点を持つ。

ケーニッヒの補題の計算可能性の側面は徹底的に調査されてきた。この目的のために、ケーニッヒの補題を、任意の無限有限分岐部分木が${\displaystyle \omega ^{<\omega }}$無限の経路があります。${\displaystyle \omega }$は自然数（順序数とみなされる）の集合を表し、${\displaystyle \omega ^{<\omega }}$ノードがすべて自然数の有限列である木。ノードの親は、列の最後の要素を取り除くことによって得られる。各有限列は、部分関数で識別できる。${\displaystyle \omega }$それ自体に帰着し、各無限経路は総関数と同一視できる。これにより、計算可能性理論の手法を用いた解析が可能となる。

サブツリー${\displaystyle \omega ^{<\omega }}$各シーケンスが有限個の直接拡張しか持たない（つまり、グラフとして見た場合、木の次数が有限である）木は、有限分岐と呼ばれます。すべての無限部分木が${\displaystyle \omega ^{<\omega }}$無限パスを持つが、ケーニッヒの補題によれば、有限分岐の無限部分木は必ずそのようなパスを持つ。

任意のサブツリーに対して${\displaystyle T}$の${\displaystyle \omega ^{<\omega }}$表記法${\displaystyle \operatorname {Ext} (T)}$はノードの集合を表します${\displaystyle T}$そこには無限の道がある。${\displaystyle T}$集合は計算可能である${\displaystyle \operatorname {Ext} (T)}$計算できない場合があります。サブツリーが${\displaystyle T}$の ${\displaystyle \omega ^{<\omega }}$無限の経路があり、経路は以下から計算可能です${\displaystyle \operatorname {Ext} (T)}$段階的に、貪欲に後継者を選び、${\displaystyle \operatorname {Ext} (T)}$各ステップで。${\displaystyle \operatorname {Ext} (T)}$この貪欲なプロセスが停止しないようにします。

非有限分岐計算可能部分木が存在する${\displaystyle \omega ^{<\omega }}$算術的経路がなく、実際には超算術的経路もない。^{[ 3 ]}しかし、すべての計算可能な部分木は${\displaystyle \omega ^{<\omega }}$パスを持つには、クリーネの Oから計算可能なパスが必要です。$\displaystyle \Pi _{1}^{1}}$完全なセットです。これは、セットが${\displaystyle \operatorname {Ext} (T)}$いつも${\displaystyle \Sigma _{1}^{1}}$（この表記の意味については、分析階層を参照してください）${\displaystyle T}$計算可能である。

計算可能な境界を持つ木については、より詳細な分析が行われた。${\displaystyle \omega ^{<\omega }}$計算可能な関数が存在する場合、それは計算可能有界または再帰的に有界であると呼ばれます。${\displaystyle f}$から${\displaystyle \omega }$に${\displaystyle \omega }$木の中のすべてのシーケンスとすべての自然数に対して${\displaystyle n}$、${\displaystyle n}$シーケンスの 番目の要素は最大で${\displaystyle f(n)}$。 したがって${\displaystyle f}$ツリーの「幅」の上限を示します。以下の基底定理は、無限で計算可能な境界を持つ計算可能な部分木に適用されます。${\displaystyle \omega ^{<\omega }}$。

• そのような木には、以下の経路が計算可能である。${\displaystyle 0'}$停止問題を判定できる標準的なチューリング完全集合。
• このような木には必ず低い基底を持つパスが存在する。これは低基底定理として知られている。
• このような木構造には、超免疫フリーなパスが存在する。これは、そのパスから計算可能な関数は、計算可能な関数によって支配されることを意味する。
• 計算不可能な部分集合の場合${\displaystyle X}$の${\displaystyle \omega }$木には計算されないパスがあります ${\displaystyle X}$。

弱いケーニッヒの補題は、すべての無限二分木には無限の枝が存在することを述べています。これは、2階算術のサブシステム WKL _{0を定義するために使用されます。このサブシステムは}、逆算において重要な役割を果たします。ここで、二分木とは、木内のすべてのシーケンスのすべての項が 0 または 1 である木、つまり定数関数2 によって計算可能に制限されている木を指します。

RCA _{0上では、弱いケーニッヒの補題は証明できないため、RCA 0}に弱いケーニッヒの補題を追加して得られるシステム WKL ₀は厳密に強力です。

WKL _{0上では、ケーニッヒの補題の完全な形式は証明できませんが、より強力な部分系 ACA 0}と同等です。

弱いケーニッヒの補題は、すべての太い無限二分木には無限枝があることを述べている。これをに追加して得られるシステムは WWKL _{0と呼ばれる。その強度は RCA 0}と WKL ₀の間に厳密に存在する。太い無限二分木とは、次のような無限二分木のことである。${\displaystyle \liminf _{n}{\frac {1}{2^{n}}}|\#({\text{レベル }}n のノード数)|>0}$つまり、ツリーをどれだけ深く辿っても、レベルnのノードの割合は下限を下回ることはない。

上記の証明は、各段階で背理法を用いて、無限に多くの他の頂点に到達できる隣接頂点が存在することを立証していること、および選択公理の弱い形式に依存していることから、一般的には構成的とはみなされない。補題の計算上の側面に関する事実から、構成的数学の主要な学派によって構成的とみなされるような証明は存在しないことが示唆される。

LEJ Brouwer ( 1927 )の扇の定理は、古典的な観点から見ると、Kőnig の補題の形式の対偶である。 ${\displaystyle \{0,1\}^{<\omega }}$関数が​${\displaystyle \omega }$セットへ${\displaystyle \{0,1\}}$Sに何らかの初期セグメントが存在する。バーは、すべてのシーケンスがバー内にあるか、バー内にないかのいずれかである場合に分離可能である（この仮定は、通常、排中律が仮定されていない状況で定理が検討されるため必要である）。バーは、ある数が存在する場合に均一である。${\displaystyle N}$そのため、${\displaystyle \omega }$に${\displaystyle \{0,1\}}$バーの最初のセグメントの長さは以下${\displaystyle N}$ブロワーの扇形定理によれば、取り外し可能な棒はすべて均一である。

これは、棒をコンパクトな位相空間の開被覆とみなすことで、古典的な設定で証明できる。${\displaystyle \{0,1\}^{\オメガ }}$バー内の各シーケンスは、この空間の基本開集合を表し、仮定によりこれらの基本開集合は空間を覆います。コンパクト性により、この被覆は有限部分被覆を持ちます。ファン定理のNは、基本開集合が有限部分被覆に含まれる最長のシーケンスの長さとすることができます。この位相的証明は、古典数学において、ケーニッヒの補題の次の形式が成り立つことを示すために使用できます。任意の自然数kに対して、木の任意の無限部分木に対して、${\displaystyle \{0,\ldots ,k\}^{<\omega }}$無限の経路を持つ。

ケーニッヒの補題は選択原理とみなすことができる。上記の最初の証明は、この補題と従属選択公理との関係を示している。帰納の各段階で、特定の性質を持つ頂点を選択しなければならない。少なくとも1つの適切な頂点が存在することは証明されているが、適切な頂点が複数ある場合は、標準的な選択が存在しない可能性がある。実際、従属選択公理の完全な力は必要なく、後述するように、可算選択公理で十分である。

グラフが可算グラフであれば、頂点は整列しており、適切な最小頂点を標準的に選択できます。この場合、ケーニッヒの補題は、算術内包表記を用いた2階算術において証明可能であり、ましてやZF集合論（選択なし）においてはなおさら証明可能です。

ケーニッヒの補題は、本質的には従属選択公理を全体関係に限定したものである。${\displaystyle R}$各${\displaystyle x}$有限個しかない${\displaystyle z}$そのため${\displaystyle xRz}$選択公理は一般に従属選択原理よりも強いが、この従属選択の制限は選択公理の制限と同等である。特に、各ノードでの分岐が可算であると仮定されていない任意の集合の有限部分集合で行われる場合、「すべての無限有限分岐木は無限パスを持つ」というケーニッヒの補題の形式は、すべての可算有限集合集合が選択関数を持つという原理、すなわち有限集合の可算選択公理と同等である。^{[ 4 ]}この選択公理の形式（したがってケーニッヒの補題の形式）は、ZF集合論では証明できない。

集合のカテゴリーにおいて、空でない有限集合の任意の逆系の逆極限は空でない。これはケーニッヒの補題の一般化と見なすことができ、有限集合をコンパクトな離散空間とみなし、コンパクト性の有限交点特性を用いることで、チホノフの定理によって証明できる。

• アロンシャイン木は、補題をより高い濃度に一般化する際に反例が存在する可能性を示唆している。
• PA学位

• ブロウワー、LEJ（1927）、『関数の定義領域について』。van Heijenoort、Jean編で出版。 (1967)、フレーゲからゲーデルへ
• Franchella, Miriam (1997)、「Dénes Königの無限補題の起源について」、Archive for History of Exact Sciences、51 (51(1)3:2-3): 3–27、doi : 10.1007/BF00376449、S2CID 117198918 
• ハワード、ポール、ルービン、ジーン（1998）「選択公理の帰結」、数学概論およびモノグラフ、第 59巻、プロビデンス、ロードアイランド州：アメリカ数学会
• Kőnig, D. (1927)、「Über eine Schlussweise aus dem Endlichen ins Unendliche」、Acta Sci.数学。 (Szeged) (ドイツ語)、3 ( 2–3 ): 121–130 、 2014 年 12 月 23日取得{{citation}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)
• レヴィ、アズリエル（1979）、『基本集合論』、シュプリンガー、ISBN 3-540-08417-7MR 0533962​ 再版、ドーバー、2002年、ISBN 0-486-42079-5。
• ロジャース、ハートリー・ジュニア（1967）、『再帰関数と有効計算可能性の理論』、マグロウヒル、MR 0224462 
• Truss, J. (1976)、「ケーニッヒの補題のいくつかの場合」、Marek, V. Wiktor、Srebrny, Marian、Zarach, Andrzej (編)、『集合論と階層論：アンジェイ・モストフスキへの追悼』、Lecture Notes in Mathematics、第 537巻、Springer、pp. 273–284、doi : 10.1007/BFb0096907、ISBN  978-3-540-07856-2MR 0429557​ 
• クヌース、ドナルド（1968）、『コンピュータプログラミングの技法』第1巻：基本アルゴリズム、382ページ 、ISBN 978-0-201-03801-9

• センザー、ダグラス（1999）「$\displaystyle \Pi _{1}^{0}}$「計算可能性理論におけるクラス」、計算可能性理論ハンドブック、エルゼビア、pp. 37–85、doi : 10.1016/S0049-237X(99)80018-4、ISBN  0-444-89882-4MR 1720779​ 
• Kőnig, D. (1926)、「Sur les communications multivoques des ensembles」(PDF)、Fundamenta Mathematicae (フランス語)、8 (8): 114–134、doi : 10.4064/fm-8-1-114-134
• Kőnig, D. (1936)、Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (ドイツ語)、ライプツィヒ: Akad。フェルラーグ
• シンプソン、スティーブン・G. (1999)、2階算術のサブシステム、数理論理学の展望、シュプリンガー、ISBN 3-540-64882-8MR 1723993​ 
• Soare, Robert I. (1987), Recursively Enumerable Sets and Degrees: A study of computable functions and computably generated sets , Perspectives in Mathematical Logic, Springer, ISBN 3-540-15299-7MR 0882921​ 

• スタンフォード哲学百科事典：構成的数学
• Mizarプロジェクトは、ファイルTREES_2において、ケーニッヒの補題の証明を完全に形式化し、自動的に検証しました。