이전 읽을거리)
[집합론 기초] ch2. 합집합, 교집합, 명제
함수의 엄밀한 정의
데카르트 곱의 일반화된 정의
수학적 귀납법과 정렬원리
다음 읽을거리: ch2. 가산집합과 비가산집합
유한집합의 정의
자연수 에 대해 보다 작은 자연수의 집합을 또는 이라고 표기하고, 이를 자연수의 절편(section)이라고 한다. 물론 이다. 자연수의 절편은 유한집합이라고 불리는 것들의 원형이다.
Definition. 집합 와 자연수의 어떤 절편 에 대해 일대일 대응 이 존재하면 가 유한하다(finite)고 한다. 다시말해 가 유한하다는 것은 공집합이거나, 어떤 자연수 에 대해 전단사함수 이 존재하는 것이다. 전자의 경우 의 크기(cardinality)가 0이라고 하고, 후자의 경우 의 크기가 이라고 한다.
예를들면 집합 은 항등함수에 의해 스스로에 대한 일대일대응을 가지므로 크기가 이다.
아직 우리는 유한집합의 크기가 그 집합에 의해 유일하게 결정됨을 보이지 않았음에 유의하자. 공집합의 경우 크기가 0임은 분명하다. 하지만 현재까지의 정보로는, 공집합이 아닌 집합 에서 서로 다른 두 집합 , 으로의 두 일대일대응이 존재할 수 없다고 확신할 수 없다. 이는 마치 두 사람이 한 상자 안의 조약돌 갯수를 세고 서로 다른 수를 말했는데 둘 다 정답인 것과 비슷하므로, 우스꽝스러운 가능성에 대해 논의하는 것 처럼 느껴진다. 일상에서 갯수를 세어본 경험을 이것이 불가능함을 암시하며, 실제로 작은 수 1,2,3 등에 대해서는 이를 쉽게 증명할 수 있다. 그러나 5백만 등의 경우 이를 직접 증명하는 것은 엄청나게 부담스러울 것이다.
인생을 살며 우리는 작은 집합을 세는 경험이 임의의 큰 집합에 대해서도 동일학 적용될 것이라고 믿는다. 그러나 수학에서는 이러한 표현을 믿음에 의지하지 않는다. 물리적 셈 보다는 일대일대응의 유무가 수학적 증명으로 적합하다.
유한집합의 성질
유한집합에 대한 수많은 직관적 사실들은 수학적으로 증명 가능하다. 아래는 그 시작으로 적절한 예시이다.
Lemma 1.1. 자연수 과 집합 , 의 원소 을 생각하자. 일대일대응 이 존재할 필요충분조건은 일대일대응 이 존재하는 것이다.
Proof.
() 일대일대응 이 존재한다고 가정하자. 이때 함수 을 다음과 같이 정의하자.
는 자명하게 전단사이므로 원하는 결과를 얻는다.
() 일대일대응 이 존재한다고 가정하자. 만약 이라면 은 우리가 찾는 일대일대응 이다. 그 밖의 경우에 대해, 이라고 하고 이도록 하는 를 생각하자. 이때 이다. 이제 새로운 함수 을 다음과 같이 정의하자.
는 자명하게 전단사이다. 이때 은 우리가 찾는 일대일대응 이므로 원하는 결과를 얻는다.
이 보조정리로부터 수많은 유용한 결과가 얻어진다.
Theorem 1.2. 집합 에 대해, 어떤 자연수 에 대하여 일대일대응 이 존재한다고 가정하자. 진부분집합 에 대해 일대일대응 은 존재하지 않지만, 인 경우 어떤 에 대해 일대일대응 이 존재한다.
Proof. 의 경우 공집합 에서 공집합이 아닌 집합으로의 전단사함수가 존재할 수 없으므로 본 정리가 자명하게 성립한다.
이 정리를 귀납법으로 증명하자. 먼저 이 정리가 에 대해 참임을 보이자 이 경우 는 홀원소집합이며 이의 유일한 진부분집합 는 공집합이므로 위의 논의에 따라 본 정리가 성립한다.
이제 이 정리가 에 대해 참이라고 가정하고 에 대해서도 참임을 보이자. 일대일대응 과 의 공집합이 아닌 진부분집합 를 생각하자. 의 원소 과 의 원소 을 선택하자. 보조정리 1.1.에 따르면 일대일대응 이 존재한다. 이때 은 에 속하지만 에는 속하지 않으므로 는 의 진부분집합이다. 귀납법 가정에 따라 다음이 성립한다.
(1) 일대일대응 이 존재하지 않는다.
(2) 이거나 어떤 에 대해 일대일대응 가 존재한다.
(1) 과 도움정리 1.1.에 따르면 일대일대응 은 존재하지 않는다. 이는 본 정리의 첫 번째 결론이다. 본 정리의 두 번째 결론을 증명하자. 만약 이면 이므로 일대일대응 이 존재한다. 반면 이라면 (2)와 도움정리 1.1.에 따라 일대일대응 이 존재하며, 특히 이다. 정리하면 두 경우 모두 어떤 에 대해 일대일대응 이 존재하므로 원하는 결과를 얻는다.
따름정리들
Corollary 1.3. 유한집합 에 대해, 에서 의 진부분집합으로의 일대일대응은 존재하지 않는다.
Proof. 모순을 보이기 위해 의 진부분집합 에 대해 일대일대응 가 존재한다고 가정하자. 유한집합의 정의에 따라 어떤 자연수 에 대해 일대일대응 이 존재한다. 이때 합성함수 는 일대일대응 이며, 이는 정리 1.2.와 모순된다. 따라서 원하는 결과를 얻는다.
Corollary 1.4. 은 유한하지 않다.
Proof. 함수 , 은 에서 의 진부분집합으로의 일대일대응이다. 따름정리 1.3.에 따라 는 유한하지 않다.
Corollary 1.5. 유한집합 의 크기는 에 의해 유일하게 결정된다.
Proof. 에 대해 일대일대응 , 을 생각하자. 합성함수 는 일대일대응 이다. 은 의 진부분집함이므로 이는 따름정리 1.3.에 모순되므로 원하는 결과를 얻는다.
Corollary 1.6. 가 유한집합 의 부분집합이면 는 유한하다. 만약 가 의 진부분집합이면 의 크기는 의 크기보다 작다.
Proof. 이면 자명하게 는 유한하다. 가 의 진부분집합이라고 가정하자. (이 가정은 를 전제한다) 만약 이면 는 유한하며 의 크기는 0이므로 본 정리가 성립한다. 이면 정리 1.2.에 따라 의 크기를 이라고 할 때 어떤 에 대해 일대일대응 이 존재한다. 따라서 는 유한하며, 의 크기 은 보다 작으므로 원하는 결과를 얻는다.
다음의 정리에 따르면 어떤 집합이 유한할 조건은 (자연수의 절편과의) 전단사함수가 존재하는 대신, 적절한 방향의 전사함수 또는 단사함수가 존재하는 것 만으로 충분함을 말한다.
Corollary 1.7. 공집합이 아닌 집합 에 대해 다음의 세 명제는 동치이다.
(1) 는 유한하다.
(2) 어떤 자연수 에 대해 전사함수 가 존재한다.
(3) 어떤 자연수 에 대해 단사함수 가 존재한다.
Proof.
() 는 공집합이 아니므로, 유한성의 정의에 따라 에서 자연수의 어떤 절편으로의 전단사함수가 존재한다.
() 전사함수 에 대해, 함수 을 각 에 대해 라고 정의하자. 는 전사이므로 는 공집합이 아니며 정렬원리에 따라 최소원소가 존재하므로 가 잘 정의된다. 이때 에 대해 와 는 서로소이므로 (만약 서로소가 아니면 공통의 원소 에 대해 , , 이며 이는 대응규칙의 정의에 어긋난다) 각 집합의 최소원소도 서로 다르다. 따라서 는 단사이다.
() 단사함수 에 대해, 의 치역을 라고 하자. 이때 함수 , 는 전단사이다. 는 유한집합 의 부분집합이므로 유한하며, 의 크기를 이라고 할 때 일대일대응 에 대해 합성함수 는 일대일대응 이므로 는 유한하다.
Corollary 1.8. 유한집합의 유한 합집합과 유한 데카르트 곱은 유한하다.
Proof. 먼저 유한집합 에 대해 가 유한함을 보이자. 또는 가 공집합인 경우에는 자명하게 성립한다. 그 밖의 경우 어떤 자연수 에 대해 전단사함수 , 가 존재한다. 에서 로의 함수 를 각 에서 , 각 에서 이라고 정의하자. 는 전사함수이므로 따름정리 1.7.에 따라 는 유한하다.
이제 귀납법을 이용해 집합 이 유한하면 이 유한함을 보이자. 인 경우에 정리가 자명하게 성립한다. 에서 정리가 성립한다고 가정하자. 이때 집합 은 유한집합 과 유한집합 의 합집합이므로 위의 논의에 따라 에서도 정리가 성립한다. 따라서 원하는 결과를 얻는다.
유한집합 에 대해 가 유한함을 보이자. 만약 또는 가 공집합이라면 이므로 는 유한하다. 그 밖의 경우, 각 에 대해 는 자명한 일대일대응 에 의해 유한하다. 는 이러한 집합의 합집합이다. 가 유한하므로 이는 유한집합이 유한 합집합이며 따라서 는 유한하다.
이제 귀납법을 이용해 집합 이 유한하면 이 유한함을 보이자. 의 원소의 1-순서쌍의 집합은 자명한 일대일대응 에 의해 유한하므로 의 경우 정리가 성립한다. 에서 정리가 성립한다고 가정하자. 이전의 논의에 따라 과 의 데카르트 곱 은 유한하며, 자명한 일대일대응
에 의해 도 유한하다. 따라서 원하는 결과를 얻는다.
읽어주셔서 감사합니다.
References)
[1] James R. Munkres. (2000). Topology. Pearson College Div.
이전 읽을거리)
[집합론 기초] ch2. 합집합, 교집합, 명제
함수의 엄밀한 정의
데카르트 곱의 일반화된 정의
수학적 귀납법과 정렬원리
다음 읽을거리: ch2. 가산집합과 비가산집합
댓글