대각선 논법 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Diagonal argument 01 svg.svg|right|섬네일|250px|이진법에서 [[비가산 집합]]의 존재성을 증명하는 칸토어의 대각선 논법을 나타낸 것이다. 아래에 있는 수는 위의 어느 수와도 같을 수 없다.]]
[[집합론]]에서 '''대각선 논법'''(對角線論法, {{llang|en|diagonal argument}})은 [[게오르크 칸토어]]가 [[실수]]가 [[자연수]]보다 [[집합의 크기|많음]]을 증명하는 데 사용한 방법이다. 즉, 대각선 논법은 [[실수]]의 집합이 [[비가산 집합]]임을 보이는 데 사용된다.

== 자연수와 실수의 집합의 크기 ==
[[자연수]](음이 아닌 정수)의 집합 <math>\mathbb N</math>과 실수 [[구간]] <math>(0,1)</math> 사이에는 [[전단사 함수]]가 존재하지 않으며, 이는 대각선 논법으로 증명할 수 있다. 이는 [[실수]]의 집합 <math>\mathbb R</math>이 [[비가산 집합]]이라는 명제와 [[동치]]이다. 이 명제가 참인지를 묻는 문제는 [[게오르크 칸토어]]가 1873년에 [[리하르트 데데킨트]]에게 보내는 서신에서 처음 제기하였다. 칸토어는 이 정리를 1874년에 구간 축소법을 이용하여 증명하였으며, 1891년에 대각선 논법을 사용하여 재증명하였다.<ref>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</ref> 대각선 논법을 이용한 증명은 이전의 증명보다 더 간단하며 오늘날 더 널리 알려져 있다.

=== 증명 ===
임의의 [[함수]] <math>f\colon\mathbb N\to(0,1)</math>가 주어졌다고 하자. 구간 <math>(0,1)</math>에 포함되는 실수는 소수로 표기할 수 있다. 다만, 0.1과 같은 유한 소수는 0.0000…, 0.9999…로 쓰도록 해서 실수 하나에는 하나의 소수 표현만이 대응하도록 한다. 이렇게 표기하였을 때, <math>f</math>의 값들이 다음과 같다고 하자.
:<math>f(0)=0.a_{11}a_{12}a_{13}\cdots</math>
:<math>f(1)=0.a_{21}a_{22}a_{23}\cdots</math>
:<math>f(2)=0.a_{31}a_{32}a_{33}\cdots</math>
:<math>\vdots</math>
다음과 같은 실수 <math>r\in(0,1)</math>를 생각하자.
:<math>r=0.b_1b_2b_3\cdots</math>
여기서 <math>b_i</math>는 다음과 같다.
:<math>b_i=\begin{cases}1&a_{ii}\ne 1\\2&a_{ii}=1\end{cases}</math>
그렇다면 임의의 <math>n\in\mathbb N</math>에 대하여, <math>r</math>는 <math>f(n)</math>과 소수점 뒤 <math>n+1</math>번째 자리에서 다르므로, <math>r\ne f(n)</math>이다. 즉, <math>r</math>는 <math>f</math>의 [[치역]]에 포함되지 않으며, <math>f</math>는 [[전사 함수]]가 아니다. 즉, 전사 함수 <math>\mathbb N\to(0,1)</math>는 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 이 역시 존재하지 않는다. 전단사 함수 <math>(0,1)\to\mathbb R</math>는 자명하게 존재하므로, 전단사 함수 <math>\mathbb N\to\mathbb R</math> 역시 존재하지 않는다.

=== 다른 방법의 증명 ===
{{참고|바나흐-마주르 게임}}
다음 증명은 대각선 논법을 사용하지 않는다. 구간 <math>(0,1)</math>의 임의의 부분 집합 <math>S\subseteq(0,1)</math>에 대하여, 갑과 을이 다음과 같은 규칙의 게임을 한다고 가정하자.
* 갑과 을은 번갈아 가며 실수를 취한다.
* 우선 갑이 <math>x_0=0</math>을 취하고, 그 뒤 을이 <math>y_0=1</math>을 취한다.
* <math>x_{n-1},y_{n-1}</math>이 선택되었을 때, 먼저 갑이 임의의 <math>x_n\in(x_{n-1},y_{n-1})</math>을 취하고, 을은 임의의 <math>y_n\in(x_n,y_{n-1})</math>를 취한다.
* 이 경우, <math>(x_n)_{n=0}^\infty</math>는 수렴하며, <math>\textstyle\lim_{n\to\infty}x_n\in(0,1)</math>이다. 만약 <math>\textstyle\lim_{n\to\infty}x_n\in S</math>라면 갑이 승리하며, 만약 <math>\textstyle\lim_{n\to\infty}x_n\not\in S</math>라면 을이 승리한다.
만약 <math>S=\{s_1,s_2,\dots\}</math>가 [[가산 집합]]일 경우, 다음과 같은 을의 필승 전략이 존재한다. 임의의 <math>n\in\mathbb Z^+</math>에 대하여,
* 만약 <math>n\le|S|</math>이며 <math>s_n\in(x_n,y_{n-1})</math>라면, 을은 <math>n</math>번째 실수로 <math>y_n=s_n</math>을 취한다.
* 만약 <math>n>|S|</math>이거나 <math>s_n\not\in(x_n,y_{n-1})</math>라면, 을은 <math>n</math>번째 실수로 임의의 <math>y_n\in(x_n,y_{n-1})</math>을 취한다.
그러나 <math>S=(0,1)</math>일 경우 항상 갑이 승리하므로, 을은 필승 전략을 가지지 않는다. 따라서 <math>(0,1)</math>은 [[비가산 집합]]이다.

== 멱집합의 크기 ==
{{본문|칸토어의 정리}}
[[칸토어의 정리]](1890년)에 따르면, 임의의 집합 <math>X</math> 과 그 [[멱집합]] <math>\mathcal P(X)</math> 사이에는 [[전단사 함수]]가 존재하지 않는다. 이 역시 대각선 논법을 이용해 증명할 수 있다. 이 증명에서는 각각의 집합 <math>\psi(x)</math>에 대해서 <math>x</math>를 포함할지로 항상 다른 집합 <math>A</math>를 만들어 내는 점이 대각선을 이용하고 있다. 이 정리에 의해, 멱집합의 크기가 원래의 집합보다 커지는 것은 알 수 있지만, 그럼 그 사이에 다른 크기는 존재하는가 하는 문제를 생각할 수도 있고 이것은 [[연속체 가설]]로 불리고 있다.

만약 모든 집합의 집합 <math>V</math>가 존재한다면, <math>\mathcal P(V)</math>는 <math>V</math>의 부분 집합이면서도 <math>V</math>보다 크기가 커져 모순을 일으킨다. 이를 '''[[칸토어 역설]]'''이라고 한다. 따라서, [[공리적 집합론]]에서는 모든 집합을 포함한 집합이 존재하지 않는다. 대신 모든 집합의 [[고유 모임]]은 존재하며, [[폰 노이만 전체]]라고 불린다.

=== 증명 ===
임의의 집합 <math>X</math>에 대하여, [[함수]]
:<math>f\colon X \to\mathcal P(X)</math>
가 주어졌다고 하자. 그렇다면
:<math>A=\{x\in X\colon x\not\in f(x)\}\subset X</math>
를 정의하자. 그렇다면 다음 두 명제를 쉽게 보일 수 있다.
* 임의의 <math>a\in A</math>에 대하여, <math>A\ne f(a)</math>이다.
** 정의에 따라서 <math>a\not\in f(a)</math>이다. 그러나 <math>a\in A</math>이므로, <math>A\ne f(a)</math>이다.
* 임의의 <math>b\in X\setminus A</math>에 대하여, <math>A\ne f(b)</math>이다.
** 정의에 따라서 <math>b\in f(b)</math>이다. 그러나 이 경우 <math>b\not\in A</math>이므로, <math>A\ne f(b)</math>이다.
따라서 <math>A</math>는 <math>f</math>의 [[상 (수학)|상]]에 포함되지 않는다. 즉, <math>f</math>는 [[전사 함수]]가 아니다. 따라서, <math>X</math>와 <math>\mathcal P(X)</math> 사이에 전사 함수가 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 역시 존재하지 않는다.

위의 구성은 [[러셀의 역설]]에서 이용되는 자기 자신을 포함하지 않는 집합 <math>\{S\colon S\not\in S\}</math>과 유사하다.

== 같이 보기 ==
* [[집합의 크기]]

== 각주 ==
{{각주}}

== 참고 문헌 ==
* (흥미있는 수학 이야기 -이만근,오은영 2007)http://shop.mathlove.kr/shop/goods/goods_view.php?&goodsno=472&category=004001
* (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

{{집합론}}

[[분류:집합론]]
[[분류:증명]]
[[분류:게오르크 칸토어]]