[Section 2] 칸토어의 대각선 증명과 러셀의 역설

대수학 목차 보기

[INTRO] 대수학 미리보기

0. INTRO

어렸을 때 우리는 무한한 수, 무한한 우주에 대한 상상을 끊임없이 해왔다. 정말 우주는 무한할까? 수는 끝이 없을까? 누구나 한 번쯤 어렸을 때 해왔을법한 상상이다. 칸토어는 집합을 통해서 무한한 수에 대한 연구를 한 수학자이다. 그는 대각선 증명법을 이용하여, 실수는 셀 수 없는 집합임을 대각선 증명 방법을 이용해서 증명하였다. 그의 증명 방법과 더불어 러셀의 역설에 대해 알아보자. 

1. 칸토어의 대각선 증명 방법

칸토어는 집합을 '크기' 관점에서 기수라는 개념을 이용하여, 자연수의 기수를 '알레프-제로'로 나타내어 임의의 집합 x의 기수를 알레프 제로와 비교하여 가산 이하, 가산, 초한수 그리고 무한한 성질로 기수를 분류하였다. 그는 알레프 제로 이하의 기수를 가지는 집합은 모두 유한하다고 정의하고, 자연수를 포함하는 유리수와 실수에 대해서도 대각선 증명방법을 이용하여 셀 수 있거나 셀 수 없음을 증명하였다. 

A. 유리수 집합(The set of rational numbers)

유리수는 자연수를 포함하는 수이며 동시에 0이 아닌 정수를 분모로 가지는 분수 형태의 수 또한 포함하는 수의 집합이다. 그렇다면 자연수 집합을 포함하는 수 집합이니까 유리수 집합은 유한하지 않은 것이 아닌가? 이 질문에 대한 대답은 "Yes, it is countable"이다. 칸투어는 대각선 증명방법을 이용하여 유리수 집합이 셀 수 있음을 증명하였다. 

 

양의 정수를 A, 유리수 집합을 B로 정의하여, 다음과 같이 비교해보자.

 

유리수는 가산 집합?

 

유리수가 가산 집합이기 위해서는 알레프 제로와 그 크기가 같거나 더 작아야 한다. 칸토어는 대각선 증명방법을 이용하여 다음과 같이 유리수 집합의 기수는 알레프 제로와 같음을 증명하였다.

 

유리수는 가산 집합

 

자연수는 대각선으로 표시되고, 어떤 유리수 집합에 있어, 두 자연수의 집합과 전단사 관계를 만들어 내는 것을 대각선을 이용하여 증명하였다.

B. 실수 집합(The set of real numbers)

유리수와 달리, 실수 집합은 셀 수 없음이 칸토어의 두 번째 대각선 증명방법을 통해 증명되었다. 

칸토어의 방법으로 실수(real numbers)는 셀 수 없는 집합임을 입증해보자. 

 

(a); 0과 1사이의 실수 집합을 A라 할 때, A와 일대일 대응인 집합 B가 있다고 가정하고,

집합 B의 원소를 다음과 같이 정의하자. 

 

증명 과정 (a)

(b); 실수는 위와 같이 무한한 소수(infinite decimals)들로 표현되었다. 이 무한한 소수가 만드는 집합과 일대일 대응 관계를 이루는 어떤 집합 b'가 존재한다고 가정한다. 

 

소수점의 각 수는 0과 9를 포함하고 그 사이의 있는 수로 표현될 수 있다. 그렇다면, 이제 0과 1 사이에 존재하는 새로운 실수 집합 b'를 다음과 같이 만들어보자.

 

새로운 실수 집합, b'

 

(c); 새로운 집합 b'는 실수의 집합과 서로 연관성을 가지고 있다.

그 연관성이라 함은 b'의 원소와 b집합의 대각선 원소 성분과의 연관성을 말한다. 각각의 대각 성분이 1이면 2로 대치되고 대각 성분이 1을 제외한 0부터 9까지의 수이면 1로 대치된다. 이렇게 구성된 b'는실수이지만, 항상 b 집합의 원소에는 없는 새로운 원소를 만들 수 있다. 

 

(d) 위의 해석에 따라서 0과 1 사이에 존재하는 실수는 일대일 대응하는 함수를 만들 수 없고 가정은 잘못된 가정임이 증명된다. 칸토어의 증명에 따라 우리는 실수 집합을 셀 수 없는 집합으로 분류한다. 

 

 

2. 러셀의 역설과 선택 공리

칸토어의 증명과정은 러셀의 역설과 같은 핵심적인 내용을 이야기하고있다. 바로 어떠한 집합을 원소로 가지는 집합에 대한 자기 참조는 모순을 낳는다는 역설이다.

 

예를 들어, 다음과 같이 어떤 유한한 집합 x의 멱집합을 Px라고 하자. x의 기수를 X̃라 할 때, 멱집합의 기수는 (1)로 명시하고, 다음의 조건(2)을 항상 만족한다. 그렇다면 이는 무한한 집합 x에 대해서도 성립할 것이다.

 

조건 (1), (2)

 

다음과 같이 자연수 멱집합의 기수를 (1)로 명시하고, 전체 집합(universal set)에서 부분 집합 A를 만들면, 위에서 명시한 바와 같이 조건(2)를 명시할 수 있다. 하지만, 멱집합 PA는 집합 A의 하위 집합과 서로 동등한 관계를 가져야 하므로 조건 (3) 또한 만족해야 한다. 조건(3)과 조건(2)은 서로 역설을 낳는다.

 

조건 (1),(2),(3)

 

A. 폰노이만의 선택 공리(axiom of comprehension, AC)와 모임(class)

함수 f(x)가 집합을 원소로 가지는 것으로부터 기인한 '임의의(arbitrary) 특성들'로부터 발생하는 것으로 보인다. 역설을 제외하기 위해서, 집합론은 선택 공리를 따르는 것으로 공리계를 제한하였다. 이것은 x, y, z.. 라 불리는 모임들(classes)을 원소로 정의하고 원소들 사이에서 두 자리 관계(two-place relation)인 ∈를 존재할수 있다고 본다. 즉, x∈y는 '어떤 모임 x가 어떤 모임 y의 원소이다'라고 정의한다. 모임과 원소의 공식적 차이는 없고, 특정한 모임들을 집합이라고 정의했는데, 그 집합들은 적어도 하나의 모임의 원소들이다.

 

모임의 정의에 따라서, 술어 명제 Hx는 다음의 명제와 동치이다. 

 

"Hx ⇔ ⋁_u x∈u"

 

B. 모임간의 동등성(equality) 정리

모임을 정의함에 따라서 모임 간의 동등성을 정의해야 한다.

(1); 만약 두 모임이 같은 원소들을 가지며, (2); 둘 중 하나가 어떤 한 모임의 원소가 되면, 나머지 다른 모임이 그 모임의 원소가 되는 것으로 두 모임을 같은 모임으로 간주한다. 예를 들어, 두 모임 a와 b가 있다고 하자.

 

그러면, a=b라는 것은 다음의 명제와 동치이다. 

 

"⋀x(x∈a ⟷ x∈b)^⋀x(a∈x⟷b∈x)"

 

(1)과 (2)의 정리에 따라서 임의의 모임은 완벽하게 모임들의 원소에 의해서만 결정된다. 

 

C. 모임으로 제한된 집합 정리

순수 집합 정리에서 명시한 확장성의 원리는 같은 집합(a=b)을 다음의 명제로 나타낸다.

 

"⋀x(x∈a ⟷ x∈b)⟶a=b)"

 

만약 술어 명제 H(x)가 다음의 함수 기능을 한다고 가정하자.

 

"x∈x or x∈y or x∈z"

 

그렇다면, 선택 공리(AC)의 제한은 다음의 명제로 나타낸다. 

 

"⋀x(H(x)⟶Mx)⟶⋁u⋀x(x∈u⟷H(x)))"

 

여기에서 u는 종속 변수이다. 

 

AC의 제한으로 술어 명제 H(x)는 베타적으로 집합이 어떤 모임의 원소가 될 수 있는 모임들로 한정된 경우에만 하나의 모임을 정의할 수 있다. 따라서, H(x)에 의해 정의된 모임은 확장성의 원리에 따라 유일하게 결정된다. 선택 공리를 따르는 집합론은 러셀의 역설인 자기 참조 모순을 일으키지 않는다.