選択公理との関連
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/06/16 07:25 UTC 版)
ケーニヒの補題は選択の原理であるとも言える。上述の一つめの証明はこの補題とdependent choice の公理(en)との関係を表している。帰納法の各ステップにおいて、ある特別な性質を持った点を選ばなければならない。そのような性質を満たす点が少なくとも一つ存在することが証明されているが、もし適切な点が一つよりも多く存在するときは、その内の一つを canonical に選択する方法はない。 グラフが可算であるなら、点は整列集合を成し、適切な点のうち最小のものを canonical に選ぶことができる。この場合、ケーニヒの補題は二階算術(en)の算術的内包公理 ACA 0 {\displaystyle {\mbox{ACA}}_{0}\,} を使って証明できる。ZF集合論を用いるなら尚更のことである（選択公理は不要）。 ケーニヒの補題は本質的に、dependent choice の公理を、各 x に対して xRz となる z が有限個しか存在しないような entire relation R に制限するものである。選択公理は一般には dependent choice の原理より強いが、この dependent choice の制限と選択公理の制限は同じものになる。特に各点が、可算とは限らない任意の集合の有限部分集合上で分岐する場合、ケーニヒの補題の言う"有限分岐する無限木は無限パスをもつ" は、有限集合の可算集合は全て選択関数を持つという原理と同値になる(Truss (1976:273); Levy (1979, Exercise IX.2.18)と比較せよ)。この形の選択公理は（すなわちケーニヒの補題も）ZFの下では証明できない。
※この「選択公理との関連」の解説は、「ケーニヒの補題」の解説の一部です。
「選択公理との関連」を含む「ケーニヒの補題」の記事については、「ケーニヒの補題」の概要を参照ください。
- 選択公理との関連のページへのリンク
