집합론에서 칸토어의 정리(영어: Cantor's theorem)는 멱집합의 크기가 항상 원래의 집합의 크기보다 크다는 정리이다. 즉, 집합과 멱집합의 원소는 일대일 대응할 수 없다.
집합
의 멱집합
는
의 모든 부분 집합의 집합이다.
칸토어의 정리에 따르면, 멱집합
의 크기는 항상 원래의 집합
의 크기보다 크다. 즉, 다음이 성립한다.
![{\displaystyle |2^{X}|>|X|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffdc316101ce10fd32827a9338407194ab62f99d)
즉, 임의의 기수
에 대하여, 다음이 성립한다.
![{\displaystyle 2^{\kappa }>\kappa }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7280231a8641bb0cc4885b8c81d4b6f6392f47fd)
만약
이라면,
![{\displaystyle |\varnothing |=0<1=|\{\varnothing \}|=|2^{\varnothing }|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/283458154cabe70522023dc9d6aaf3248631d9c6)
이므로 성립한다.
만약
이라면, 우선 단사 함수
![{\displaystyle X\to 2^{X}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2f049372f4e4f3c8970737545a441d5d2fe49b8)
![{\displaystyle x\mapsto \{x\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/677f0a4a44a23922d2a73949f8e0cb30735eb6c0)
가 존재하므로,
![{\displaystyle |X|\leq |2^{X}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afaeb04d55c59d135a67ca736be0e25149ed1c6b)
이다. 또한, 만약
![{\displaystyle |X|=|2^{X}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91f422a0e5aa83086079a2647503bf9ce2ae6093)
라고 가정하면, 전단사 함수
![{\displaystyle f\colon X\to 2^{X}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b134c615ed1213bb94ce240203d9d3addc338eac)
가 존재한다. 이 경우, 부분 집합
![{\displaystyle f(a)=\{x\in X\colon x\not \in f(x)\}\in 2^{X}\qquad (a\in X)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d33439beb6cec426862839788b8523452fb0550)
를 구성할 수 있는데,
의 정의에 따라
![{\displaystyle a\in f(a)\iff a\not \in f(a)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50b7a7124196b3232f9f0c026e9611c8ae86177a)
이며, 이는 모순이다. 즉,
![{\displaystyle |X|\neq |2^{X}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6a7cc50a496e43fa6247a8e40e29bcd35db493f)
이며, 따라서
![{\displaystyle |X|<|2^{X}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7212709d48b6fffc99e0f0d4161c64192447bfc)
이다.
게오르크 칸토어가 증명하였다. 이 정리로부터 제기된 의문은 연속체 가설의 토대를 제공하였다.
같이 보기[편집]