ケーニヒの定理 (集合論)

集合論において、ケーニヒの定理 (ハンガリー人数学者 Gyula Kőnig に由来する。ケーニヒはJulius Königの名前で発表していた。) とは選択公理の下で成り立つ命題で、 I が集合で、全ての I の要素 i について m_i と n_i は それぞれ基数であり、[math]m_i \lt n_i \![/math]であるなら

[math]\sum_{i\in I}m_i\lt \prod_{i\in I}n_i.[/math]

となる。というものである。

ここでの 和 は集合m_i達の直和の濃度で、 積 は直積の濃度である。 しかしながら、選択公理を仮定しない場合は、この和と積は基数として定義できないので、 その場合にこの定理を考慮するにはこの不等式の意味は明らかにされる必要がある。

詳細

定理の正確な内容は以下のようになる: I を集合 ,その任意の要素 i に対して A_i と B_i を 集合で、[math]A_i\lt B_i\![/math]であるものとすると、

[math]\sum_{i\in I}A_i\lt \prod_{i\in I}B_i,[/math]

となる。ここで < は 基数の意味で真に小さい ことを意味する。 言い換えると、A_i から B_iへの単射があるが、逆方向には単射がない。 この和は直和でなくてもよい(選択公理の有無に関わらず、単なる集合和は直和より決して大きくはならない)。 ここでのケーニヒの定理は選択公理と同値である。

(もちろん、ケーニヒの定理は添え字集合 I が無限でm_i と n_iが有限基数なら自明である。 I が空集合なら、左辺の和は0になり、右辺の積は1となる。)

ケーニヒの定理は結論が狭義の不等式になっていることが注目すべき点である。 基数の無限和と無限積の演算に関する広義不等号 ≤ を結論に持つ簡単なルールはたくさんある。 例えば、I の要素 i に対して[math]m_i \lt n_i \![/math]ならば、

[math]\sum_{i\in I} m_i \le \sum_{i\in I} n_i [/math]

とまでしか言えない。例として、[math]m_i = 1 [/math] & [math]n_i = 2[/math]で添え字集合 I は自然数全体とすれば 両辺の和は[math]\aleph_0[/math]となり、等号が成立することになる。

ケーニヒの定理の系

• [math]\kappa\,[/math] が基数なら [math]\kappa \lt 2^{\kappa}.\![/math]

κの要素iに対してm_i = 1,n_i = 2とすると、 ケーニヒの定理の不等式の左辺はちょうどκになり、 右辺はκから{0,1}への関数全体の集合の濃度である2^κとなる。 これはκの冪集合の濃度であり、ケーニヒの定理はカントールの定理の別証明を与える。 (歴史的にはカントールの定理の方が先に証明されている。)

選択公理

選択公理は"任意の空でない集合の直積は空でない"という命題とも言える。 I の要素i に対し B_iを空でない集合、A_i = {}とする。 ケーニヒの定理から、:

• [math]\forall i\in I(\{\}\lt B_i)[/math]ならば[math]\{\}\lt \prod_{i\in I}B_i.[/math]

となる。すなわち、与えられた空でない集合B_iの直積は空集合の和より大きい濃度を持ち、空でないから、これは選択公理の主張に他ならない。 つまり、ケーニヒの定理から選択公理が導かれる。ケーニヒの定理からの帰結について議論するときは暗黙の内に、選択公理を仮定することになる。

ケーニヒの定理と共終数

ケーニヒの定理は基数の共終数に関する重要な帰結も持つ。

• [math]\kappa\ge\aleph_0[/math]ならば[math]\kappa\lt \kappa^{cf(\kappa)}. \![/math]

κに到達する基数の狭義増加なcf(κ)-列をとる この列の要素はどれもκ未満であり、 それらの和はκで、積はκのcf(κ)個のコピーの直積である。

イーストンの定理によると、次の帰結は正則基数のcontinuum functionに対する唯一の非自明な制限である。

• [math]\kappa\geq\aleph_0[/math] かつ [math]\lambda\geq 2[/math] ならば [math]\kappa\lt cf(\lambda^\kappa).\![/math]

[math]\mu = \lambda^\kappa \![/math]としよう。 この系の結論に反して、[math]\kappa \ge cf(\mu)[/math]であったとしよう。 先に挙げた系により、[math]\mu\lt \mu^{cf(\mu)}\le\mu^{\kappa}=(\lambda^\kappa)^\kappa=\lambda^{\kappa\cdot\kappa}=\lambda^\kappa=\mu[/math]となり、これは矛盾である。よって、この系の結論は成立しなければならない。

ケーニヒの定理の証明

ZFC公理系を仮定して証明する。 [math]\forall i\in I\quad A_i\lt B_i[/math] が与えられたとして [math]\sum_{i\in I}A_i\lt \prod_{i\in I}B_i[/math] を示す。

最初に、和から積への単射があることを証明する。選択公理により、 全ての i について A_i から B_i への 単射 f_i を選ぶ。 ここで、 f_i は全射にはならない。 なので、各 i に対して f_i の値域の外にある B_i の要素が存在する。 それらを x_i として、選択公理を再度用いて取り出す。和の上の関数 g を j = i で a が A_i の要素なら g ( i,a ) ( j ) = f_i ( a ) かつ j ≠ i で a が A_i の要素なら g ( i,a ) ( j ) = x_j とすることによって定義する。 各 i に対して f_i(a) ≠ x_i であるので、 g は和から積への単射である。

次に、和から積への関数 f が全射ではないことを示す。 関数 f に対し、カントールの対角線論法と同様の議論によって f の値になりえない 積の要素 e を構成する。I の各要素 i に対し、 A_i から B_i への関数 f_i を f_i ( a ) = (f ( a )) ( i ) で定義する。 仮定により f_i は A_i から B_i への全射ではないので、I の各要素 i に対して、B_i の要素で f_i の像に入らないものがある。 選択公理により、B の要素 e であって e ( i ) が f_i の値にならないものが存在する。 もし f が全射ならば、ある A_i と A_i の要素 c があり f ( c ) = e を満たす。 しかし、f_i ( c ) = e ( i ) となるので、これは e ( i ) の取り方に矛盾する。よって f は全射ではない。 よって、積の濃度は和の濃度より真に大きい。

参考

• M. Holz, K. Steffens and E. Weitz (1999). Introduction to Cardinal Arithmetic. Birkhäuser. ISBN 3764361247. 

関連項目

• 選択公理

外部リンク

• König's theorem article on PlanetMath, includes a proof