대각선 논법

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

집합론에서, 대각선 논법(對角線論法, 영어: diagonal argument)은 실수비가산 집합을 이룸을 보이는 수학적 증명이다. 게오르크 칸토어가 고안하였다.

역사[편집]

실수가 가산 집합을 이루는지 여부를 묻는 문제는 게오르크 칸토어가 1873년에 리하르트 데데킨트에게 보내는 서신에서 처음 제기하였다. 1874년에 그는 구간 축소법을 사용하여 실수가 비가산 집합을 이룸을 증명하였으며, 1891년에 대각선 논법을 사용하여 이를 재증명하였다. 이 증명의 내용은 대략 아래의 증명과 같다. 다만 그는 0~9의 숫자 대신 2진 숫자를 사용하였다.[1] 대각선 논법을 사용한 증명은 이전의 증명보다 간단하여 오늘날 더 널리 알려져 있다.

정의[편집]

실수 집합의 비가산성[편집]

실수의 집합 의 부분 집합 이 가산 집합이라고 가정하자. 그렇다면 이와 음이 아닌 정수의 집합 사이에 전단사 함수

가 존재한다. 속의 각 실수는 유일한 무한 소수 표기를 가지므로 (유한 소수는 끝에 9를 무한히 순환하여 나타내야 한다. 예컨대 1/5=0.1999...와 같이 나타낸다), 는 다음과 같은 유일한 무한 소수 표현을 갖는다.

다음과 같은 실수 를 생각하자.

여기서 는 다음과 같다.

그렇다면 임의의 에 대하여 과 소수점 뒤 번째 자리에서 다르다. 즉, 에 포함되지 않으며, 전사 함수가 아니다. 이는 가 전단사 함수임에 모순이다. 따라서 는 비가산 집합이며, 이를 부분 집합으로 갖는 역시 비가산 집합이다. 이와 같은 증명 방법을 대각선 논법이라고 한다.

칸토어의 정리[편집]

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

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

임의의 집합 에 대하여, 함수

가 주어졌다고 하자. 그렇다면

를 정의하자. 그렇다면 다음 두 명제를 쉽게 보일 수 있다.

  • 임의의 에 대하여, 이다.
    • 정의에 따라서 이다. 그러나 이므로, 이다.
  • 임의의 에 대하여, 이다.
    • 정의에 따라서 이다. 그러나 이 경우 이므로, 이다.

따라서 에 포함되지 않는다. 즉, 전사 함수가 아니다. 따라서, 사이에 전사 함수가 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 역시 존재하지 않는다.

위의 구성은 러셀의 역설에서 이용되는 자기 자신을 포함하지 않는 집합 과 유사하다.

같이 보기[편집]

각주[편집]

  1. 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

참고 문헌[편집]

  • (흥미있는 수학 이야기 -이만근,오은영 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 http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002113910)https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi