집합론에서, 칸토어-번슈타인 정리(영어: Cantor-Bernstein theorem)는 두 집합 사이에 두 방향으로 단사 함수가 존재하면 그 사이에 일대일 대응이 존재한다는 정리이다. 이는 선택 공리에 의존하지 않고 증명할 수 있다.
다음 두 명제가 서로 동치이며, 이를 칸토어-번슈타인 정리라고 한다.
두 단사 함수 f : A → B {\displaystyle f\colon A\to B} 와 g : B → A {\displaystyle g\colon B\to A} 가 주어졌다고 하자.
집합족 { C n } n = 0 ∞ {\displaystyle \{C_{n}\}_{n=0}^{\infty }} 및 집합 C {\displaystyle C} 및 함수 h : A → B {\displaystyle h\colon A\to B} 를 다음과 같이 정의하자.
우선 h {\displaystyle h} 는 단사 함수이다. x , y ∈ A {\displaystyle x,y\in A} 이며 x ≠ y {\displaystyle x\neq y} 라고 하자. x , y ∈ C {\displaystyle x,y\in C} 인 경우, f {\displaystyle f} 가 단사 함수이므로 h ( x ) ≠ h ( y ) {\displaystyle h(x)\neq h(y)} 이다. x , y ∈ A ∖ C {\displaystyle x,y\in A\setminus C} 인 경우, g − 1 {\displaystyle g^{-1}} 가 A ∖ C {\displaystyle A\setminus C} 에서 단사 함수이므로 역시 h ( x ) ≠ h ( y ) {\displaystyle h(x)\neq h(y)} 이다. x ∈ C n ⊆ C {\displaystyle x\in C_{n}\subseteq C} 이며 y ∈ A ∖ C {\displaystyle y\in A\setminus C} 인 경우, h ( x ) ∈ f ( C n ) = g − 1 ( C n + 1 ) {\displaystyle h(x)\in f(C_{n})=g^{-1}(C_{n+1})} 이며 h ( y ) ∈ g − 1 ( A ∖ C ) {\displaystyle h(y)\in g^{-1}(A\setminus C)} 이므로 h ( x ) ≠ h ( y ) {\displaystyle h(x)\neq h(y)} 이다.
또한 h {\displaystyle h} 는 전사 함수이다. b ∈ B {\displaystyle b\in B} 라고 하자. b ∈ f ( C ) {\displaystyle b\in f(C)} 인 경우, 당연히 b = h ( a ) {\displaystyle b=h(a)} 인 a ∈ A {\displaystyle a\in A} 가 존재한다. b ∉ f ( C ) {\displaystyle b\notin f(C)} 인 경우, a = g ( b ) {\displaystyle a=g(b)} 로 놓으면, a ∈ g ( B ∖ f ( C ) ) {\displaystyle a\in g(B\setminus f(C))} 즉 a ∈ A ∖ C {\displaystyle a\in A\setminus C} 이므로 b = h ( a ) {\displaystyle b=h(a)} 이다.
이에 따라 전단사 함수 h : A → B {\displaystyle h\colon A\to B} 가 존재한다.