# 대각선 논법 > [!abstract] 목차 > 1. [[#개요]] > 2. [[#역사적 맥락]] > - [[#칸토어의 첫 번째 증명]] > - [[#1891년 대각선 논법]] > 3. [[#증명의 구조]] > - [[#실수의 비가산성]] > - [[#멱집합에 대한 일반화]] > 4. [[#응용과 영향]] > - [[#괴델의 불완전성 정리]] > - [[#튜링의 정지 문제]] > - [[#자기참조와 역설]] > 5. [[#비판과 논쟁]] > - [[#직관주의적 반론]] > - [[#배중률 문제]] > 6. [[#철학적 함의]] > - [[#자기참조의 힘]] > - [[#한계의 증명]] > 7. [[#관찰자의 기록]] > 8. [[#같이 읽기]] ## 개요 대각선 논법(diagonal argument)은 [[수학/집합론/게오르크 칸토어|게오르크 칸토어]]가 1891년 발표한 증명 기법으로, 실수의 집합이 자연수의 집합보다 크다는 것을 보여준다. 이 논법의 핵심은 "모든 원소를 나열했다"는 가정으로부터 "나열에 포함되지 않은 원소"를 구성하여 모순을 이끌어내는 것이다. 대각선 논법은 단순히 실수의 비가산성을 증명하는 것 이상의 의미를 갖는다. 이 논법의 구조는 20세기 수리논리학과 계산 이론의 핵심 결과들에서 반복적으로 나타난다. 괴델의 불완전성 정리, 튜링의 정지 문제 불가해성 증명, 타르스키의 진리 비정의성 정리—현대 논리학의 가장 심오한 결과들이 대각선 논법의 변형이다. 인간 이성의 한계를 증명하는 도구가 된 이 논법은 수학사에서 가장 강력하고 다재다능한 증명 기법 중 하나로 관찰된다. ## 역사적 맥락 ### 칸토어의 첫 번째 증명 실수가 자연수보다 많다는 명제의 최초 증명은 1874년에 나왔다. 칸토어는 리하르트 데데킨트에게 보낸 1873년 서신에서 이 문제를 처음 제기했고, 이듬해 구간 축소법(nested interval method)을 사용한 증명을 발표했다. 구간 축소법 증명은 다음과 같이 진행된다. 실수가 가산이라고 가정하면, 모든 실수를 r₁, r₂, r₃, ...로 나열할 수 있다. 이제 어떤 닫힌 구간 [a₁, b₁]을 선택하되 r₁이 포함되지 않게 한다. 그 안에서 r₂가 포함되지 않는 더 작은 구간 [a₂, b₂]를 선택한다. 이 과정을 반복하면 모든 rₙ을 배제하면서 수축하는 구간들의 무한 수열이 만들어진다. 완비성에 의해 이 구간들의 교집합에는 적어도 하나의 실수가 존재하는데, 이 수는 목록에 없다. 모순이다. 이 증명은 유효하지만, 실수의 특정 성질(완비성)에 의존한다. 칸토어는 더 일반적이고 직접적인 방법을 찾았다. ### 1891년 대각선 논법 1891년, 칸토어는 논문 「다양체론의 한 기초 문제에 대하여」(Über eine elementare Frage der Mannigfaltigkeitslehre)에서 대각선 논법을 발표했다. 이 논법은 첫 번째 증명보다 17년이나 늦게 나왔지만, 더 간결하고 일반화 가능했다. 원래 논문에서 칸토어는 0과 1로 이루어진 무한 수열들의 집합을 다루었다. 그러나 이 논법은 실수, 멱집합, 함수 등 다양한 맥락에 적용될 수 있다. 대각선 논법은 칸토어가 남긴 가장 영향력 있는 유산 중 하나이다. ## 증명의 구조 ### 실수의 비가산성 실수의 비가산성에 대한 대각선 논법은 다음과 같이 진행된다. **가정**: 열린 구간 (0, 1)의 모든 실수가 [[가산 집합|가산]]이라고 하자. 그러면 모든 실수를 나열할 수 있다: r₁ = 0.d₁₁d₁₂d₁₃d₁₄... r₂ = 0.d₂₁d₂₂d₂₃d₂₄... r₃ = 0.d₃₁d₃₂d₃₃d₃₄... r₄ = 0.d₄₁d₄₂d₄₃d₄₄... ... 여기서 dᵢⱼ는 rᵢ의 소수점 이하 j번째 자리 숫자이다. **대각선 구성**: 이제 새로운 수 s = 0.s₁s₂s₃s₄...를 다음과 같이 정의한다: - s₁ ≠ d₁₁ (첫 번째 수의 첫 번째 자리와 다르게) - s₂ ≠ d₂₂ (두 번째 수의 두 번째 자리와 다르게) - sₙ ≠ dₙₙ (n번째 수의 n번째 자리와 다르게) 예를 들어, dₙₙ이 짝수이면 sₙ을 홀수로, 홀수이면 짝수로 선택한다. **모순**: s는 (0, 1) 구간의 실수이다. 그러나 s는 목록의 어떤 수와도 같지 않다: - s ≠ r₁ (첫 번째 자리에서 다름) - s ≠ r₂ (두 번째 자리에서 다름) - s ≠ rₙ (n번째 자리에서 다름) 따라서 s는 목록에 포함되어야 하지만 포함되어 있지 않다. 이는 원래의 가정(모든 실수를 나열할 수 있다)과 모순된다. **결론**: (0, 1) 구간의 실수는 가산이 아니다. 따라서 실수 전체는 비가산이다. ### 멱집합에 대한 일반화 대각선 논법은 더 일반적인 결과를 증명하는 데 사용된다. **칸토어의 정리**(1891)에 따르면, 임의의 집합 X에 대해, X의 멱집합 P(X)는 X보다 크다. 즉, |X| < |P(X)|이다. 증명은 대각선 논법을 따른다. X에서 P(X)로의 전사함수 f가 존재한다고 가정하자. 집합 D = {x ∈ X : x ∉ f(x)}를 정의한다. D는 X의 부분집합이므로 P(X)의 원소이다. f가 전사이므로, 어떤 d ∈ X에 대해 f(d) = D이어야 한다. 그러면 d ∈ D인가? - d ∈ D라면, D의 정의에 의해 d ∉ f(d) = D이다. 모순. - d ∉ D라면, D의 정의에 의해 d ∈ f(d) = D이다. 모순. 어느 경우도 모순이므로, 전사함수 f는 존재하지 않는다. 따라서 |P(X)| > |X|이다. 이 정리는 [[수학/집합론/무한|무한]]의 무한한 위계가 존재함을 함의한다. 무한 [[수학/집합론/집합의 기수|기수]]들이 ℵ₀ < 2^ℵ₀ < 2^(2^ℵ₀) < ... 로 끝없이 이어진다. ## 응용과 영향 ### 괴델의 불완전성 정리 1931년, 쿠르트 괴델은 "충분히 강력한 무모순 형식 체계는 완전할 수 없다"는 불완전성 정리를 증명했다. 증명의 핵심에는 대각선 논법의 변형이 있다. 괴델은 형식 체계의 진술들을 자연수로 코딩하는 방법(괴델 수)을 고안했다. 이를 통해 체계는 자기 자신에 대해 '말할' 수 있게 된다. 괴델은 대각선 보조정리(diagonal lemma)를 사용하여 "이 문장은 증명될 수 없다"를 형식화했다. 이 문장 G가 증명 가능하다면, 체계는 거짓을 증명한 것이므로 무모순이 아니다. G가 증명 불가능하다면, G는 참이지만 증명될 수 없다. 따라서 무모순 체계에서 G는 참이지만 증명 불가능하다—체계는 불완전하다. 괴델 자신이 리샤르의 역설(Richard's paradox)과의 유사성을 명시적으로 언급했다. 대각선화는 체계가 자기 자신에 대해 말하도록 하고, 그로부터 한계가 드러난다. ### 튜링의 정지 문제 1936년, 앨런 튜링은 "어떤 프로그램이 주어진 입력에 대해 멈출지 여부를 결정하는 일반적 알고리즘은 존재하지 않는다"는 것을 증명했다. 이것이 정지 문제(halting problem)의 불가해성이다. 증명은 대각선 논법을 따른다. 정지 여부를 판단하는 프로그램 H가 존재한다고 가정하자. H(P, I)는 프로그램 P가 입력 I에 대해 멈추면 '예'를, 그렇지 않으면 '아니오'를 출력한다. 이제 '병리적' 프로그램 G를 다음과 같이 정의한다: ``` G(P): if H(P, P) == '예': 무한 루프 else: 정지 ``` G(G)를 실행하면 어떻게 되는가? - G(G)가 멈춘다면, H(G, G) = '아니오'였어야 한다. 그러면 G의 정의에 의해 G(G)는 무한 루프에 빠졌어야 한다. 모순. - G(G)가 멈추지 않는다면, H(G, G) = '예'였어야 한다. 그러면 G의 정의에 의해 G(G)는 멈춰야 한다. 모순. 어느 경우도 모순이므로, H는 존재하지 않는다. ### 자기참조와 역설 대각선 논법은 자기참조(self-reference)와 깊이 연결되어 있다. F. 윌리엄 로베어(F. William Lawvere)에 따르면, 많은 자기참조적 역설, 불완전성 정리, 고정점 정리가 같은 기본 구조에서 나온다. 러셀의 역설("자기 자신을 포함하지 않는 모든 집합의 집합")은 대각선 논법과 구조적으로 동일하다. "대각선이 지나는 곳에 체크표시가 있어야 하는 동시에 없어야 한다"는 불가능한 상황이 발생한다. 거짓말쟁이 역설("이 문장은 거짓이다"), 리샤르의 역설(유한한 표현으로 정의할 수 있는 실수들), 베리의 역설("백 글자 이내로 정의할 수 없는 가장 작은 정수")—이들 모두 대각선화의 변형으로 이해될 수 있다. 로베어의 정리는 이러한 유사성을 범주론적으로 일반화한다. 거의 모든 대각선화가 수리논리학의 중요한 결과로 이어지므로, 이 일반화는 상당한 힘을 갖는다. ## 비판과 논쟁 ### 직관주의적 반론 대각선 논법에 대한 가장 체계적인 비판은 직관주의(intuitionism)에서 나왔다. 루이첸 브라우어(L.E.J. Brouwer)를 중심으로 한 직관주의자들은 칸토어의 결론에 이의를 제기했다. 직관주의자들은 칸토어의 정리 자체의 유효성을 부정하지 않았다. 그들이 문제 삼은 것은 증명의 전제, 특히 배중률(Law of Excluded Middle)의 무한 집합에 대한 적용이었다. 브라우어에 따르면, 배중률은 아리스토텔레스 이래 유한한 체계에서 도출된 것이다. 이 법칙이 무한 집합에도 적용된다고 가정할 이유는 없다. 직관주의자에게, 수학적 대상은 구성되어야 존재한다. 무한한 목록과 그에 포함되지 않는 수를 '한 번에' 다루는 것은 정당화되지 않은 도약이다. ### 배중률 문제 대각선 논법은 귀류법(proof by contradiction)에 의존한다. "모든 실수를 나열할 수 있다"를 가정하고, 모순을 이끌어내어 가정을 부정한다. 고전 논리에서 배중률은 유효하다: 명제는 참이거나 거짓이다. 제3의 가능성은 없다. 따라서 "~P가 모순이면 P"이다. 그러나 직관주의 논리에서 배중률은 공리가 아니다. "~P가 모순"이라는 것은 "P의 구성적 증명이 존재함"을 함의하지 않는다. 직관주의자에게, 대각선 논법은 "실수를 나열할 수 없다"를 증명하지만, "비가산적으로 많은 실수가 존재한다"를 증명하지는 않는다. 오늘날 대다수의 수학자는 고전 논리를 받아들이고, 대각선 논법을 유효한 것으로 인정한다. 그러나 직관주의적 비판은 증명의 전제에 대한 성찰을 요구한다는 점에서 철학적 가치가 있다. ## 철학적 함의 ### 자기참조의 힘 대각선 논법의 핵심은 자기참조(self-reference)이다. 목록이 자기 자신을 포함해야 하는지를 묻고, 그 질문 자체가 모순을 생성한다. 자기참조는 역설을 낳기도 하지만, 심오한 정리를 증명하는 도구이기도 하다. 괴델, 튜링, 타르스키의 결과들은 모두 형식 체계가 자기 자신에 대해 말하도록 함으로써 얻어졌다. 대각선 논법은 자기참조를 '길들이는' 방법을 제공한다. 순환적 정의는 역설로 이어질 수 있지만, 적절히 통제된 자기참조는 한계를 드러내는 강력한 도구가 된다. ### 한계의 증명 대각선 논법의 응용들은 대부분 '부정적' 결과—무언가가 불가능하다는 것—를 증명한다: - 실수를 자연수로 셀 수 없다 - 무모순 체계는 완전할 수 없다 - 정지 여부를 결정하는 알고리즘은 없다 - 진리를 형식적으로 정의할 수 없다 이 결과들은 인간 지식의 한계를 수학적으로 증명한다. 어떤 것들은 원리적으로 알 수 없거나, 계산할 수 없거나, 형식화할 수 없다. 그러나 이 한계 자체는 알 수 있다. 대각선 논법은 불가능성을 증명함으로써 가능성의 경계를 획정한다. 한계를 아는 것은 그 자체로 지식이다. ## 관찰자의 기록 대각선 논법을 관찰하면서 몇 가지 특기할 만한 점이 발견된다. 첫째, 이 논법의 단순성과 힘 사이의 괴리가 주목된다. 증명 자체는 초등적이다—고등학교 수준의 수학으로 이해할 수 있다. 그러나 그 결과와 응용은 20세기 수학과 논리학의 가장 심오한 결과들을 포함한다. 단순한 도구가 깊은 진리를 드러내는 사례로 보인다. 둘째, 대각선 논법의 편재성이 흥미롭다. 집합론, 논리학, 계산 이론, 복잡도 이론에서 같은 구조가 반복적으로 나타난다. 로베어의 정리가 이를 일반화하지만, 왜 이 특정 구조가 그토록 많은 맥락에서 작동하는지는 완전히 해명되지 않은 것으로 보인다. 셋째, 자기참조의 이중적 성격이 관찰된다. 자기참조는 역설을 낳기도 하고(러셀의 역설, 거짓말쟁이 역설) 정리를 증명하기도 한다(불완전성, 정지 문제). 같은 구조가 파괴적일 수도 건설적일 수도 있다는 것은 흥미로운 대칭이다. 넷째, 직관주의적 비판은 무시되기 어렵다. 대다수의 수학자는 대각선 논법을 받아들이지만, 그것이 '자명하게' 유효한 것은 아니다. 배중률의 지위, 무한에 대한 추론의 정당성—이런 문제들은 대각선 논법을 사용할 때마다 암묵적으로 전제된다. 다섯째, 칸토어가 대각선 논법을 첫 번째 증명 17년 후에야 발표한 것이 주목된다. 같은 결과에 대한 더 간결한 증명을 찾는 데 그토록 오랜 시간이 걸렸다는 것은 수학적 발견의 비선형성을 보여준다. 혹은 칸토어가 첫 번째 증명에 만족했고 대각선 논법은 우연히 발견된 것일 수도 있다. ## 같이 읽기 ### 핵심 개념 - [[가산 집합]] - 대각선 논법이 반증하려는 가설 - [[수학/집합론/무한|무한]] - 대각선 논법이 구조화하는 개념 - [[수학/집합론/연속체 가설|연속체 가설]] - 가산과 비가산 사이의 문제 ### 관련 인물 - [[수학/집합론/게오르크 칸토어|게오르크 칸토어]] - 대각선 논법의 창안자 - [[수학/집합론/쿠르트 괴델|쿠르트 괴델]] - 불완전성 정리에 대각선화 적용 - [[앨런 튜링]] - 정지 문제에 대각선화 적용 - [[루이첸 브라우어]] - 직관주의적 비판 ### 응용 분야 - [[괴델의 불완전성 정리]] - 형식 체계의 한계 - [[정지 문제]] - 계산의 한계 - [[러셀의 역설]] - [[수학/집합론/소박한 집합론|소박한 집합론]]의 모순 ### 철학적 맥락 - [[자기참조]] - 대각선 논법의 핵심 구조 - [[직관주의]] - 대각선 논법에 대한 비판적 입장 - [[수학철학]] - 수학적 증명의 본성 **마지막 업데이트**: 2025-11-27 23:12:18