집합의 크기(카디널리티)

집합의 크기의 정의

집합의 크기는 다른 말로 카디널리티(cardinality)라고 한다. 집합의 크기는 아래와 같이 정의된다. 

두 집합 A,B 사이에 일대일 대응 함수(전단사 함수) A→B가 존재한다면 두 집합 A, B의 크기가 같다.

두 집합 A,B 사이에 일대일 함수(단사 함수) A→B가 존재하지만, 반영 함수(전사 함수) A→B가 존재하지 않는다면 A가 B보다 크기가 작다.

디시 말하면 A의 각기 다른 모든 원소가 B의 각기 다른 모든 원소와 유일하게 대응된다면 두 집합 A와 B의 크기가 같다고 할 수 있다. 바구니 A와 바구니 B 안에 정확히 몇개가 있는지 알 수 없는 공들이 들어있다고 생각하자. 바구니 A에서 공을 하나 꺼낼 때 마다 바구니 B에서 공을 꺼내도록 하자. 만약 A에서 공을 모두 꺼냈는데, B에 공이 남았다면 A보다 B에 공이 더 많이 들있다고 할 수 있다. 반대로 A에서 공을 모두 꺼내지 않았는데 B에 공이 다 떨어졌다면 A가 B보다 공이 더 많이 들었다고 할 수 있다. 만약 A에서 공을 모두 꺼냈더니 B에 더이상 남은 공이 없다면? 그렇다면 A와 B의 공의 개수가 같다고 할 수 있다.

 

유한집합인 경우 두 집합의 크기를 비교하는 것이 매우 쉽다. 원소의 갯수를 세어줬을 때 원소의 갯수가 더 적은 쪽이 크기도 당연히 작다. 하지만 무한집합(원소의 개수가 유한하지 않은 집합)인 경우 크기를 비교하는 것이 선뜻 쉽지 않다. 그러나 두 집합이 무한집합이라고 해서 크기를 비교할 수 없는 것은 아니며, 크기가 같을수도, 다를 수도 있다. 위에서 본 "집합의 크기"의 정의를 이용하면 무한집합의 크기를 비교할 수 있다.

무한 집합의 크기 비교와 칸토어의 대각선 논법

대표적으로 자연수 집합(양의 정수)과 양의 짝수 집합을 생각해보자. 직관적으로 생각했을 때 짝수집합은 자연수집합보다 더 크다고 착각을 할 수 있다. 아니면 두 집합이 모두 무한집합이니 크기를 비교할 수 없다고 생각할 수도 있다. 그러나 두 집합의 크기는 비교할 수 있으며, 두 집합의 크기는 같다.

자연수 집합    -  1 2 3 4 ...
양의짝수 집합 -  2 4 6 8 ...

자연수 집합과 양의 짝수 집합을 일렬로 나열해보자. 이제 각 집합의 원소를 하나씩 차례로 짝을 지으면 f(x) = 2x 라는 함수 f를 얻을 수 있다. 이 함수는 자연수 x와 y에 대해서 x ≠ y일 때 2x≠2y 이므로 일대일 함수라는 것을 알 수 있다. 반대로 2x≠2y라면 x≠y이므로 반영함수라는 것을 알 수 있다. 즉 f는 일대일 대응 함수이다. 집합의 크기에 대한 정의에 의하면 두 집합의 크기는 같다고 할 수 있다. 같은 방식으로 자연수 집합과 정수 집합의 크기가 서로 같은 것을 증명할 수 있다.

 

한편 무한집합이라고 해서 항상 크기가 같은 것은 아니다. 두 무한집합 A, B에서 A의 모든 원소가 유일하게 B의 모든 원소와 대응되지 않는다면 A가 B보다 더 크다고 할 수 있다. 대표적인 예시로 실수 집합은 정수 집합보다 더 크다.

 

f(x)=tan( xπ + π/2) 를 생각해보자.

tan( xπ + π/2) 

이 함수는 구간 (0,1)에서 실수 집합과 일대일 대응이다. 따라서 구간 (0,1)은 실수집합의 크기가 같다는 것을 알 수 있다. 만약 모든 자연수가 구간 (0,1)에 있는 실수와 일대일 대응인 함수를 찾을 수 있다면, 실수 집합과 정수 집합의 크기가 같다. 

 

우선 실수 집합과 정수 집합의 크기가 같다고 가정하자. 즉, (0,1) 사이에 있는 실수와 자연수를 일대일로 대응시킬수 있다고 생각해보자.

 

(0,1)사이에 있는 실수를 자연수와 일대일 대응을 시켜보자. 단, 0.23과 같은 유한소수는 0.22999...등 무한소수로 변환해 모든 실수가 무한소수꼴로 나타내어질 수 있도록 하자. 

이렇게 모든 실수가 자연수에 하나씩 빈틈없이 대응되도록 했지만, 문제는 어떠한 자연수에도 대응되지 않는 실수가 존재한다. 그런 실수가 과연 존재할까?

(0,1)구간 사이의 어떤 실수 r을 다음과 같이 정의하자.

이 bi는 다음과 같은 규칙을 가지고 있다.

aii가 1일 경우, bi는 2가 된다. 그러나 aii가 1이 아닐경우, bi는 1이 된다. 

bi의 정의에 의해서 bi는 aii와 같은 수가 아니다. 이 때문에 bi는 각 자연수와 대응되는 모든 실수와 다를수 밖에 없다. 위 그림에서 대각선으로 노랗게 표시된 지점들을 보자. bi는 aii와 같은 수가 아니기 때문에 r은 위 나열의 어떤 실수와도 같은 실수가 아니다. 즉 r은 어떤 자연수에도 대응될 수 없는것이다. 바로 f가 전사함수가 아니라는 것이 r의 존재로 증명된 것이다. 따라서 실수 집합은 자연수 집합보다 더 크다.

가산적 집합 (셀수 있는 집합)

위에서 살펴본 것 처럼 정수 집합과 실수 집합은 크기가 다르다. 종합격투기에서 헤비급, 미들급, 라이트급이 나뉘는 것 처럼 무한에도 체급이 있다는 것이다. 특히 자연수, 정수, 짝수 등의 체급을 가진 집합을 우리는 가산적 집합이라고 한다. 그와 반면에 실수의 집합처럼 정수의 집합보다 크기가 큰 집합을 비가산적 집합이라고 한다. 

 

대표적인 가산적 집합 : 정수, 짝수, 자연수, 유리수 등등 ...

대표적인 비가산적 집합 : 실수, 무리수, 자연수 집합의 멱집합 등등 ...