멱집합과 실수와 자연수 집합의 크기 관계 Power set and relationship between magnitude of real number and of natural number

이전 포스트에서 무한의 크기를 알아봤는데,

실수와 자연수 집합 크기의 관계를 규명하고자 글을 쓴다.

 

이 관계를 규명하기 위해서

멱집합( Power set )을 이용한다.

그래서 멱집합에 대해 먼저 얘기해보겠다.

 

집합 A가 있다고 하자.

그러면, A의 부분집합이 있을건데,

집합 A의 부분집합을 모아놓은 집합이 멱집합이다.

부분집합의 수는 해당 집합의 멱집합의 크기와 같다고 할 수 있다.

 

멱집합의 크기는 어떻게 정할 수 있을까?

이걸 얘기하기 전에 함수관계 수를 얘기하도록 하겠다.

 

f : A -> B 가 있으면,

A와 B의 연결을 여러가지 방식으로 할 수 있을 것이다.

A에 있는 원소 a가 B에 있는 원소 아무 곳에나 갈 수 있기 때문에,

이 경우에 대한 수는 B의 크기와 같을 것이다.

A의 다른 원소들도 마찬가지 이므로,

조합의 수는 각각 곱해야 된다.

각 경우에 대해 수형도를 그려보면 알 수 있을 것이다.

그러면, f의 함수 관계의 수는 

(n(B))^(n(A))

이렇다.

A가 3개이고, B가 4개이면, 

3^4=81 개의 함수를 만들 수 있다는 얘기다.

 

멱집합 얘기로 돌아와서

부분집합은 해당 집합의 원소를 넣느냐, 안 넣느냐로 결정되므로,

부분집합에 대한 표현은 

해당 집합과 S={넣는다, 안 넣는다} 집합의 함수 관계로 만들 수 있다. 

집합 A와 S의 함수를 만들 수 있는 함수의 수는

(n(S))^(n(A))

n(S)=2 이므로,

2^(n(A))

가 된다.

따라서 A의 멱집합의 수는 2^(n(A)) 개가 된다.

 

 

멱집합과 해당 집합의 크기는 어떻게 될까?

A의 멱집합을 P(A)라고 하자.

P는 멱집합( Power set)의 머리글이다.

 

f : A -> P(A) 함수가 있다고 하자.

f(x)={x} 라고 하면,

f는 일대일 함수가 된다.

 

f가 전사함수(surjection)가 될 수 있는지 알아보자.

 

단순하게 생각할 수 있는 한가지는

 

f(x)={ a는 A의 원소 l A의 원소 x는 포함되지 않음. }

 

f(x)를 이런 식으로 정해놓자.

예를 들어 f(a)={b,c,d} 이런 식이다.

f(a)에 a가 포함되지 않았지 않는가?

 

A는 f(x)가 될 수 없기 때문에,

f는 전사함수가 되지 않는다.

앞에서 f는 단사함수가 되기 때문에,

P(A)가 A의 수보다 많다는 결론을 얻을 수 있다.

 

다른 방식을 보자.

비슷하다.

 

우선 S를 아래와 같이정해보자.

 

S={ x는 A의 원소ㅣ x는 f(x)에 속하지 않음 }

 

S는 A의 원소로 이루어져 있으므로

A의 부분집합이다.

 

이 때, f(a)=S라고 하자.

a는 A의 원소

그러면 a는 S에 속하지 않는다.

그렇다면, S의 조건에 의해 a는 S에 속해야한다.

두 말이 서로 모순이 된다.

그래서 f(a)=S 인 a는 없다.

 

또, A의 원소 a가 S에 속한다고 하면,

조건에 의해 a가 S에 속하면 안된다.

서로 모순이다.

이 논증에 의해서도 f(a)=S인 a가 없음을 밝혔다.

 

A에 있는 어느 원소도 S에 대응되지 못하므로

f는 전사함수가 되지 못한다.

아까 단사함수는 된다고 했으므로,

P(A) 수는 A의 수보다 많다.

 

즉, n(A) < 2^(n(A)) 가 된다.

 

 

이건 자연수 집합에도 적용할 수 있다.

n(N) < 2^(n(N))

 

n(N)<n(R)인데,

n(R)과 2^(n(N))은 크기 비교가 가능할지를 알아보겠다.

 

그럴려면, f : P(N) -> R 로

f가 단사, 전사가 가능한지 검증하여 비교해야 할 것이다.

아니면, g : R -> P(N) 으로 하던지 말이다.

 

f : P(N) -> R

 

P(N) 과 동치인 집합은 h : N -> { 0, 1}의 함수 집합일 것이다.

이 집합을 { 0, 1} ^N 이란 이름을 붙이자.

 

k : {0,1}^N -> R 이란 함수가 있을 때,

 

k(h)=h(1)/p + ... + h(n)/(p^n) +... 라고 하면,

 

k(h)의 결과는 R의 원소이므로,

k는 단사함수가 존재하며,

2^(n(N))=< n(R)

이 성립한다.

 

이제 g : R -> P(N) 을 보자.

N과 Q(유리수)가 대등하므로,

P(N)과 P(Q)도 대등하다.

 

d : R -> P(Q) 를 알아보자.

 

d(r) = { a는 Q의 원소 l r<a, r은 R의 원소 }

 

이런 함수를 정해놓자.

d(r)은 실수 r보다 큰 유리수의 집합이라고 정한 것이다.

 

서로 다른 실수 x, y를 놓았을 때,

x< b <y 라고 하자.

이 때, b를 유리수라고 하면,

그러면, b는 d(x)의 원소이나,

d(y)의 원소는 아니게 된다.

 

x, y가 다르면, d(x), d(y)가 다르므로,

d는 일대일 함수가 된다.

 

n(P(N))=< n(R) =< n(P(Q)) 이고,

n(P(N)) = n(P(Q)) 이므로,

n(P(N))= n(R) = n(P(Q)) 이다.

 

결국 실수의 개수는 2^(n(N)) 과 같게 된다.

자연수의 멱집합 개수와 같은 것이다.