쾨니그의 정리 (집합론)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

쾨니그의 정리(집합론)는 기수(cardinal number)에 관한 중요한 정리로, 주어진 기수들의 합이 곱보다 작다는 것을 나타낸다. 이 정리는 선택 공리와 동치 관계에 있으며, 칸토어의 정리와 같은 다른 정리들의 증명에 활용된다. 쾨니그의 정리는 기수의 공종도(cofinality)와 관련된 중요한 결과를 도출하며, 이스턴의 정리에 따른 정규 기수에 대한 연속체 함수의 제약을 보여준다. 1904년 헝가리 수학자 쾨니그 줄러에 의해 증명되었다.

쾨니그의 정리 (집합론)

일반 정보

분야	집합론
증명	기수 연산, 선택 공리
이름	쾨니그의 정리

내용

서술	임의의 인덱스 집합 I에 대해, 모든 i ∈ I에 대해 aᵢ와 bᵢ가 기수이고 aᵢ < bᵢ이면, Σ aᵢ < ∏ bᵢ이다.
같이 보기	선택 공리 ZF 기수

인물 정보

명명자	쾨니그 줄러

📚 더 읽어볼만한 페이지

선택 공리 - 초른 보조정리
초른 보조정리는 공집합이 아니고 모든 사슬이 상계를 갖는 부분 순서 집합에서 적어도 하나의 극대 원소가 존재함을 보장하는 정리이다.
선택 공리 - 곱집합
곱집합은 주어진 집합들의 원소들을 순서대로 나열하여 만든 순서쌍 또는 튜플들의 집합이며, 집합론에서 중요한 개념으로 순서쌍, 선택 공리, 함수 및 관계 정의의 기초가 되고, 기수의 곱과 거듭제곱을 정의하며 다양한 수학적 성질을 가진다.
수학기초론 정리 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2<sup>κ</sup> > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.
집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

1. 개요
2. 정의
3. 따름정리
4. 증명
5. 역사

2. 정의

집합 $I$ 및 기수의 집합 $\{\kappa_i\}_{i\in I}$ , $\{\lambda_i\}_{i\in I}$ 가 주어졌고, 모든 $i\in I$ 에 대하여 $\kappa_i<\lambda_i$ 라고 하자. 쾨니그의 정리에 따르면, 다음이 성립한다.

: $\sum_{i\in I}\kappa_i<\prod_{i\in I}\lambda_i$

여기서 '<'는 기수에서 엄격하게 작음을 의미하며, 즉 $A_i$ 에서 $B_i$ 로 가는 단사 함수가 존재하지만, 그 반대 방향으로는 존재하지 않음을 의미한다. 포함된 합집합은 서로소일 필요는 없다(서로소 집합이 아닌 합집합은 서로소 버전보다 클 수 없으며, 이는 선택 공리를 가정한다). 이 공식에서 쾨니그의 정리는 선택 공리와 동치이다.

쾨니그의 정리는 결론의 엄격한 부등식 때문에 주목할 만하다. 무한한 기수의 합과 곱의 산술에 대한 많은 쉬운 규칙들이 있으며, 여기서 약한 부등식(≤)만 결론 내릴 수 있다. 예를 들어, 모든 i ∈ I에 대해 $m_i < n_i$ 이면, 다음과 같은 결론만 내릴 수 있다.

: $\sum_{i \in I} m_i \le \sum_{i \in I} n_i$

예를 들어, 인덱스 집합 I가 자연수일 때, $m_i = 1$ 및 $n_i = 2$ 로 설정하면 양변에 대해 합 $\aleph_0$ 가 나오며, 등식이 성립한다.

3. 따름정리

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

* I가 집합이고, 모든 i ∈ I에 대해 A_i와 B_i가 집합이며, 모든 i ∈ I에 대해 $A_i 이면,$

: $\sum_{i \in I}A_i < \prod_{i \in I}B_i$

여기서 <는 기수에서 엄격하게 작음을 의미하며, 즉 A_i에서 B_i로 가는 단사 함수가 존재하지만, 그 반대 방향으로는 존재하지 않음을 의미한다. 포함된 합집합은 서로소일 필요는 없다(서로소 집합이 아닌 합집합은 서로소 버전보다 클 수 없으며, 이는 선택 공리를 가정한다).

(물론, 쾨니그의 정리는 기수 m_i와 n_i가 유한이고 인덱스 집합 I가 유한하면 자명하다. I가 공집합이면, 왼쪽 합은 빈 합이므로 0이고, 오른쪽 곱은 빈 곱이므로 1이다.)

쾨니그의 정리는 결론의 엄격한 부등식 때문에 주목할 만하다. 무한한 기수의 합과 곱의 산술에 대한 많은 쉬운 규칙들이 있으며, 여기서 약한 부등식 ≤만 결론 내릴 수 있다. 예를 들어, 모든 i ∈ I에 대해 $m_i < n_i$ 이면, 다음과 같은 결론만 내릴 수 있다.

: $\sum_{i \in I} m_i \le \sum_{i \in I} n_i$

예를 들어, 인덱스 집합 I가 자연수일 때, $m_i = 1$ 및 $n_i = 2$ 로 설정하면 양변에 대해 합 $\aleph_0$ 가 나오며, 등식이 성립한다.

3.1. 칸토어의 정리

$\kappa_i=1$ 이며 $\lambda_i=2$ 라고 하면, 다음과 같다.
: $|I|<2^$

👆

좌우로 밀어서 보기

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

\kappa

가 기수라면,

\kappa < 2^\kappa

이다. 각

i

에 대해

m_i=1

와

n_i=2

를

\kappa

로 잡으면, 위 부등식의 좌변은

\kappa

가 되고, 우변은

2^\kappa

가 되는데, 이는

\kappa

에서

\{0,1\}

로 가는 함수의 기수, 즉

\kappa

의 멱집합의 기수이다. 따라서 쾨니그의 정리는 칸토어의 정리의 또 다른 증명을 제공한다. (역사적으로 칸토어의 정리가 훨씬 일찍 증명되었다.)

3.2. 선택 공리

$\kappa_i=0$ 이고, $\lambda_i$ 가 임의의 0이 아닌 기수라고 할 때, 다음이 성립한다.

: $0<\prod_{i\in I}\lambda_i$

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

쾨니그의 정리는 선택 공리와 동치이다. 선택 공리를 명시하는 한 가지 방법은 "공집합이 아닌 집합들의 임의의 데카르트 곱은 공집합이 아니다"이다. 각 i ∈ I에 대해 B_i를 공집합이 아닌 집합이라고 하고, 각 i ∈ I에 대해 A_i = {}라고 하면, 쾨니그의 정리에 의해 다음이 성립한다.

* 만약 $\forall i \in I(\{\} < B_i)$ 이면, $\{\} < \prod_{i \in I}B_i$ 이다.

즉, 주어진 공집합이 아닌 집합 B_i들의 데카르트 곱은 공집합들의 합보다 더 큰 기수를 갖는다. 따라서 공집합이 아니며, 이는 선택 공리가 말하는 바와 같다. 선택 공리는 쾨니그의 정리로부터 유도되므로, 이 정리의 결과에 대해 논의할 때 우리는 선택 공리를 자유롭고 암묵적으로 사용한다.

3.3. 공종도의 지수

$I$ 가 무한 기수 $\mu\ge\aleph_0$ 의 공종 집합이라고 할 때, $\mu<\mu^{\operatorname{cf}\mu}\stackrel{\text{def}}=\gimel(\mu)$ 가 성립한다. 여기서 $\gimel(\mu)$ 는 기멜 함수이다.

쾨니그의 정리는 기수의 공종도에 중요한 영향을 미친다.

* $\kappa \ge \aleph_0$ 이면, $\kappa < \kappa^{\operatorname{cf}(\kappa)}$ 이다.

κ가 정규 기수라면, 이 명제는 칸토어의 정리에서 바로 유도된다. κ가 특이 기수라면, κ는 극한 기수이다. κ에 접근하는 엄격히 증가하는 cf(κ)-수열 기수를 선택하고, λ를 그들의 합으로 놓는다. 쾨니그의 정리에 의해, λ는 κ의 cf(κ)개 복사본의 곱보다 작다. 각 합은 λ의 하한이므로 λ ≥ κ이다. 또한, λ ≤ cf(κ)·κ = κ이므로, λ = κ임을 보일 수 있다.

이스턴의 정리에 따르면, 다음 결과는 정규 기수에 대한 연속체 함수에 대한 유일한 비자명 제약이다.

* $\kappa \geq \aleph_0$ 이고 $\lambda \geq 2$ 이면, $\kappa < \operatorname{cf}(\lambda^\kappa)$ 이다.

$\mu = \lambda^\kappa$ 라고 가정하고, $\kappa \ge \operatorname{cf}(\mu)$ 라고 가정하면, $\mu < \mu^{\operatorname{cf}(\mu)} \le \mu^\kappa = (\lambda^\kappa)^\kappa = \lambda^{\kappa \cdot \kappa} = \lambda^\kappa = \mu$ 가 되어 모순이 발생한다.

3.4. 공종도의 하한

어떤 무한 기수 $\kappa\ge\aleph_0$ 와 기수 $\lambda\ge2$ 에 대하여, 다음이 항상 성립한다.

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

이는 다음과 같이 증명할 수 있다. 이미 증명된 따름정리에 따라
: $\left(\lambda^\kappa\right)^\kappa=\lambda^\kappa<\left(\lambda^\kappa\right)^{\operatorname{cf}(\lambda^\kappa)}$
이므로, 기수 거듭제곱의 단조성에 따라서
: $\kappa<\operatorname{cf}(\lambda^\kappa)$
이다.

이스턴의 정리에 따르면, 쾨니그의 정리의 다음 결과는 정규 기수에 대한 연속체 함수에 대한 유일한 비자명 제약이다.

* 만약 $\kappa \geq \aleph_0$ 이고 $\lambda \geq 2$ 이면, $\kappa < \operatorname{cf}(\lambda^\kappa)$ 이다.

$\mu = \lambda^\kappa$ 라고 하자. 이 따름정리에 반하여, $\kappa \ge \operatorname{cf}(\mu)$ 라고 가정한다. 그러면 이전 따름정리를 사용하여, $\mu < \mu^{\operatorname{cf}(\mu)} \le \mu^\kappa = (\lambda^\kappa)^\kappa = \lambda^{\kappa \cdot \kappa} = \lambda^\kappa = \mu$ 가 되어 모순이 발생한다.

4. 증명

집합족 $\{A_i\}_{i\in I}$ 와 $\{B_i\}_{i\in I}$ 가 주어졌고, 임의의 $i\in I$ 에 대하여 전사 함수
: $A_i\twoheadrightarrow B_i$
가 존재하지 않는다고 가정한다. 임의의 함수
: $f\colon\bigsqcup_{i\in I}A_i\twoheadrightarrow\prod_{i\in I}B_i$
가 주어졌을 때, $f$ 가 전사 함수가 아님을 보이면 충분하다.

사영 함수
: $\sigma_i\colon A_i\hookrightarrow\bigsqcup_{i\in I}A_i$
: $\pi_i\colon\prod_{i\in I}B_i\twoheadrightarrow B_i$
를 정의하여,
: $f_i=\pi_i\circ f\circ\sigma_i\colon A_i\to B_i$
를 생각한다. 가정에 따라, 이 함수는 전사 함수가 아니므로,
: $b_i\in B_i\setminus f_i(A_i)$
를 선택할 수 있다. 그렇다면
: $(b_i)_{i\in I}\in\prod_{i\in I}B_i\setminus f\left(\bigsqcup_{i\in I}A_i\right)$
이므로, $f$ 는 전사 함수가 아니다.

체르멜로-프렝켈 집합론(특히 선택 공리를 포함)을 가정하면, 이 정리를 증명할 수 있다. $\forall i\in I\quad A_i 를 가지고 있으며, \sum_{i\in I}A_i<\prod_{i\in I}B_i 임을 보이고자 한다.$

선택 공리는 A < B라는 조건이, A에서 B로의 전사 함수가 없고, B가 공집합이 아니라는 조건과 동치임을 의미한다.

따라서, A_i에서 B_i≠{}로의 함수가 없다는 것을 알고 있으며, A들의 분리합집합에서 B들의 곱으로 가는 임의의 함수 f가 전사적이지 않으며, 곱이 공집합이 아님을 보여야 한다. 곱이 공집합이 아니라는 것은 선택 공리와 인자들이 공집합이 아니라는 사실로부터 바로 따라 나온다. 각 i에 대해, f와 B_i로의 투영의 합성 아래에서 A_i의 이미지에 없는 B_i 안의 b_i를 선택한다. 그러면 요소 b_i들의 곱은 f의 이미지에 없으므로, f는 A들의 분리합집합을 B들의 곱으로 사상하지 않는다.

칸토어의 대각선 논법과 유사한 논증을 통해, 합에서 곱으로의 함수 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는 전사 함수가 아니다.

따라서, 곱의 농도는 합의 농도보다 진정으로 크다.

5. 역사

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

분야	집합론
증명	기수 연산, 선택 공리
이름	쾨니그의 정리

내용

서술	임의의 인덱스 집합 I에 대해, 모든 i ∈ I에 대해 aᵢ와 bᵢ가 기수이고 aᵢ < bᵢ이면, Σ aᵢ < ∏ bᵢ이다.
같이 보기	선택 공리 ZF 기수

인물 정보

명명자	쾨니그 줄러