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

集合論において、ケーニヒの定理（ケーニヒのていり） とは選択公理の下で成り立つ命題で、 I が集合で、全ての I の要素 i について mi と ni は それぞれ基数であり、 m i < n i {\displaystyle m_{i}<n_{i}\!} であるなら ∑ i ∈ I m i < ∏ i ∈ I n i . {\displaystyle \sum _{i\in I}m_{i}<\prod _{i\in I}n_{i}.} となる。というものである。 ここでの 和 は集合mi達の直和の濃度で、 積 は直積の濃度である。 しかしながら、選択公理を仮定しない場合は、この和と積は基数として定義できないので、 その場合にこの定理を考慮するにはこの不等式の意味は明らかにされる必要がある。 定理の正確な内容は以下のようになる: I を集合 ,その任意の要素 i に対して Ai と Bi を 集合で、 A i < B i {\displaystyle A_{i}<B_{i}\!} であるものとすると、 ∑ i ∈ I A i < ∏ i ∈ I B i , {\displaystyle \sum _{i\in I}A_{i}<\prod _{i\in I}B_{i},} となる。ここで < は 基数の意味で真に小さい ことを意味する。 言い換えると、Ai から Biへの単射があるが、逆方向には単射がない。 この和は直和でなくてもよい(選択公理の有無に関わらず、単なる集合和は直和より決して大きくはならない)。 ここでのケーニヒの定理は選択公理と同値である。 (もちろん、ケーニヒの定理は添え字集合 I が無限でmi と niが有限基数なら自明である。 I が空集合なら、左辺の和は0になり、右辺の積は1となる。) ケーニヒの定理は結論が狭義の不等式になっていることが注目すべき点である。 基数の無限和と無限積の演算に関する広義不等号 ≤ を結論に持つ簡単なルールはたくさんある。 例えば、I の要素 i に対して m i < n i {\displaystyle m_{i}<n_{i}\!} ならば、 ∑ i ∈ I m i ≤ ∑ i ∈ I n i {\displaystyle \sum _{i\in I}m_{i}\leq \sum _{i\in I}n_{i}} とまでしか言えない。例として、 m i = 1 {\displaystyle m_{i}=1} & n i = 2 {\displaystyle n_{i}=2} で添え字集合 I は自然数全体とすれば 両辺の和は ℵ 0 {\displaystyle \aleph _{0}} となり、等号が成立することになる。 κ {\displaystyle \kappa \,} が基数なら κ < 2 κ . {\displaystyle \kappa <2^{\kappa }.\!} κの要素iに対してmi = 1,ni = 2とすると、 ケーニヒの定理の不等式の左辺はちょうどκになり、 右辺はκから{0,1}への関数全体の集合の濃度である2κとなる。 これはκの冪集合の濃度であり、ケーニヒの定理はカントールの定理の別証明を与える。 (歴史的にはカントールの定理の方が先に証明されている。) 選択公理は"任意の空でない集合の直積は空でない"という命題とも言える。 I の要素i に対し Biを空でない集合、Ai = {}とする。 ケーニヒの定理から、: ∀ i ∈ I ( { } < B i ) {\displaystyle \forall i\in I(\{\}<B_{i})} ならば { } < ∏ i ∈ I B i . {\displaystyle \{\}<\prod _{i\in I}B_{i}.} となる。すなわち、与えられた空でない集合Biの直積は空集合の和より大きい濃度を持ち、空でないから、これは選択公理の主張に他ならない。 つまり、ケーニヒの定理から選択公理が導かれる。ケーニヒの定理からの帰結について議論するときは暗黙の内に、選択公理を仮定することになる。 ケーニヒの定理は基数の共終数に関する重要な帰結も持つ。 κ ≥ ℵ 0 {\displaystyle \kappa \geq \aleph _{0}} ならば κ < κ c f ( κ ) . {\displaystyle \kappa <\kappa ^{cf(\kappa )}.\!} κに到達する基数の狭義増加なcf(κ)-列をとる この列の要素はどれもκ未満であり、 それらの和はκで、積はκのcf(κ)個のコピーの直積である。 イーストンの定理によると、次の帰結は正則基数のcontinuum functionに対する唯一の非自明な制限である。 κ ≥ ℵ 0 {\displaystyle \kappa \geq \aleph _{0}} かつ λ ≥ 2 {\displaystyle \lambda \geq 2} ならば κ < c f ( λ κ ) . {\displaystyle \kappa <cf(\lambda ^{\kappa }).\!} μ = λ κ {\displaystyle \mu =\lambda ^{\kappa }\!} としよう。 この系の結論に反して、 κ ≥ c f ( μ ) {\displaystyle \kappa \geq cf(\mu )} であったとしよう。 先に挙げた系により、 μ < μ c f ( μ ) ≤ μ κ = ( λ κ ) κ = λ κ ⋅ κ = λ κ = μ {\displaystyle \mu <\mu ^{cf(\mu )}\leq \mu ^{\kappa }=(\lambda ^{\kappa })^{\kappa }=\lambda ^{\kappa \cdot \kappa }=\lambda ^{\kappa }=\mu } となり、これは矛盾である。よって、この系の結論は成立しなければならない。 ZFC公理系を仮定して証明する。 ∀ i ∈ I A i < B i {\displaystyle \forall i\in I\quad A_{i}<B_{i}} が与えられたとして ∑ i ∈ I A i < ∏ i ∈ I B i {\displaystyle \sum _{i\in I}A_{i}<\prod _{i\in I}B_{i}} を示す。 最初に、和から積への単射があることを証明する。選択公理により、 全ての i について Ai から Bi への 単射 fi を選ぶ。 ここで、 fi は全射にはならない。 なので、各 i に対して fi の値域の外にある Bi の要素が存在する。 それらを xi として、選択公理を再度用いて取り出す。和の上の関数 g を j = i で a が Ai の要素なら g ( i,a ) ( j ) = fi ( a ) かつ j ≠ i で a が Ai の要素なら g ( i,a ) ( j ) = xj とすることによって定義する。 各 i に対して fi(a) ≠ xi であるので、 g は和から積への単射である。 次に、和から積への関数 f が全射ではないことを示す。 関数 f に対し、カントールの対角線論法と同様の議論によって f の値になりえない 積の要素 e を構成する。I の各要素 i に対し、 Ai から Bi への関数 fi を fi ( a ) = (f ( a )) ( i ) で定義する。 仮定により fi は Ai から Bi への全射ではないので、I の各要素 i に対して、Bi の要素で fi の像に入らないものがある。 選択公理により、B の要素 e であって e ( i ) が fi の値にならないものが存在する。 もし f が全射ならば、ある Ai と Ai の要素 c があり f ( c ) = e を満たす。 しかし、fi ( c ) = e ( i ) となるので、これは e ( i ) の取り方に矛盾する。よって f は全射ではない。 よって、積の濃度は和の濃度より真に大きい。