흔히 모든 실수의 집합이 uncountable임을 증명하는 데는 우선 R과 (0,1)을 일대일 대응시키고, 그 후에는 G. Cantor의 대각선 논법을 사용하여 증명함.


근데 이 증명을 들여다보면 실수의 십진전개법을 사용해서 증명하는데, 보통 실수하면 완비성공리를 처음 배우고 이게 정말 중요한 성질이라고 그러는 걸 생각해보면 이 방식은 완비성공리를 뭘 어떻게 사용했나 의문이 들거임. ('공리'라는 이름이 마음에 안 들면, (total) order가 Dedekind-complete하다고 말해도 됨. 같은 뜻임)


또한 집합론 공부하는데 갑자기 tangent가 나와서 얼떨떨해 하거나, 아니면 아예 R과 구간 (0,1)을 대응시키지 않고는 뭐 못하나 이런 의문도 종종 드는 것 같고. (결론부터 말하면 쓰는 걸 망설일 이유도 없고, 대응시키지 않고 증명하는 방법도 있음)


그래도 이 증명이 완비성공리를 암묵적이나마 사용하는 것이, diagonal pick들 가지고 만든 녀석이 정말로 실수임을 보장하는 녀석이 바로 완비성공리임. 하지만, 이것보다 더 명시적으로 완비성공리를 사용하고, 역사적으로도 Cantor가 위 증명보다 더 이전에 증명한 방식을 소개하려고 함.


그럼 이제 시작해보자. 결론을 부정하여 실수 전체의 집합 R이 countable이라고 가정하고, R={a_n : n in N}={a_0, a_1, a_2, ...}로 두자. (다시 한 번 말하지만 0은 자연수...ㅋㅋㅋ)


우리가 하고 싶은 건, 그 어느 a_n과도 같지 않은 실수가 존재함을 보이는 것임. 집합론에서 늘 써먹는 방식으로 출발할거임.

표기상 편의를 위해 n_0=0으로 둠.


a_0보다 큰 실수 a_k들의 집합을 생각할 수 있는데, 얘네들 중 index가 가장 작은 녀석이 있을 거 아님? 그 index가 n_1으로 잡음. 그럼 하나 알 수 있는 건 0보다 크고 n_1보다 작은 k에 대하여, a_k는 전부 a_0보다 작다는것임. 뭔가 "배제한" 느낌이 들면 좋은 거임. 우리의 목표가 모든 a_n을 "배제하는" 것과 관련이 있으니.


지금부터는 수고를 덜기 위해 a_(n_k)=b_k로 간략히 적겠음.


다음은 n_2를 잡아야 할텐데, 지금 b_0과 b_1이라는 bound가 생겼으니 여기 들어가는 녀석들을 생각하려고 함. 그렇다면 n_2는 b_0과 b_1 사이의 실수 전체의 집합을 생각하는데, 얘네들 중 index가 가장 작은 녀석의(여기서 말하는 index는 a_n으로 보았을 때 말하는 거임) index가 되는 것임. 그럼 또 알 수 있는 점, n_1보다 크고 n_2보다 작은 k에 대하여, a_k는 구간 (b_0,b_1) 바깥에 있다는 점임.


한 발 더 나아가자. b_2과 b_1 사이에도 실수가 있겠지? 이번에도 걔네들 중 index가 (여기서도 역시 a_n으로서의) 가장 작은 녀석이 있을 거고, 그 index가 n_3, 걔가 a_n_3=b_3가 되는 거임. 이번에도 n_2보다 크고 n_3보다 작은 k를 생각에 대해, a_k는 구간 (b_2, b_1) 바깥에 있음을 알 수 있음.


이걸 recursive하게 반복하여 subsequence (b_k)를 얻음. 이 친구의 특징은 크기가 마치 "진자처럼" 커졌다 작아졌다하는데, "진폭은 감소하는 중"임. 정확히 말하면


b_0<b_2<b_4<...와 b_1>b_3>b_5>... 이고, b_(2n)<b_(2n+1) for all n in N and b_(2n+1)>b_(2n+2) for all n in N이라는 뜻.


그럼 이제 할 일은, (b_(2k))의 supreme을 생각하는 것임. 이 subsequence가 유계임은 위에서 바로 확인할 수 있으니까 확실히 supreme이 존재하지. 이 요주의 실수를 x라고 하자. 이제 문제는, is there a natural number m satisfying a_m=x?


우리의 구성에서 알 수 있겠지만, 적어도 n_k (k는 자연수) 들은 후보 탈락임. 왜냐하면 이 indices에 대응하는 실수는 b_k인데, 얘네는 확실히 x, (b_(2k))의 상한이 될 수 없으니까. 그럼 n_k가 아닌 녀석들은 어떨까? 얘네들 역시 곤란한 것이, 우선 n_0=0보다 크고 n_1보다 작은 자연수 k에 대해 a_k는 a_0보다 작으므로 후보가 될 수 없음.


k>0인 경우, n_k보다 크고 n_(k+1)보다 작은 자연수 j들에 대해서도 답은 부정적임. 왜냐하면 그런 j에 대해, 우리는 이미 a_j가 (b_(k-1), b_k) (만약 대소관계가 역전된다면, 뒤집어서 생각) 안에 있지 않음을 알고 있음. 근데 둘 중 하나는 index가 홀수니까 상계이고, 하나는 문제의 수열의 항이니까, a_j는 계속 고려 중인 상한, 즉 x가 될 수 없음.


이제 우리 목표가 완성됨. x는 어느 자연수 n에 대해서도 a_n과 같을 수 없고, 따라서 가정은 잘못되었고, R은 uncountable임.


여기서 우리는 R의 특성 중 R이 Dedekind-complete하다는 사실만 사용했고, 따라서 이 증명은 Dedekind-complete한 모든 total order에 대해 적용될 수 있음.


지금까지 이렇게 R이 uncountable함을 살펴 봤는데, 사실 Baire category theorem을 쓰면 단 세 줄만에 끝나는 일임.


R is a complete metric space, so cannot be represented as the countable union of closed sets with empty interior by Baire category theorem.


Every singleton is not open but closed, so it is a closed set with empty interior.


Hence R is uncountable.


물론 R이 complete metric space라는 증명, Baire category theorem의 증명은 단 세 줄 만에 끝내기엔 아주 어렵지 않을까 생각함.