집합론(Set theory)

칸토어의 대각선 논법(Cantor's diagonal argument)

0과 1의 무한한 줄들을 어떻게 나열해도, 대각선의 숫자를 모두 뒤집으면 목록에 없는 줄이 나온다. 그래서 실수⁠(real number)⁠는 셀 수 없다.

s^*_k = 1 - s_{k,k} \;\Rightarrow\; s^* \neq s_k \;\;(\forall k)

먼저 보면 좋은 개념가산 집합

자연수⁠(natural number)⁠에 1번, 2번, 3번, … 번호를 붙이듯, 0과 1 사이의 실수에도 번호를 붙여 하나도 빠짐없이 늘어놓을 수 있을까요? 이렇게 1번, 2번, 3번, …으로 번호를 붙여 빠짐없이 늘어놓을 수 있는 집합⁠(set)⁠을 셀 수 있다(가산)고 합니다. 짝수 전체나 분수 전체처럼 끝없이 많은 집합도 셀 수 있으니, 실수도 그럴 것 같습니다. 칸토어는 답이 '아니요'임을 보였습니다. 어떤 목록을 내밀어도 그 목록은 반드시 무언가를 빠뜨린다는 것입니다.

실수 대신 0과 1로 된 무한한 줄(이진 수열)로 시작합니다. 0과 1 사이의 실수는 이진 소수⁠(binary expansion)⁠ $0.b_1b_2b_3\ldots$ 로 쓸 수 있으니(진법⁠, positional notation⁠), 이진 수열의 목록은 실수의 목록과 거의 같습니다. '거의'인 까닭은 아래에서 다룹니다. 이제 이진 수열들을 모두 나열한 목록이 있다고 해 봅시다.

노란 테두리가 대각선, 맨 아래 빨간 줄 s*는 대각선을 뒤집어 만든 줄입니다. 칸을 누르면 그 줄과 s*를 비교합니다.

목록의 k번째 줄에서 k번째 숫자(대각선)를 읽고, 모두 뒤집어(0↔1) 새 줄 $s^*$ 를 만듭니다. 이 줄은 k번째 줄과 적어도 k번째 자리에서 다릅니다. 지금 번째 줄과 비교해 보면, 그러니 $s^*$ 는 목록 어디에도 없습니다. 새 목록을 몇 번 눌러 보세요. 목록이 무엇이든 매번 같은 일이 일어납니다.

흔히 '빠진 $s^*$ 를 목록 맨 앞에 넣으면 되지 않나?'라고 생각합니다. 그러면 새 목록이 생기고, 새 목록의 대각선을 뒤집으면 또 빠진 줄이 나옵니다. 이 논법은 특정한 목록 하나가 아니라 '어떤 목록이든'에 대한 것이라, 고친 목록에도 똑같이 적용됩니다.

가산 집합⁠(countable set)⁠이라면 모든 원소⁠(element)⁠를 담은 목록이 있어야 하니, 이진 수열의 집합은 가산이 아닙니다. 실수로 옮기려면 한 가지를 처리해야 합니다. 이진법⁠(binary)⁠으로 $0.0111\ldots$ 과 $0.1000\ldots$ 은 둘 다 ½이듯, 두 가지 이진 수열로 적히는 실수가 있습니다. 그래도 0 이상 1 이하의 실수 하나는 많아야 두 가지 수열로 적히고, 이진 수열은 모두 이 범위의 실수 하나를 나타냅니다. 그러니 이 범위의 실수를 목록으로 늘어놓을 수 있다면, 각 실수의 수열을(두 가지면 둘 다) 차례로 적어 모든 이진 수열의 목록도 만들 수 있습니다. 그런 목록은 없으므로 실수의 목록도 없습니다. 0과 1 사이의 실수는 자연수와 크기가 다른 더 큰 무한입니다.

이진 수열 하나는 "각 자연수를 넣을지 말지"를 적은 표이기도 합니다. 첫째 자리는 1을, 둘째 자리는 2를 넣을지 말지라고 하면, 1, 0, 1, 0, 0, 0, …은 {1, 3}을 뜻합니다. 그래서 같은 논법으로 자연수의 멱집합(부분집합⁠(subset)⁠ 전체)이 자연수보다 크다는 것도 나옵니다. 유리수⁠(rational number)⁠는 가산이니, 실수에서 유리수를 빼고 남은 무리수⁠(irrational number)⁠도 셀 수 없이 많습니다.

대각선 논법⁠(diagonal argument)⁠은 실수가 자연수보다 많다는 것만 알려 줍니다. 그 사이에 중간 크기가 있는지가 연속체 가설⁠(continuum hypothesis)⁠의 질문입니다. 오늘날 수학의 표준 공리⁠(axiom)⁠ 체계를 ZFC라 하는데, ZFC가 모순이 없다면 그 공리로는 연속체 가설을 증명할 수도 반박할 수도 없습니다. 1940년 무렵 괴델이 반박할 수 없음을, 1963년 폴 코언이 증명할 수 없음을 보였습니다.

칸토어가 실수를 셀 수 없음을 처음 보인 것은 1874년이고, 그때는 구간을 겹겹이 좁혀 가는 다른 방법을 썼습니다. 대각선 논법은 1891년 논문에 처음 나옵니다. 그는 같은 논문에서 이 논법으로 어떤 집합이든 그 부분집합 전체가 원래 집합보다 크다는 것을 보였고, 그래서 무한의 크기에는 끝이 없다는 결론에 이르렀습니다. 끝없이 많은 것을 다 모은 하나의 대상으로 다루는 이런 생각은 거센 반대를 불렀습니다. 크로네커는 유한한 절차로 지을 수 없는 대상을 수학에 들이는 데 반대했고, 이 다툼은 20세기 초의 수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠으로 이어졌습니다.

같은 대각선 뒤집기는 다른 곳에서도 모순을 만듭니다. 목록의 줄마다 자기 자신에 대한 답을 읽고 그것을 뒤집는 대상을 만드는 방식입니다. 모든 프로그램이 멈추는지 판정하는 알고리즘⁠(algorithm)⁠이 없다는 정지 문제⁠(halting problem)⁠는 "판정기가 자기에 대해 멈춘다고 답하면 영원히 돌고, 멈추지 않는다고 답하면 멈추는" 프로그램을 만듭니다. '자기 자신을 원소로 갖지 않는 집합들의 집합'이 모순을 낳는 러셀의 역설⁠(Russell's paradox)⁠도, "이 문장은 증명할 수 없다"고 스스로에 대해 말하는 문장을 만드는 괴델의 불완전성 정리⁠(incompleteness theorem)⁠도 모두 이 모양입니다.

더 알고 싶다면.

1969년 윌리엄 로베어는 이 논법들이 모두 같은 모양이라는 것을, 수학의 구조를 대상과 화살표로 다루는 범주론⁠(category theory)⁠의 정리 하나로 정리했습니다.
데이나 스콧은 함수⁠(function)⁠가 자기 자신을 인자로 받을 수 있는 계산 체계(람다 계산⁠(lambda calculus)⁠)에 수학적 뜻을 붙이려다, '원소가 둘 이상인 D에서 D로 가는 함수 전체는 D보다 많다'는 이 논법에 막혔습니다. 유한한 정보로 정해지는 함수만 모으면 이 벽을 피할 수 있다는 것이 영역 이론⁠(domain theory)⁠의 출발점입니다.

관련된 시대와 장소20세기 초 케임브리지

이 개념이 나오는 큰 생각무한을 다루는 법 자기 참조와 대각선

이 개념이 나오는 긴 글

집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다. 계산언어학 말을 세는 기계 문법은 규칙일까, 확률일까? 파니니의 문법에서 촘스키의 위계, 섀넌의 영어 엔트로피, 오늘날의 언어 모델까지. 타입 이론과 범주론 증명은 프로그램이다 러셀의 역설을 막으려던 '타입'이 프로그램의 실수를 막는 장치가 되었다. 명제를 타입으로, 증명을 프로그램으로 읽으면 둘이 규칙 하나하나까지 맞아떨어진다. 오늘날 수학자들은 그 사실로 컴퓨터에게 증명을 검사받는다. 게임과 증명 이기는 쪽이 존재한다 "이 판은 백이 이겼다"는 흑이 어떻게 두든 백에게 답이 있다는 말이다. 체스의 체르멜로 정리, ε–δ, 님의 이진법, 폰 노이만의 최소최대와 쌍대성, 논리의 한계를 재는 게임, 끝나지 않는 게임과 선택공리, 대화로 읽는 증명, 겨루며 배우는 신경망까지. 수학의 참을 두 사람의 게임으로 읽는다. 수학의 오류 틀린 증명이 만든 수학 틀린 증명은 흔하다. 드물게, "정확히 어디가 틀렸는가"라는 물음이 새 분야를 낳는다. 코시의 합 정리와 균등 수렴, 라메의 증명과 아이디얼, 켐프의 사슬, 푸앵카레의 회수된 논문과 혼돈, 프레게의 법칙과 러셀의 편지, 보예보츠키와 증명 보조기까지. 오류는 대개 서로 다른 두 가지를 하나로 여긴 자리에 있었다. 불가능성 정리 불가능의 증명 각의 삼등분, 5차방정식의 근의 공식, 모든 파일을 줄이는 압축, 멈춤을 판정하는 프로그램, 공정한 투표 규칙. 없다는 것은 어떻게 증명할까? 서로 먼 분야의 불가능성 증명들은 거의 모두 불변량, 세기, 대각선이라는 세 가지 무기 가운데 하나를 쓴다. 범주론 화살표만으로 본 수학 최대공약수와 교집합과 '그리고'는 같은 것이고, 화살표를 뒤집으면 최소공배수와 합집합과 '또는'이 된다. 무엇으로 만들었는지 묻지 않고 어떻게 이어지는지만 보는 언어로, '자연스럽다'는 말의 뜻, 관계만으로 대상을 알아보는 요네다의 생각, 함자로 본 연쇄법칙, 어디에나 있는 수반까지 사이트의 여러 분야를 가로지른다.

이 개념 위에 세워진 것

칸토어 집합 연속체 가설 러셀의 역설 정지 문제 자기 참조와 대각선

이 개념을 언급하는 페이지

집합의 크기
… 그렇다면 모든 무한은 같은 크기일까요? 아닙니다. 실수 전체는 어떻게 짝지어도 빠지는 수가 생기고(대각선 논법), 어떤 집합이든 그 멱집합은 원래 집합보다 엄격히 큽니다. 무한에도 크기의 층이 끝없이 있습니다. …
가산 집합
… 가산 개뿐입니다. 반대로 실수는 가산이 아닙니다. 어떤 목록을 만들어도 빠진 실수를 만들 수 있습니다(대각선 논법). 유리수는 가산이니, 실수에서 유리수를 빼고 남은 무리수는 셀 수 없이 많습니다. 길이로 재도 …
멱집합
… f(x)\} 은 어느 원소의 짝도 될 수 없습니다. 자연수의 경우 이것이 곧 무한 이진 수열에 대한대각선 논법입니다. 그래서 무한 위에 더 큰 무한이 끝없이 쌓입니다. 멱집합을 취할 때마다 크기는 엄격히 커집니다. …
칸토어 집합
… 2만으로 된 3진 수열이고, 2를 1로 바꾸면 모든 이진 수열과 하나씩 짝지어집니다. 그러니 칸토어 집합은셀 수 없는집합, 실수 전체와 같은 크기입니다. 또 k 단계에서 남은 조각 하나를 3^k 배로 확대하면 칸토어 …
무리수
… 1번, 2번, 3번, …으로 빠짐없이 번호를 붙일 수 있다는 뜻입니다. 유리수는 셀 수 있지만 실수는대각선 논법에 따라 셀 수 없습니다. 셀 수 있는 유리수를 실수에서 빼도, 남는 무리수는 여전히 셀 수 없습니다. …
진법
… 0.0222\ldots_3 처럼 한쪽 표기만 그래도 됩니다), 무한한 2진 전개들을 나열할 수 없다는 것이대각선 논법입니다. 0과 1 사이의 수를 두 배 하고 정수 부분을 버리는 규칙(0.3 → 0.6 → 0.2 → 0.4 …
연속체 가설
… 적습니다. \aleph 는 히브리 문자입니다. 이것이 가장 작은 무한입니다. 실수 전체는 그보다 큽니다(대각선 논법). 얼마나 큰지 적으려면 부분집합을 세는 셈이 쓸모 있습니다. 원소가 셋인 집합 {1, 2, 3}의 …
대수적 수와 초월수
… 마지막 높이에서 새로 나타난 근은 크게 그렸습니다. 확대해 볼 수 있습니다. 수 하나를 골라 봅시다. :실수는 셀 수 없고대수적 수는 셀 수 있으니, 초월수는 있을 뿐 아니라 셀 수 없이 많습니다. 길이로 재도 거의 전부입니다. …
측도 0
… 인 구간 2^d 개로 덮이고, 그 합은 , 곧 (2/3)^d \to 0 입니다. 그런데 칸토어 집합은셀 수 없습니다. 측도는 크기와 다른 잣대입니다. 이 집합 위에서만 오르는 칸토어 함수는 측도 0인 집합이 얼마나 …
러셀의 역설
… 데 없어 보였고, 그런 조건으로 집합을 만드는 것이 당시 논리학의 기본 원리였기 때문입니다. 이 논증은칸토어의 대각선 논법과 같은 모양입니다. 칸토어는 집합 A에서 멱집합으로 가는 어떤 함수 f도 모든 부분집합에 닿지 …
괴델의 불완전성 정리
… '참'을 '증명할 수 있음'으로 바꾸었기 때문에 모순 대신 증명의 한계가 나옵니다. 행과 대각선을 뒤집는대각선 논법의 후손이기도 합니다. G의 부정도 증명되지 않음을 보일 때 괴델은 조금 더 강한 가정인 ω-무모순성을 …
튜링 기계
… 가산개뿐이고, 자릿수를 계산해 낼 수 있는 실수도 가산개뿐입니다. 그런데 실수는 셀 수 없이 많으므로(대각선 논법) 나머지 셀 수 없이 많은 실수는 어떤 기계로도 자릿수를 계산해 낼 수 없습니다. 튜링의 1936년 논문 …
정지 문제
… 멈춘다면 H가 '멈춘다'고 답했을 테니 D는 영원히 돌아야 하고, 멈추지 않는다면 곧바로 멈춰야 합니다.칸토어의 대각선 논법에서 뒤집은 대각선이 목록에 없는 실수를 만들었듯, 여기서는 목록에 없는 프로그램을 만듭니다. ⟦러셀의 …
람다 계산
… 항이 함수이면서 인자라서 값의 집합 D가 D에서 D로 가는 함수 전체와 같아야 하는데, 원소가 둘 이상이면대각선 논법이 그것을 막기 때문입니다. 1969년 데이나 스콧은 연속 함수만 모으면 된다는 것을 보여 이 문제를 …
촘스키 위계
… 반면 언어는 Σ*(Σ의 글자로 만들 수 있는 모든 유한 문자열의 집합)의 부분집합이라 멱집합만큼, 곧대각선 논법에 따라 셀 수 없이 많습니다. 따라서 어떤 문법으로도 적을 수 없는 언어가 셀 수 없이 많고, 문법으로 …
수 체계: 자연수에서 실수까지
… 양수여도 그 사이에서 0이 되는 점이 없습니다. ℕ ⊂ ℤ ⊂ ℚ는 모두 셀 수 있는 무한이지만 ℝ는대각선 논법에 따라 셀 수 없습니다. 구멍을 메운 수가 원래 있던 수보다 훨씬 많은 셈입니다. 정수 계수 방정식의 …
수학 기초론 논쟁
… 이어지는 곳. 역설과 불완전성과 정지 문제를 한 줄로 꿰는 대각선의 구조는 자기 참조와 대각선과칸토어의 대각선 논법에서, 공리가 무엇이고 무모순과 독립을 어떻게 증명하는지는 공리와 공준에서 볼 수 있습니다. …
기술 집합론
… 무한 집합을 연구하기 시작한 것도 삼각급수가 함수를 하나로 정하는지를 묻다가였습니다(가산 집합,대각선 논법). 측도에 대해서는 르베그 적분과 측도와 측도 0을, 그 무대였던 세미나에 대해서는 ⟦모스크바 …
단순 타입 람다 계산
… 커야 하니 모순입니다. 따라서 그 언어로 적을 수 없는, 늘 끝나는 계산 가능한 함수가 반드시 있습니다(칸토어의 대각선 논법과 같은 모양입니다). 단순 타입 람다 계산의 한계는 훨씬 더 좁습니다. 처치 수의 타입을 N = (A …
대수적 자료형
… 있습니다. 개수의 법칙은 무한 집합에서도 통하는 집합의 크기의 셈과 같은 모양이며, 2^{|A|} 는칸토어의 대각선 논법이 멱집합이 늘 더 크다고 말할 때의 그 수입니다. 리스트와 나무의 개수를 세는 급수는 생성함수로, …
데카르트 닫힌 범주
… 1을 맞바꾸기)으로 두면 부정에는 고정점이 없으므로, A에서 A의 부분집합 전체로 가는 전사는 없습니다.칸토어의 대각선 논법입니다. 러셀의 역설, 정지 문제, 괴델의 불완전성 정리의 논증도 같은 틀의 변형으로 읽을 수 …
영역 이론: 스콧과 재귀의 의미
… 'D에서 D로 가는 함수들의 집합'과 원소를 빠짐없이 하나씩 짝지을 수 있어야(동형이어야) 합니다. 그런데칸토어의 대각선 논법에 따르면, 원소가 둘 이상인 D에서 D로 가는 함수 전체는 D보다 엄격히 많습니다. 스콧은 처음에 이 …
F-대수와 fold: 재귀와 귀납의 범주론
… 집합을 멱집합으로 보내는 함자 P에는 시작 대수가 없습니다. 있다면 X\cong P(X) 일 텐데,칸토어의 대각선 논법에 따르면 어떤 집합도 자기 멱집합과 크기가 같지 않기 때문입니다. 반대로 상수, +, ×로 지은 …
게임의 결정성
… 둔 판들과 겹치지 않는 판을 늘 찾을 수 있습니다. 이렇게 만든 A에서는 어떤 전략도 이기지 못합니다.대각선 논법의 비켜 가기가 전략 전체를 상대로 벌어진 것입니다. 바나흐–마주르 게임과 결정성 공리. 이보다 앞서 …

이 페이지가 가리키는 개념

게오르크 칸토어 진법 집합의 크기 멱집합 무리수 연속체 가설 레오폴트 크로네커 수학 기초론 논쟁 정지 문제 러셀의 역설 쿠르트 괴델 괴델의 불완전성 정리 윌리엄 로베어 람다 계산 영역 이론: 스콧과 재귀의 의미