울산대학교 | 데이터응용수학과
본문바로가기

울산대학교

ender

커뮤니티

메인화면 바로가기
커뮤니티
자료실
공유 프린트

자료실

집합론 탐방(3)
작성자 하** 작성일 2017-07-07 조회수 3239

1-3 집합의 농도

공집합이 아닌 집합 에 대하여 적당한 자연수 이 존재하여

이 성립할 때, 를 유한집합이라 한다. 이 때, 자연수 을 집합 의 원소의 개수라 한다.

유한집합이 아닌 집합을 무한집합이라 한다. 집합 와 가 를 만족할 때, 와 는 같은 농도를 가진다고 한다. 이 개념은 유한집합의 개수의 확장된 개념이다. 의 농도를

라 나타내기로 한다. 집합 와 가 같은 농도를 가지면 = 이다.

 

 

(1) 가산집합

자연수의 집합 의 농도 을 가산농도라 한다. 과 동등인 집합을 가산집합이라 한다.

 

정리 10. 정수의 집합 는 가산집합이다.

증명. 를 으로 나열하면 처음부터 순서대로 번호를 붙일 수 있어서 는 가산집합이 된다. 즉, = .□

정리 11. 유리수 집합 는 가산집합이다.

증명. 우선, 양의 유리수 집합이 가산집합임을 보이자. 양의 유리수를 아래 표와 같이 나열해서 오른쪽 위에서부터 왼쪽 밑으로 비스듬히 번호를 붙여 나간다.

첨자는 붙인 번호를 의미하고, 같은 수가 반복하여 나올 때는 건너 뛰어 번호를 붙여 나간다. 이런 시행을 계속하면 양의 유리수가 가산집합이 됨을 안다. 과 음의 유리수는 정리10과 같은 방법을 통하여 유리수는 가산집합이 된다. 즉, = .

 

따름정리. 가산집합의 가산무한의 합집합은 가산집합이다.

증명. 정리 11과 같은 방법으로 각 가산집합을 위로부터 순서대로 나열하고, 그것을

오른쪽 위에서부터 왼쪽 밑으로 비스듬히 번호를 붙여 나가면 된다.□

 

(2) 연속체의 농도

과 는 외견상 다른 크기에도 구애되지 않고 같은 가산농도를 가짐을 알았으나 이의 농도가 가산이 아님을 칸토어가 발견하였다.

 

정리 12. 실수의 개구간 은 과 동등이 아니다.

증명. 귀류법으로 증명하자. 개구간 의 수의 집합이 가산농도를 가진다고 하자.

의 원소 을 빠짐없이 다음과 같이 나열한다. 이 때, 대각선상의 숫자 에 주목하자. 숫자 을 다음과 같이 정한다.

 

 

위의 을 사용하여

를 만들면 이면서 는 과 소수점이하 번째 자리가 다르므로 모든 과 다르게 된다. 이것은 의 모든 수에 번호가 매겨졌다는 사실에 모순이다. 그러므로

이다.□

 

는 개구간 로부터 로 전단사로 사상한다. 또한, 는

를 로 전단사로 사상한다. 그러므로

이다. 실수전체의 집합의 농도 를 연속체의 농도라한다.

 

로부터 로의 사상 전부는 표로부터 8가지 이다.

 

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

이 사상으로 의 원소를 취하느냐 마느냐로 생각하면(가령, 의 상이 모두 0이므로 은 의 원소를 하나도 취하지 않는 것으로 간주한다), 이 사상 전체는 의 부분집합의 집합과 일대일로 대응된다. 그래서 그의 개수가 이다.

일반적으로, 로부터 로의 사상전체는 의 부분집합의 집합과 동등하므로 의 부분집합의 집합을 멱집합이라 하고

로 나타낸다.

 

 

정리 13. 를 임의의 집합이라고 할 때,

<

이다.

증명. 사상 을 생각하면, 명백히 단사이다.

.

다음으로 임을 보이자. 증명은 귀류법으로 한다.

지금, 전사 가 존재하고 있음을 가정한다.

라 두면 이다.

따라서, 가 전사이므로 의 원소 가 존재하여 이다.

(i) 이면, . . 이것은 모순이다.

(ii) 이면, . . 이것은 모순이다.

그러므로 는 나 이거나 이므로 전사는 존재하지 않는다.

< . □

 

주의. 이 정리는 의 농도보다 의 부분집합의 집합 의 농도가 정말로 크다는 것을 보여주고 있다. 여기서 칸토어가 제안하였고 생전에 증명하지 못한 연속체가설을 소개한다.

칸토어의 연속체가설

“ 가 무한히 많은 원소를 갖는 집합이면 의 원소의 개수보다 크고, 그것의 멱집합의 원소 개수보다 작은 집합이 존재하지 않는다.”

이것은 아래 괴델의 불완전성 정리에 의해 참 혹은 거짓인지 알 수 없는 것으로 밝혀졌다.

한편, 모든 것을 포함하는 집합의 존재는 당연시 되었으나 아래 러셀의 패러독스에 의하면 그것이 불가능하게 되었다. 러셀의 파라독스에 의하여 속성들이 실제로 실집합을 정의하고 있는지를 밝혀야 하는 과제를 안게 되었다. 그러나 그렇게 할 수 있는 방법을 제시하는 것은 불가능한 것일 수 도 있음을 아래 괴델의 불완전성 정리는 설명하고 있다.

 

칸토어의 패러독스로 알려지고 있는 다음의 성질을 생각해 보자.

“모든 것의 집합 의 부분집합의 집합 는 이미 집합이 아니다.”

증명. 귀류법으로 증명하자. 를 집합이라고 하면 의 정의로부터

이다. 그런데 . 따라서 . 이것은 정리 13에 모순이다. 따라서 는 집합이 아니다.□

※1901년 러셀은 언뜻 보아서 단순해 보이는 질문을 자문했다.

자기자신을 원소로 하지 않는 모든 집합의 집합을 생각하였다. 그는 이 집합을 이라 두고, 은 자신의 한 원소인가? 여기서 러셀은 패러독스를 얻었다. 집합 가 자신의 한 원소이면 원소가 아니고, 원소가 아니면 원소가 된다. 이를 러셀의 패러독스(칸토어의 패러독스와 유사함)라 하며 수학의 기초를 이루는 집합론과 논리의 구조를 뒤 흔들어 놓았다. 러셀의 패러독스의 핵심 의미는 모든 것을 포함하는 집합이란 존재할 수 없다는 것이다.

※1920년대에 이르러서 괴델은 어떤 체계가 주어 졌을 때, 그 체계 내에서는 증명될 수 없는 명제가 항상 존재한다는 것을 증명하였다. 어떤 정리가 참이라 해도, 그것을 수학적으로 증명하는 것이 불가능 할 수 있다. 이것이 바로 유명한 괴델의 불완전성 정리의 핵심이다.
목록보기