Set Power Class

집합 이야기의 틀 로 돌아가기

유한 집합과 무한 집합 ; 셀 수 있는 무한 집합과 셀 수 없는 무한 집합

집합론은 무한에 대한 탐구로부터 비롯되었다. 집합은 원소들의 모인 총체적인 한 덩어리다. 그런 집합들을 서로 비교하는 기초적인 관계들은 포함관계 ( $\subset$ ) , 같음관계 ( = ) , 그리고 집합의 세기가 같음 (여기서는 대등 관계라고 부르겠다. 기호로 $\sim$ ) 이 있었다. 이에 대한 정의나 기본적인 성질은 집합의 관계와 연산 , 집합의 크기 비교 를 참고하라.

보통 우리는 유한집합을 원소의 개수가 끝이 있는 집합으로 여기고 그렇지 않은 집합을 무한집합이라고 이해한다. 이를 우리는 '원소를 하나씩 세어가다 끝이 있으면' 유한 집합이라 하였고, 이 세어가기 과정이 끝이 나지 않는 것을 무한집합이라 불렀다. 그렇지만, 무엇이 '세어가다'이고 어떻게 '세어간다'는 것인가? 상식적으로 이해하는 유한과 무한에 대한 개념은 아직 충분하지 않다. 여기서는 이것에 대해 뜯어보고 더 엄격하게 유한과 무한에 대하여 정의하려고 한다. 이 정의는 물론 상식과 어긋나지 않는다. 다만 더 엄격하게 정의함으로서 안개 속처럼 뿌연 '유한'과 '무한'에 대한 개념에 맑은 햇살을 주어 더 분명하게 보는 것이다.

유한 집합의 정의

가장 기초적이고 명확한 것으로 받아들이는 자연수 세계에 발딪고 선다. 거기에 '하나씩 짝짓기' 개념을 사다리 삼아 유한과 무한 집합을 정의한다. 그리고 마침내 자연수 세계로부터 독립하여 '포함관계'와 '대등 관계' 로만 '유한 집합'과 '무한 집합'을 정의할 수 있다는 것을 확인할 것이다.

유한집합의 정의 : " n 개의 자연수 집합과 대등한 집합 "

기호 하나를 정하자. 집합의 이름을 줄 때, 보통 A, B, C 와 같이 썼지만 여기서는 집합의 원소에 따라 변하는 이름을 쓰자.

{\bar {n}}

:= { x | x 는 n 보다 같거나 작은 자연수 }

그렇다면 | ${\bar {n}}$ | = n 인 것은 분명하다. 그럴 때 유한집합을 다음과 같이 정의할 수 있다.

정의 (유한집합) :

\emptyset

이나 어떤 n 에 대해

{\bar {n}}

과 대등한 집합을 유한집합이라 부른다. 그렇지 않으면 무한집합이라 한다.

한번 생각해보라.

여기서 유한 집합의 정의를 " 어떤 n 에 대하여

{\bar {n}}

의 부분집합과 대등한 집합을 유한집합이라 한다" 라고 하면 어떻게 될까?

유한집합의 성질

여기서는 유한 집합들 끼리의 포함관계에 따라 대등성이 어떻게 변하는지 본다. 다시 말해 포함관계와 대등관계의 관계에 대하여 보는 것이다.

(정리1) X 는 유한집합일 때, X 가 Y의 진부분집합 이거나 Y가 X 의 진부분집합이면, X $\nsim$ Y 다.

이를 보이면, 논리적으로, X 가 유한집합일 때,

X\sim Y\rightarrow X=Y

가 될 수 있다. 물론 두 집합이, 예를들어 {1, 3} 와 {영동고속도로, 사과} 처럼, 어떤 포함관계도 없으면 위의 문장은 말이 안된다. 하지만, 두집합이 포함관계로 비교할 수 있다면 같음 관계와 대등관계는 논리적으로 비슷한 성질을 갖는다는 것을 시사한다. 이 정리는 앞으로 나올 정리들의 가장 기초가 되는 정리이기 때문에 증명을 소개한다.

Y 가 X의 진부분집합이면 X $\nsim$ Y 를 보도록 하자.

만약 X 가 비어있는 집합이라면, 그런 Y 는 없다. 따라서 X 와 대등한 집합은 없다.
만약 X 가 비어있는 집합이 아니면, $\sim {\bar {n}}$ $\sim {\bar {n}}$ 인 어떤 n 이 있다. 수학적 귀납의 원칙을 써서 보이기로 하자.
- (base) n = 1 이면 Y는 비어있어야 한다. 따라서 X $\nsim$ Y.
- (step) n = k 에서 X $\nsim$ Y 이 성립한다면 반드시 n = k+1 일 때도 성립한다는 것을 보여야 한다.

우리가 보여야 할 것은 X 가 {1, 2, 3, ... , k + 1 } 와 일대일로 대응할 때, 그 진부분집합 Y 는 X 와 일대일 대응이 있을 수 없다는 사실이다.

진부분집합 Y 는 X 와 일대일 대응 g 가 있다고 해보자.

그리고 X 가 {1, 2, 3, ... , k + 1 } 와 일대일로 대응하기 때문에, 그 때의 대응을 f 라 하면, X의 모든 원소는 {f(1), f(2), ... , f(k+1)} 이 된다. 진부분 집합 Y와 본래집합 X가 g로 일대일 대응하기 때문에, 집합 Y 는 { g(f(1)), g(f(2)), ... , g(f(k+1))} 다.

그런데 Y 는 X 의 진부분집합이다. 따라서 최소한 X 의 어떤 원소 중 최소한 하나는 Y 에 있다. 그것을 f(1) 이라 하자. f(1) 은 g(f(1)), g(f(2)), ... , g(f(k+1))들 중 하나와 겹칠 것이다. 그것을 g(f(k+1)) 이라고 해보자.

이제 집합 X 와 집합 Y 에서 같은 원소 f(1) 을 빼낸 집합들을 보자. 그것들을 X' , Y' 라 하자.

다시 말해 X' := { f(2), ... , f(k+1)} 이고 Y':= { g(f(1)), g(f(2)), ... ,g(f(k)) } 다. 그런데 Y 와 X는 g 로 일대일로 대응한다고 했고, 같은 원소를 빼냈기 때문에 여기서도 X'와 Y' 는 g 로 일대일 대응한다. 그리고 여전히 Y'는 X'의 진부분집합이다.

이것은 말이 안된다. 왜냐하면, 바로 induction의 앞 단계에서, n = k 일 때, 진부분집합과 어떤 일대일 대응도 없다고 했기 때문이다.

이제 나머지 한 쪽만 보이면 된다. 증명에서 남은 부분은 X 가 어떤 집합 Y의 진부분집합일 때, X $\nsim$ Y 를 보이는 것이다. 우리는 이미 앞에서 Y 가 X의 진부분집합이면 X $\nsim$ Y 인 것을 확인했다. Y 가 X의 진부분집합이면 Y는 유한집합일 수 밖에 없다. 그렇다면 이 문제는 X 와 Y를 바꿔쓰기만 할 뿐, 같은 말이다. 증명 끝.

위 문장의 역이 참인 것이 분명하다. 따라서 우리는 여기서 유한 집합의 경우 '집합의 대등성'은 집합의 원소의 일치(같음) 와 아주 닮았다는 것을 알 수 있다.

이제 우리가 흔히 말하는 '원소의 개수'에 대하여 이야기 해보자. 우리의 직관과 어긋나지 않는 수학적 정의는 어떤 것이 있을까? 유한 집합의 정의에서 이미 상당히 드러났다. {2, 3, 5, 7} 은 ${\bar {4}}$ 와, 그리고 집합 { 300, 500, {300, 500} } 은 ${\bar {3}}$ 과 세기가 같다 (대등하다). (왜 그런가?) 직관적인 원소의 개수 개념과 맞아 떨어지는 듯 보인다. 하지만 아직 충분하지 않다. 왜냐하면 {2, 3, 5, 7} 이 ${\bar {4}}$ 로만 일대일 대응해야 하나? { 300, 500, {300, 500} } 이 ${\bar {3}}$ 이 아닌 다른 ${\bar {n}}$ 과 대등하지 않다고 말할 수 있는가? 원소의 개수라는 뜻을 살리려면, 집합마다 고유한 n 이 보장되어야만 한다. 그래야 일대일 대응이라는 '집합의 세기' 개념으로 유한집합의 '크기'까지 포괄하는 개념이 될 수 있는 것이다.

다음 정리는 그럴 수 밖에 없다는 것을 보여준다. 따라서 우리의 유한의 정의는 충분히 괜찮은 정의였다는 것을 알 수 있다.

(정리2) X 가 유한집합일 때, ${\bar {n}}\sim$ X 인 n 은 유일하다.

자, 그렇다면 유한 집합은 어떤 '하나의 자연수'로 대응한다는 것이 밝혀졌다. 어떤 유한집합은 꼭 하나의 자연수로 대응한다. 아주 좋다. 그 대응 규칙을 | | 라고 하자. 그러면 그에 따라 정의를 할 수 있는데,

정의(원소의 개수) :

{\bar {n}}\sim

X 이면 그때의 n 을 X 의 원소의 개수라 한다.

기호로는 | X | = n 라 쓰자. 그렇다면 다음 성질은 분명하다.

X와 Y 가 모두 유한집합 일 때, X $\sim$ Y 면 | X | = | Y | 다.

아주 좋다. 그런데 지금까지 '원소의 개수'를 이야기하면서 무언가 빠뜨린 것은 없는가? 우리는 모든 유한 집합에 대하여 대응하는 자연수를 정의했는가? 그렇지 않다. $\emptyset$ 에 대하여 빠뜨렸다. (정리 2) 에서도 X 가 $\emptyset$ 이 아니라는 전제를 붙여야 완벽해진다. 그리고, 원소의 개수를 나타내는 함수는 | | 은 더 확장되어야 깔끔해진다.

|

\emptyset

| = 0

셀 수 있는 집합 (Denumerable Set)

우리는 집합의 세기 에서 보았지만, 우리가 흔히 만날 수 있는 많은 무한 집합들은 자연수 집합과 일대일 대응을 찾을 수 있다.

정의 (셀 수 있는 집합) : 자연수 집합과 일대일로 대응하는 집합을 셀 수 있는 집합이라고 부른다.

따라서 자연수 집합과 하나씩 짝지을 수 있는 알고리듬을 찾느냐하는 문제가 관건이다. 물론 모든 개별적인 문제에서 그것을 찾기란 쉽지 않다. 예를들어 '자연수 집합'과 '소수집합'의 일대일 관계를 찾아본다고 생각해보라. (지난 수백년 동안 이 알고리듬을 찾고 있긴하다. 과연 그것이 찾아질까 ?)

셀 수 있는 집합은 무한집합에서 아주 특별한 지위를 갖는다. 셀 수 있는 집합들은 어떤 성질을 가질까? 증명없이 주요 정리들을 나열하겠다. 스스로 증명해보기 바란다. 다음 두 정리는 유한 집합 바로 다음이 셀 수 있는 집합이라는 것을 말해준다. 다시 말해 무한집합에서 가장 작은 집합은 셀 수 있는 집합이다.

정리 : 셀 수 있는 집합에 포함되는 집합은 유한집합이거나 셀 수 있는 집합이다.

정리 : 어떤 무한집합도 셀 수 있는 집합을 포함한다.

그렇다면 모든 셀 수 있는 집합을 합해가면 그 집합은 어떻게 될까? 언젠가는 셀 수 없는 집합이 될까? 다음 성질은 셀 수 있는 집합에 유한집합을 합하거나 셀 수 있는 정도의 무한 집합을 합할 경우, 연산의 결과 얻은 새로운 집합은 셀 수 있는 집합일 뿐이라는 사실을 말해준다.

정리 : X 가 셀 수 있는 집합이고 Y 는 유한 집합이거나 셀 수 있는 집합이라 하자. 그러면 X $\cup$ Y 는 셀 수 있는 집합이다.

앞의 정리는 보다 일반적으로 다음과 같이 나타낼 수 있다.

셀 수 있는 집합들의 어떤 집합이 셀 수 있는 집합이면 그 원소들의 합은 셀 수 있는 집합이다.

셀 수 있는 집합의 예 : 위에서 말한 셀 수 있는 집합들의 성질을 써서

{ (n , m) | n , m 은 자연수 }
$\mathbb {N} \times \mathbb {N} \times \mathbb {N} \cdots \times \mathbb {N}$
한국어로 만들 수 있는 모든 단어와 문장의 집합
한 때 나마 존재하는 모든 별들의 집합
순환마디가 있는 소수들의 집합

셀 수 있는 집합에 대한 성질은 무척 많지만, 마지막으로 하나만 더. 셀 수 있는 집합은 어떤 무한집합의 '세기'를 변화시키지 않는다.

정리 " 무한 집합 X 에 셀 수 있는 집합 A 을 합한 X $\cup$ A 집합은 X 와 대등하다.

다음 성질은 무한집합과 유한집합에 새로운 정의를 가능하게 한다. (어느 한 부분을 증명하면 나머지도 증명된다. 증명해보라. )

정리 : 어떤 무한집합이든 대등한 진부분집합이 있다. 유한집합은 그렇지 않다.

무한집합이면 대등한 진부분집합이 있고, 무한집합이 아니면 대등한 진부분집합이 없다고 했으니, 이는 무한과 유한 집합을 대등한 진부분집합이 있고 없음과 논리적으로 등가라는 것을 말해준다. 따라서 이 성질은 처음에 우리가 내린 유한과 무한의 정의에서 자연수 개념을 버리도록 해준다.

정의 (유한과 무한): 그 자신의 진부분집합과 대등한 집합을 찾을 수 있으면 그 집합은 무한 집합이다. 그렇지 않으면 그 집합은 유한집합이다.

오로지 '포함 개념'과 '대등'개념만 필요하다. 대등 개념은 집합론적으로 정의한 함수의 개념에만 기대고 있다는 점에서, 처음의 정의였던 '자연수의 세계(산술세계)' 로부터 떠나 순수하게 집합론적으로 정의가 가능해진 것이다 !

셀 수 있는 집합이 아닌 집합들

그렇다면 무한 집합 중에서 셀 수 없는 집합이 있을까? 우리는 벌써 그런 예를 집합의 세기 를 보았다. 실수 집합, 어떤 특정한 실수의 구간, 0 과 1로 이루어진 무한개의 열을 가진 수들의 집합들 모두 그런 예다. 그리고 셀 수 없는 집합들은 '세기'의 관점에서 한가지 종류만 있을까? 아니면 셀 수 없는 집합들끼리 '대등하지않을 수 있을까? 더 나아가 가장 큰 세기를 갖는 집합은 무엇일까? 모든 집합을 원소로 갖는 집합, 바로 그렇게 '절대적으로 전체 집합'이 가장 큰 크기를 갖지 않겠는가?

다음의 정리는 위의 질문들에 대해 한꺼번에 답을 주는 성질이다. 용어하나를 정의하고 성질로 넘어가자.

정의 (Power Set) : 어떤 집합 X 에 대해서도 X 의 모든 부분집합들을 원소로 하는 집합을 X 의 Power Set 이라 하고 기호로

{\mathcal {P}}(X)

라 쓴다.

칸토르 정리 : 어떤 집합 X 에 대해서도 $X\ \prec \ {\mathcal {P}}(X)$ 이고 $X\ \nsim \ {\mathcal {P}}(X)$ 다.

이 정리는 집합 X 보다 P(X) 가 '더 크다'라는 것을 말하고 있다. 우리는 어떤 집합보다 '더 센' 집합들이 얼마든지 많이 있다 것을 알 수 있다. 따라서 가장 큰 무한 집합을 정할 수 없다 ! 그런데 바로 이 경이로운 정리 덕분에 집합론에 경종이 울린다. 모든 집합들을 원소로 갖는 '전체 집합 U '이 있다면 모순이 생긴다. 이를 '칸토르 파라독스' 라고 부른다. 상식적으로 생각하면 모든 집합들을 원소로 갖는 집합은 있는데, 있으면 모순이 생기는 것이다.

칸토르 파라독스 :

U\ \prec \ {\mathcal {P}}(U)

이고

{\mathcal {P}}(U)\ \nsim \ U

이면서, 동시에

{\mathcal {P}}(U)\ \prec \ U

앞부분은 칸토르 정리에 따라 자명하고, 전체집합 U 에 대해 P(U) 는 어쨌든 어떤 집합이므로 P(U) 는 U 에 포함되기 때문에 자명하다.

따라서 다시 집합의 정의로 돌아가야 할 것 같다. 집합이란 도대체 무엇인가? 이런 고민의 결과가 공리론적 집합론을 낳게 되는 결과를 낳는다. 그 시스템에서는 러셀 파라독스을 일으키는 집합이나 전체집합과 같은 개념은 애초에 불가능하다.

Cardinal Number

그럴 때 집합이 어떤 원소를 포함하고 있는지에 대해서는 무시하고 $\sim$ 의 기준으로 보아 모든 집합을 대등한 집합들 끼리 구분지을 수 있다. 칸토르는 그런 대등한 부분 집합들을 수로 불렀는데 이것이 바로 'Cardinal number'라고 한다. 이것은 대단히 추상적인 개념으로 다시 정의해보면,

정의 : 어떤 집합

A

와 대등한 모든 집합의 공통된 성질을

A

Cardinal Number라 한다.

다시 말해 $A\sim B$ 가 이면 집합 $A,B$ 는 같은 Cardinal Number를 갖는다.

따라서, 정의대로, 모든 셀 수 있는 집합은 같은 cadinal number 를 가질 것이다. 그것을 보통

\aleph _{0}

나

\omega _{0}

를 쓴다.

우리는 $\omega _{0}$ 를 쓰겠다. 앞에서 보았듯이 실수 집합만 해도 자연수 집합 보다 '세다'. 실수 집합의 cardinal number 를

\omega _{1}

로 하자. 일반적으로

X\prec {\mathcal {P}}(X)

이므로, cardial number 도 끝없이 많다. 그렇다면 이것을 자연수부터 시작해서 써보면

\omega _{0},\ \omega _{1},\ \omega _{2},\ \omega _{3},\dots

이제 우리 앞에는 새로운 수들이 있다. 이 수들 사이의 관계나 연산을 정의할 수 있고, 그렇다면 수들의 세계(cadinal number arithmetic) 가 열린 셈이다. 무한들의 셈이라고 할 수 있다. 몇가지 성질만 보도록 하자. 지금부터 나오는 '그리스 문자'는 어떤 cardinal number 라고 이해하면 된다. 아래에서 ('+, =' 은 무슨 뜻일까?)

\omega _{0}+n=\omega _{0},\ \omega _{0}+\omega _{1}=\omega _{1},\ \omega _{1}+\omega _{2}=\omega _{2}

\omega _{0}+\omega _{0}=\omega _{0},\ \omega _{1}+\omega _{1}=\omega _{1},\ \omega _{2}+\omega _{2}=\omega _{2}

위의 경우는 '합'의 특수한 경우였다면 아래는 더하기 셈의 가장 기초적인 성질이다. 이 성질은 집합의 '합' 연산에서 비롯된다.

\alpha +\beta \ =\ \beta +\alpha \,\qquad \ \alpha +(\beta +\gamma )\ =\ (\alpha +\beta )+\gamma

집합 이야기의 틀 로 돌아가기

Note