칸토어-베른슈타인 정리

집합론에서, 칸토어-베른슈타인 정리(영어: Cantor–Bernstein theorem) 또는 슈뢰더-베른슈타인 정리(영어: Schröder–Bernstein theorem)는 두 집합 사이에 두 방향으로 모두 단사 함수가 존재한다면, 두 집합 사이에 일대일 대응이 존재한다는 정리이다. 체르멜로-프렝켈 집합론에서 선택 공리를 사용하지 않고 증명할 수 있다. 칸토어-베른슈타인 정리에 따라, 기수의 표준적인 순서는 부분 순서이다. 선택 공리를 추가로 가정하면, 기수의 순서가 전순서임을 보일 수 있다.

칸토어-베른슈타인 정리의 최초의 서술

정의 편집

칸토어-베른슈타인 정리는 다음과 같다.[1]:28, Theorem 3.2

  • 두 집합    사이에 단사 함수   가 존재한다면, 전단사 함수  가 존재한다.

이는 선택 공리 없이 증명할 수 있다.

기수는 같은 수의 원소를 포함하는 집합들을 묶은 동치류로 여길 수 있다. 구체적으로, 만약 전단사 함수  가 존재한다면,  라고 정의한다 (  크기를 나타내는 기수). 만약 단사 함수  가 존재한다면,  라고 정의한다. 물론, 기수의 순서  의 정의는 기수를 크기로 하는 집합의 선택과 무관하다. 이 순서는 반사 관계이며 (항등 함수는 단사 함수), 추이적 관계이다 (단사 함수의 합성은 단사 함수). 칸토어-베른슈타인 정리는 다음과 같이 적을 수 있다.

  • 만약  이며  라면,  이다.

즉, 기수의 순서는 반대칭 관계이며, 따라서 부분 순서이다.

정렬 집합들 사이에서는 항상 크기를 비교할 수 있다. 선택 공리를 가정하면, 모든 집합정렬 집합과 크기가 같으므로, 모든 집합들의 크기는 비교 가능하다. 즉, 기수의 순서는 전순서이다.

증명 편집

같은 맥락의 여러 증명들이 존재한다.

표준적인 증명 편집

다음과 같이 정의하자.[1]:28, Theorem 3.2

 
 
 
 

그러면 일련의  부분 집합

 

을 얻는다. (자명하게  이다.  이므로  이다.   에 대한 을 씌우면  를 얻는다.) 이제, 함수  를 다음과 같이 정의하자.

 

( 전단사 함수일 필요가 없으므로 역함수를 가질 필요가 없지만, 공역을 제한하여 부분적인 역함수  를 정의할 수 있다.) 이제  단사 함수이자 전사 함수임을 보이면 충분하다.

  •  는 단사 함수
    •   로 제한되었을 때  이며, 그 여집합  로 제한하면  이다.   은 단사 함수이다. 따라서,  의 서로 다른 원소 또는  의 서로 다른 원소의,  에 대한 상은 서로 다르다.   의 원소를  의 원소로 보내고,  의 원소를 (스스로로 보내므로)  로 보낸다.   는 서로 만나지 않는다. 따라서,  의 원소와  원소의,  에 대한 상은 서로 다르다.
  •  는 전사 함수
    •  라고 하자.  이라면,  이다 ( ). 즉,  ,  이다.  단사 함수이므로,   이 존재한다.  이라면,  이다.

쾨니그의 증명 편집

편의상  이라고 가정하자 (가정이 참이 아니라면, 두 집합을 크기가 같은 두 서로소 집합   로 대체한다). 단사 함수   의 부분적 역함수

 
 

를 정의하자. 임의의  에 대하여,   위의 열

 

을 구성할 수 있다. 마찬가지로, 임의의  에 대하여,   위의 열

 

을 구성할 수 있다. 이러한 열은   의 원소가 번갈아 가며 나타나며, 오른쪽으로는 끝없이 이어지고, 왼쪽은 끝이 없거나 (  가 정의되지 않는) 어떤   또는  의 원소에서 끝이 난다. 임의의 항은 열을 완전하게 결정하므로, 두 열이 어떤 항을 공유한다면, 두 열은 서로 같다. 즉, 위와 같은 꼴의 열들은  분할한다. 따라서, 각 열에 등장하는  의 원소와  의 원소 사이의 전단사 함수를 찾으면 충분하다. 임의의 항은 열을 결정하므로, 특히 바로 다음 항을 결정한다. 즉, 임의의 항을 오른쪽의 이웃하는 항으로 대응시키는 함수는 항상 잘 정의된다. 이는 열 속  의 원소에서 열 속  의 원소로 가는 전단사 함수이거나, 반대 방향의 전단사 함수이다.

타르스키 고정점 정리를 통한 증명 편집

 멱집합 격자  완비 격자를 이룬다. 함수

 
 

순서 보존 함수이므로, 타르스키 고정점 정리에 따라 고정점  를 갖는다. 즉,

 

이다. 따라서, 전단사 함수

 
 

가 존재한다.

참고 문헌 편집

  1. Jech, Thomas (2003). 《Set theory》. Springer Monographs in Mathematics (영어) 3판. Berlin: Springer. doi:10.1007/3-540-44761-X. ISBN 978-3-540-44085-7. ISSN 1439-7382. MR 1940513. Zbl 1007.03002. 

외부 링크 편집