1. 함수의 종류

집합끼리의 크기를 비교할 때 함수의 개념을 이용하면 좀 더 명확하게 대소관계를 정의할 수 있습니다.

집합론에서 등장하는 대표적인 함수에는 3가지가 있습니다.

1.단사(Injective)함수

a65618aa071eb553a6333e4d58c12a3a860554671e736e2a2153

공역의 임의의 원소에 대응되는 정의역의 원소가 한 개 이하인 함수를 말합니다. 고교과정에서는 일대일함수라는 표현으로 사용됩니다.

2.전사(Surjective)함수

a17d34aa071eb553a6333e4d58c12a3ad070959fe5b70e8b2edc

공역의 모든 원소가 적어도 한 개 이상의 정의역의 원소에 대응되는 함수를 말합니다. 다시 말해 공역과 치역이 일치하는 함수입니다.

3.전단사(bijective)함수

24b0d121e0edb77a86e85969ff9f34334d482c7ae09dd9295c73e9

공역의 모든 원소가 정의역에 대응되는 동시에 두 개 이상 대응되지 못하는 함수를 말합니다. 전사함수와 단사함수의 조건을 모두 만족시키는 함수입니다.

고교과정에선 일대일대응이라 표현됩니다.


그림에서 확인할 수 있으시겠지만, 정의역과 공역 사이의 함수의 종류에 따라 두 집합의 대소관계가 달라짐을 알 수 있습니다.


단사함수(○),전사함수(×)-> 정의역<공역

단사함수(×),전사함수(○)-> 정의역>공역

단사함수(○),전사함수(○)-> 정의역=공역(전단사함수)


따라서 우린 임의의 두 집합이 어떤 함수관계를 맺느냐를 파악함으로써 집합의 크기비교를 할 수 있습니다.


2. 집합과 멱집합의 관계


멱집합은 특정 집합의 모든 부분집합을 원소로 갖는 집합족의 일종입니다.

예를 들어 집합 A를 A={a,b,c}라 정의하면, A의 멱집합은 P(A)={{a},{b},{c},{a,b},{b,c},{a,b,c}} 가 됩니다.


그렇다면 집합과 그 멱집합 사이의 대소관계는 어떻게 될까요? 위와 같은 유한집합의 예시의 경우 멱집합의 원소의 개수는 원래 집합의 원소의 개수+해당 집합으로 만들 수 있는 조합의 수이기 때문에 멱집합쪽이 크다는 것은 자명해 보입니다. 그렇다면 무한집합에서는 어떨까요? 기존 집합으로 조합을 만들어봤자 이미 집합의 크기가 무한이니 의미없을 것 같기도 하고, 그렇다면 무한집합에선 두 집합의 크기가 같은 걸까요?

결론부터 말하자면 그렇지 않습니다.

무합집합으로 멱집합을 취할 시 그보다 더 큰 무한집합을 만들 수 있습니다. 왜 그럴까요?

이를 증명하기 위한 직관적인 방법으로는 대각선 논법이 있습니다.

09b4d121eadc39aae16309b404d63130201728800840e22d698551357f89adc6cf633365fb321e00ed7876c80a8ccc8f8f

위 동영상에서 직관적인 방식에 대해선 훌륭한 설명을 제시하고 있으니 엄밀한 증명을 원하지 않으시는 분은 위 동영상을 참고해주시고


우린 엄밀한 증명법에 대해 논해보도록 하겠습니다.

자, 앞서 밑밥으로 깔아뒀던 함수의 개념을 이용할 차례입니다. 임의의 집합을 X라 놓겠습니다. X의 멱집합은 P(X)입니다. 앞에서 보았다시피 두 집합의 크기가 같으려면 두 집합 사이 전단사함수관계가 성립해야 합니다. 즉, 우리가 집합보다 그 멱집합이 크다는 것을 보이려면 X에서 P(X)로의 전단사함수가 존재하지 않는다는 것을 보이면 됩니다.

우선 전단사함수 f:X->P(X)가 존재한다 가정해봅시다.

그 다음 X의 부분집합 중 그 원소가 P(X)의 원소가 아닌 집합을 G라 정의하겠습니다.

조건제시법으로 나타내면 다음과 같습니다.

G={g∈X: g∉f(g)}⊆X

이때, f는 전사(surjective)하기 때문에 임의의 g∈X에 대하여 f(g)=G가 성립합니다.

이제 두 가지 가능성이 생깁니다. g∈G 또는 g∉G.

1.g∈G의 경우

G의 정의에 따라 g∉f(g)=G(모순)

2.g∉G의 경우

G의 정의에 위배되므로 g∈f(g)=G(모순)

두 가지 경우 모두 모순입니다.

가정에서 모순이 귀결될 경우 모순은 무조건 거짓이므로

가정 역시 거짓입니다. X와 P(X) 사이의 전단사함수는 존재하지 않습니다.

다시 말해, 집합과 멱집합의 크기는 같지 않습니다. 


칸토어는 다음과 같은 방법으로 X<P(X)임을 증명해냈습니다. 여기서 우린 또다른 질문을 던질 수 있습니다. 멱집합을 통해 끊임없이 더 큰 집합을 구성할 수 있다면, 모든 집합을 포함하는 진정한 전체(Universal)집합 U는 존재할까? 결과적으로는 그렇지 않습니다. U의 멱집합 P(U)를 정의할 시 칸토어의 정리에 따라 U∈P(U), 그러나 P(U) 역시 정의상 모든 집합에 포함되므로 P(U)∈U 역시 성립합니다. 두 집합이 양방향함의이므로 동치관계, 즉 U=P(U)라는 결론에 도달하고, 이는 칸토어의 정리에 위배됩니다.

물론 NBG집합론에 따르면 전체 집합은 존재하지 않지만, 전체 모임은 존재합니다. 고유 모임이라는 속성 때문인데, 주제로부터 멀어지는 것 같으니 이에 대해선 다음에 작성해보는 걸로 하고..


결론: 함수의 개념을 통해 집합의 크기를 엄밀하게 비교할 수 있다, 임의의 집합의 멱집합은 가산,비가산을 막론하고 해당 집합보다 크다, 전체 집합은 존재하지 않는다

이상입니다.

- dc official App