집합론에서 대각선 논법(對角線論法, 영어:diagonal argument)은 게오르크 칸토어가 실수가 자연수보다 많음을 증명하는 데 사용한 방법이다. 즉, 대각선 논법은 실수의 집합이 비가산 집합임을 보이는 데 사용된다.
자연수(음이 아닌 정수)의 집합 과 실수 구간 사이에는 전단사 함수가 존재하지 않으며, 이는 대각선 논법으로 증명할 수 있다. 이는 실수의 집합 이 비가산 집합이라는 명제와 동치이다. 이 명제가 참인지를 묻는 문제는 게오르크 칸토어가 1873년에 리하르트 데데킨트에게 보내는 서신에서 처음 제기하였다. 칸토어는 이 정리를 1874년에 구간 축소법을 이용하여 증명하였으며, 1891년에 대각선 논법을 사용하여 재증명하였다.[1] 대각선 논법을 이용한 증명은 이전의 증명보다 더 간단하며 오늘날 더 널리 알려져 있다.
증명
임의의 함수가 주어졌다고 하자. 구간 에 포함되는 실수는 소수로 표기할 수 있다. 다만, 0.1과 같은 유한 소수는 0.0000…, 0.9999…로 쓰도록 해서 실수 하나에는 하나의 소수 표현만이 대응하도록 한다. 이렇게 표기하였을 때, 의 값들이 다음과 같다고 하자.
다음과 같은 실수 를 생각하자.
여기서 는 다음과 같다.
그렇다면 임의의 에 대하여, 는 과 소수점 뒤 번째 자리에서 다르므로, 이다. 즉, 는 의 치역에 포함되지 않으며, 는 전사 함수가 아니다. 즉, 전사 함수 는 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 이 역시 존재하지 않는다. 전단사 함수 는 자명하게 존재하므로, 전단사 함수 역시 존재하지 않는다.
칸토어의 정리(1890년)에 따르면, 임의의 집합 과 그 멱집합 사이에는 전단사 함수가 존재하지 않는다. 이 역시 대각선 논법을 이용해 증명할 수 있다. 이 증명에서는 각각의 집합 에 대해서 를 포함할지로 항상 다른 집합 를 만들어 내는 점이 대각선을 이용하고 있다. 이 정리에 의해, 멱집합의 크기가 원래의 집합보다 커지는 것은 알 수 있지만, 그럼 그 사이에 다른 크기는 존재하는가 하는 문제를 생각할 수도 있고 이것은 연속체 가설로 불리고 있다.
만약 모든 집합의 집합 가 존재한다면, 는 의 부분 집합이면서도 보다 크기가 커져 모순을 일으킨다. 이를 칸토어 역설이라고 한다. 따라서, 공리적 집합론에서는 모든 집합을 포함한 집합이 존재하지 않는다. 대신 모든 집합의 고유 모임은 존재하며, 폰 노이만 전체라고 불린다.
Georg Cantor (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78. English translation: Ewald, William B. (ed.) (1996). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2. Oxford University Press. pp. 920–922. ISBN 0-19-850536-1.- https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi
(Georg Cantor (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78. English translation: Ewald, William B. (ed.) (1996). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2. Oxford University Press. pp. 920–922. ISBN 0-19-850536-1.-Ueber eine elementare Frage der Mannigfaltigketislehre.
Jahresbericht der Deutschen Mathematiker-Vereinigung / Zeitschriftenband (1890/91) / Artikel / 75 - 78
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.