집합론 에서, 칸토어-베른슈타인 정리 (영어 : Cantor–Bernstein theorem ) 또는 슈뢰더-베른슈타인 정리 (영어 : Schröder–Bernstein theorem )는 두 집합 사이에 두 방향으로 모두 단사 함수 가 존재한다면, 두 집합 사이에 일대일 대응 이 존재한다는 정리이다. 체르멜로-프렝켈 집합론 에서 선택 공리 를 사용하지 않고 증명할 수 있다. 칸토어-베른슈타인 정리에 따라, 기수 의 표준적인 순서는 부분 순서 이다. 선택 공리 를 추가로 가정하면, 기수의 순서가 전순서 임을 보일 수 있다.
칸토어-베른슈타인 정리의 최초의 서술
칸토어-베른슈타인 정리 는 다음과 같다.[1] :28, Theorem 3.2
두 집합
X
{\displaystyle X}
Y
{\displaystyle Y}
단사 함수
f
:
X
→
Y
{\displaystyle f\colon X\to Y}
g
:
Y
→
X
{\displaystyle g\colon Y\to X}
전단사 함수
h
:
X
→
Y
{\displaystyle h\colon X\to Y}
이는 선택 공리 없이 증명할 수 있다.
기수 는 같은 수의 원소를 포함하는 집합들을 묶은 동치류 로 여길 수 있다. 구체적으로, 만약 전단사 함수
X
→
Y
{\displaystyle X\to Y}
|
X
|
=
|
Y
|
{\displaystyle |X|=|Y|}
|
X
|
{\displaystyle |X|}
X
{\displaystyle X}
크기 를 나타내는 기수 ). 만약 단사 함수
X
→
Y
{\displaystyle X\to Y}
|
X
|
≤
|
Y
|
{\displaystyle |X|\leq |Y|}
≤
{\displaystyle \leq }
반사 관계 이며 (항등 함수 는 단사 함수), 추이적 관계 이다 (단사 함수의 합성 은 단사 함수). 칸토어-베른슈타인 정리는 다음과 같이 적을 수 있다.
만약
|
X
|
≤
|
Y
|
{\displaystyle |X|\leq |Y|}
|
Y
|
≤
|
X
|
{\displaystyle |Y|\leq |X|}
|
X
|
=
|
Y
|
{\displaystyle |X|=|Y|}
즉, 기수의 순서는 반대칭 관계 이며, 따라서 부분 순서 이다.
정렬 집합 들 사이에서는 항상 크기를 비교할 수 있다. 선택 공리 를 가정하면, 모든 집합 은 정렬 집합 과 크기가 같으므로, 모든 집합들의 크기는 비교 가능하다. 즉, 기수의 순서는 전순서 이다.
같은 맥락의 여러 증명들이 존재한다.
다음과 같이 정의하자.[1] :28, Theorem 3.2
X
0
=
X
{\displaystyle X_{0}=X}
Y
0
=
g
(
Y
)
{\displaystyle Y_{0}=g(Y)}
X
n
+
1
=
g
(
f
(
X
n
)
)
{\displaystyle X_{n+1}=g(f(X_{n}))}
Y
n
+
1
=
g
(
f
(
Y
n
)
)
{\displaystyle Y_{n+1}=g(f(Y_{n}))}
그러면 일련의
X
{\displaystyle X}
부분 집합 들
X
0
⊇
Y
0
⊇
X
1
⊇
Y
1
⊇
X
2
⊇
Y
2
⊇
⋯
{\displaystyle X_{0}\supseteq Y_{0}\supseteq X_{1}\supseteq Y_{1}\supseteq X_{2}\supseteq Y_{2}\supseteq \cdots }
을 얻는다. (자명하게
X
0
⊇
Y
0
{\displaystyle X_{0}\supseteq Y_{0}}
Y
⊇
f
(
X
)
{\displaystyle Y\supseteq f(X)}
Y
0
⊇
X
1
{\displaystyle Y_{0}\supseteq X_{1}}
X
n
⊇
Y
n
⊇
X
n
+
1
{\displaystyle X_{n}\supseteq Y_{n}\supseteq X_{n+1}}
g
∘
f
{\displaystyle g\circ f}
상 을 씌우면
X
n
+
1
⊇
Y
n
+
1
⊇
X
n
+
2
{\displaystyle X_{n+1}\supseteq Y_{n+1}\supseteq X_{n+2}}
h
:
X
→
Y
{\displaystyle h\colon X\to Y}
h
(
x
)
=
{
f
(
x
)
∃
n
=
0
,
1
,
…
:
x
∈
X
n
∖
Y
n
g
−
1
(
x
)
∄
n
=
0
,
1
,
…
:
x
∈
X
n
∖
Y
n
{\displaystyle h(x)={\begin{cases}f(x)&\exists n=0,1,\dots \colon x\in X_{n}\setminus Y_{n}\\g^{-1}(x)&\not \exists n=0,1,\dots \colon x\in X_{n}\setminus Y_{n}\end{cases}}}
(
g
{\displaystyle g}
전단사 함수 일 필요가 없으므로 역함수 를 가질 필요가 없지만, 공역 을 제한하여 부분적인 역함수
g
−
1
:
g
(
Y
)
→
Y
{\displaystyle g^{-1}\colon g(Y)\to Y}
h
{\displaystyle h}
단사 함수 이자 전사 함수 임을 보이면 충분하다.
h
{\displaystyle h}
h
{\displaystyle h}
(
X
0
∖
Y
0
)
∪
(
X
1
∖
Y
1
)
∪
⋯
{\displaystyle (X_{0}\setminus Y_{0})\cup (X_{1}\setminus Y_{1})\cup \cdots }
f
{\displaystyle f}
여집합
(
Y
0
∖
X
1
)
∪
(
Y
1
∖
X
2
)
∪
⋯
{\displaystyle (Y_{0}\setminus X_{1})\cup (Y_{1}\setminus X_{2})\cup \cdots }
g
−
1
{\displaystyle g^{-1}}
f
{\displaystyle f}
g
−
1
{\displaystyle g^{-1}}
(
X
0
∖
Y
0
)
∪
(
X
1
∖
Y
1
)
∪
⋯
{\displaystyle (X_{0}\setminus Y_{0})\cup (X_{1}\setminus Y_{1})\cup \cdots }
(
Y
0
∖
X
1
)
∪
(
Y
1
∖
X
2
)
∪
⋯
{\displaystyle (Y_{0}\setminus X_{1})\cup (Y_{1}\setminus X_{2})\cup \cdots }
h
{\displaystyle h}
g
∘
h
{\displaystyle g\circ h}
X
n
∖
Y
n
{\displaystyle X_{n}\setminus Y_{n}}
X
n
+
1
∖
Y
n
+
1
{\displaystyle X_{n+1}\setminus Y_{n+1}}
Y
n
∖
X
n
+
1
{\displaystyle Y_{n}\setminus X_{n+1}}
Y
n
∖
X
n
+
1
{\displaystyle Y_{n}\setminus X_{n+1}}
X
n
+
1
∖
Y
n
+
1
{\displaystyle X_{n+1}\setminus Y_{n+1}}
Y
n
∖
X
n
+
1
{\displaystyle Y_{n}\setminus X_{n+1}}
(
X
0
∖
Y
0
)
∪
(
X
1
∖
Y
1
)
∪
⋯
{\displaystyle (X_{0}\setminus Y_{0})\cup (X_{1}\setminus Y_{1})\cup \cdots }
(
Y
0
∖
X
1
)
∪
(
Y
1
∖
X
2
)
∪
⋯
{\displaystyle (Y_{0}\setminus X_{1})\cup (Y_{1}\setminus X_{2})\cup \cdots }
h
{\displaystyle h}
h
{\displaystyle h}
y
∈
Y
{\displaystyle y\in Y}
g
(
y
)
∈
X
n
∖
Y
n
{\displaystyle g(y)\in X_{n}\setminus Y_{n}}
n
>
0
{\displaystyle n>0}
∵
g
(
y
)
∈
g
(
Y
)
=
Y
0
{\displaystyle \because g(y)\in g(Y)=Y_{0}}
X
n
=
g
(
f
(
X
n
−
1
)
)
{\displaystyle X_{n}=g(f(X_{n-1}))}
Y
n
=
g
(
f
(
Y
n
−
1
)
)
{\displaystyle Y_{n}=g(f(Y_{n-1}))}
g
{\displaystyle g}
단사 함수 이므로,
y
=
f
(
x
)
=
h
(
x
)
{\displaystyle y=f(x)=h(x)}
x
∈
X
n
−
1
∖
Y
n
−
1
{\displaystyle x\in X_{n-1}\setminus Y_{n-1}}
g
(
y
)
∈
Y
n
∖
X
n
+
1
{\displaystyle g(y)\in Y_{n}\setminus X_{n+1}}
h
(
g
(
y
)
)
=
g
−
1
(
g
(
y
)
)
=
y
{\displaystyle h(g(y))=g^{-1}(g(y))=y}
편의상
X
∩
Y
=
∅
{\displaystyle X\cap Y=\varnothing }
X
~
=
{
(
0
,
x
)
:
x
∈
X
}
{\displaystyle {\tilde {X}}=\{(0,x)\colon x\in X\}}
Y
~
=
{
(
1
,
y
)
:
y
∈
Y
}
{\displaystyle {\tilde {Y}}=\{(1,y)\colon y\in Y\}}
f
:
X
→
Y
{\displaystyle f\colon X\to Y}
g
:
Y
→
X
{\displaystyle g\colon Y\to X}
역함수
f
−
1
:
f
(
X
)
→
X
{\displaystyle f^{-1}\colon f(X)\to X}
g
−
1
:
g
(
Y
)
→
Y
{\displaystyle g^{-1}\colon g(Y)\to Y}
를 정의하자. 임의의
x
∈
X
{\displaystyle x\in X}
X
⊔
Y
{\displaystyle X\sqcup Y}
…
,
f
−
1
(
g
−
1
(
x
)
)
,
g
−
1
(
x
)
,
x
,
f
(
x
)
,
g
(
f
(
x
)
)
,
…
{\displaystyle \dots ,f^{-1}(g^{-1}(x)),g^{-1}(x),x,f(x),g(f(x)),\dots }
을 구성할 수 있다. 마찬가지로, 임의의
y
∈
Y
{\displaystyle y\in Y}
X
∪
Y
{\displaystyle X\cup Y}
…
,
g
−
1
(
f
−
1
(
y
)
)
,
f
−
1
(
y
)
,
y
,
g
(
y
)
,
f
(
g
(
y
)
)
,
…
{\displaystyle \dots ,g^{-1}(f^{-1}(y)),f^{-1}(y),y,g(y),f(g(y)),\dots }
을 구성할 수 있다. 이러한 열은
X
{\displaystyle X}
Y
{\displaystyle Y}
f
−
1
{\displaystyle f^{-1}}
g
−
1
{\displaystyle g^{-1}}
X
{\displaystyle X}
Y
{\displaystyle Y}
X
⊔
Y
{\displaystyle X\sqcup Y}
분할 한다. 따라서, 각 열에 등장하는
X
{\displaystyle X}
Y
{\displaystyle Y}
전단사 함수 를 찾으면 충분하다. 임의의 항은 열을 결정하므로, 특히 바로 다음 항을 결정한다. 즉, 임의의 항을 오른쪽의 이웃하는 항으로 대응시키는 함수는 항상 잘 정의된다. 이는 열 속
X
{\displaystyle X}
Y
{\displaystyle Y}
전단사 함수 이거나, 반대 방향의 전단사 함수 이다.
X
{\displaystyle X}
멱집합 격자
(
P
(
X
)
,
⊆
)
{\displaystyle ({\mathcal {P}}(X),\subseteq )}
완비 격자 를 이룬다. 함수
P
(
X
)
→
P
(
X
)
{\displaystyle {\mathcal {P}}(X)\to {\mathcal {P}}(X)}
S
↦
X
∖
g
(
Y
∖
f
(
S
)
)
{\displaystyle S\mapsto X\setminus g(Y\setminus f(S))}
는 순서 보존 함수 이므로, 타르스키 고정점 정리 에 따라 고정점
S
⊆
X
{\displaystyle S\subseteq X}
X
∖
S
=
g
(
Y
∖
f
(
S
)
)
{\displaystyle X\setminus S=g(Y\setminus f(S))}
이다. 따라서, 전단사 함수
X
→
Y
{\displaystyle X\to Y}
x
↦
{
f
(
x
)
x
∈
S
g
−
1
(
x
)
x
∈
X
∖
S
{\displaystyle x\mapsto {\begin{cases}f(x)&x\in S\\g^{-1}(x)&x\in X\setminus S\end{cases}}}
가 존재한다.
