쾨니그의 정리 (집합론)

집합론에서 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 일련의 기수의 순부등식에서, 작은 쪽의 합을 취하고, 큰 쪽의 곱을 취해도 여전히 순부등식이 성립한다는 정리다.

정의

집합 ${\displaystyle I}$ 및 기수의 집합 ${\displaystyle \{\kappa _{i}\}_{i\in I}}$, ${\displaystyle \{\lambda _{i}\}_{i\in I}}$가 주어졌고, 또한 모든 ${\displaystyle i\in I}$에 대하여

${\displaystyle \kappa _{i}<\lambda _{i}}$

라고 하자. 쾨니그의 정리에 따르면, 다음이 성립한다.

${\displaystyle \sum _{i\in I}\kappa _{i}<\prod _{i\in I}\lambda _{i}}$

따름정리

쾨니그의 정리는 다음과 같은 따름정리들을 갖는다.

칸토어의 정리

 이 부분의 본문은 칸토어의 정리입니다.

${\displaystyle \kappa _{i}=1}$이며 ${\displaystyle \lambda _{i}=2}$라고 하자. 그렇다면

${\displaystyle |I|<2^{|I|}}$

이다. 이는 칸토어의 정리다.

선택 공리

 이 부분의 본문은 선택 공리입니다.

${\displaystyle \kappa _{i}=0}$이고, ${\displaystyle \lambda _{i}}$가 임의의 0이 아닌 기수라고 하자. 그렇다면

${\displaystyle 0<\prod _{i\in I}\lambda _{i}}$

이다. 이는 선택 공리의 한 형태이다.

공종도의 지수

${\displaystyle I}$가 어떤 무한 기수 ${\displaystyle \mu \geq \aleph _{0}}$의 (최소) 공종 집합이라고 하자. 즉, 이는 순서수들의 집합이다. 또한, ${\displaystyle \kappa _{i}=|i|}$로 놓고, ${\displaystyle \lambda _{i}=\mu }$라고 하자. 그렇다면

${\displaystyle \mu =\left|\bigcup _{i\in I}i\right|\leq \sum _{i\in I}|i|<\mu ^{|I|}=\mu ^{\operatorname {cf} \mu }}$

이다. 즉, 무한 기수 ${\displaystyle \mu }$에 대하여

${\displaystyle \mu <\mu ^{\operatorname {cf} \mu }{\stackrel {\text{def}}{=}}\gimel (\mu )}$

이다. 여기서 ${\displaystyle \gimel (\mu )}$를 기멜 함수라고 한다.

공종도의 하한

어떤 무한 기수 ${\displaystyle \kappa \geq \aleph _{0}}$와 기수 ${\displaystyle \lambda \geq 2}$에 대하여, 항상

${\displaystyle \kappa <\operatorname {cf} (\lambda ^{\kappa })}$

이다.

증명은 다음과 같다. 이미 증명된 따름정리에 따라

${\displaystyle \left(\lambda ^{\kappa }\right)^{\kappa }=\lambda ^{\kappa }<\left(\lambda ^{\kappa }\right)^{\operatorname {cf} (\lambda ^{\kappa })}}$

이므로, 기수 거듭제곱의 단조성에 따라서

${\displaystyle \kappa <\operatorname {cf} (\lambda ^{\kappa })}$

이다.

증명

집합족 ${\displaystyle \{A_{i}\}_{i\in I}}$와 ${\displaystyle \{B_{i}\}_{i\in I}}$가 주어졌고, 임의의 ${\displaystyle i\in I}$에 대하여 전사 함수

${\displaystyle A_{i}\twoheadrightarrow B_{i}}$

가 존재하지 않는다고 하자. 임의의 함수

${\displaystyle f\colon \bigsqcup _{i\in I}A_{i}\twoheadrightarrow \prod _{i\in I}B_{i}}$

가 주어졌다고 하자. 그렇다면 ${\displaystyle f}$가 전사 함수가 아님을 보이면 족하다.

사영 함수

${\displaystyle \sigma _{i}\colon A_{i}\hookrightarrow \bigsqcup _{i\in I}A_{i}}$

${\displaystyle \pi _{i}\colon \prod _{i\in I}B_{i}\twoheadrightarrow B_{i}}$

를 정의하여,

${\displaystyle f_{i}=\pi _{i}\circ f\circ \sigma _{i}\colon A_{i}\to B_{i}}$

를 생각하자. 가정에 따라, 이 함수는 전사 함수가 아니므로,

${\displaystyle b_{i}\in B_{i}\setminus f_{i}(A_{i})}$

를 고르자. 그렇다면

${\displaystyle (b_{i})_{i\in I}\in \prod _{i\in I}B_{i}\setminus f\left(\bigsqcup _{i\in I}A_{i}\right)}$

이므로, ${\displaystyle f}$는 전사 함수가 아니다.

역사

헝가리의 수학자 쾨니그 줄러가 1904년에 증명하였다.^[1][2]