집합론의 역설

소박한 집합론에는 몇 가지 흥미로운 역설이 있는데, 이 역설들 때문에 결국 더 엄밀한 집합론이 만들어졌다. 이런 역설은 대개 고전적인 소박한 집합론에서 집합이 자기 자신을 원소로 가질 수 있다는 사실에 기대고 있다.

러셀의 역설

가장 유명한 역설 가운데 하나가 러셀의 역설이다. 다음과 같이 정의할 수 있다. 자기 자신을 원소로 갖지 않는 집합만을 모두 원소로 갖는 집합 N이 있다고 하자. 즉 어떤 집합이 자기 자신을 원소로 가지면 집합 N에 속하지 않는다. 자기 자신을 원소로 갖지 않으면 집합 N에 속한다.

그렇다면 집합 N은 집합 N, 즉 자기 자신을 원소로 가질까?

경우를 나누어 따져 보면 다음과 같다. 집합 N이 N을 원소로 갖지 않으면, 이 집합은 자기 자신을 원소로 갖지 않는 집합이므로 집합 N에 속해야 한다. 즉 N ∈ N이 성립해야 한다.

그런데 집합 N이 원소 N을 가지면 N ∈ N이 성립하면 안 된다. 집합 N은 자기 자신을 원소로 갖지 않는 집합만을 원소로 갖기 때문이다.

역설은 어느 쪽이든 조건 하나를 어기게 된다는 데 있다. N ∈ N이면 집합 N의 정의(자기 자신을 원소로 갖지 않는 집합만을 원소로 갖는다)에 어긋나고(여기서는 분명히 N이 N을 원소로 갖는다), N ∈ N이 성립하지 않아도 역시 N의 정의에 어긋난다.

따라서 이런 집합은 만들 수 없는데, 올바른 집합론에서는 이런 일이 일어나면 안 된다.

러셀의 역설은 일상적인 말로도 나타낼 수 있다. 예를 들어 이발사의 역설이 있다. 어느 마을에 이발사가 있는데, 이 이발사는 스스로 면도하지 않는 사람만을 모두 면도해 준다. 그렇다면 이발사는 스스로 면도할까?

칸토어의 역설

또 다른 역설은 칸토어의 역설이다. 이 역설은 집합 M이 있으면 그 멱집합 P(M)(집합 M의 모든 부분집합의 집합)의 기수가 언제나 더 크다는 사실에 기댄다. 유한집합에서는 한눈에 알 수 있고, 무한집합에서도 쉽게 증명할 수 있다. 이 명제를 칸토어의 정리라고 하며, 정확한 내용과 증명은 위키백과에 있다.

역설 자체는 앞의 것보다 간단하다. 모든 집합의 집합을 생각하고, 이것을 M이라고 하자. 즉 어떤 집합 N에 대해서도 N ∈ M이다. 그런데 칸토어의 정리에 따르면 멱집합 P(M)의 기수는 M의 기수보다 크다. 이는 M이 모든 집합을 원소로 갖는다는 것과 모순이다. 집합 P(M)이 M보다 크다면 M에 없는 원소를 반드시 가져야 하기 때문이다.