대각선 논법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

자연수와 실수의 크기[편집]

자연수의 집합 과 실수의 구간 사이에는 일대일대응이 존재하지 않으며, 이는 대각선 논법으로 증명할 수 있다. 칸토어는 이 정리를 1874년 구간 축소법을 이용하여 증명하였으나, 1891년에 대각선 논법을 사용하여 재증명하였다. 대각선 논법을 이용한 증명은 이전의 증명보다 더 간단하고 직관적이다.

증명[편집]

임의의 함수

가 존재한다고 하자. 구간 (0, 1] 에 포함되는 실수는 소수로 표기할 수 있다. 다만,

0.1

과 같은 유한 소수는

0.09999...

로 쓰도록 해서 실수 하나에는 하나의 소수 표현만이 대응하도록 한다. 이렇게 표기하였을 때, 의 값들이 다음과 같다고 하자.

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

여기서 는 다음과 같다.

그렇다면 임의의 에 대하여 과 소수점 뒤 째 자리에서 다르다. 즉, 에 포함되지 않으며, 전사 함수가 아니다. 즉, 전사 함수 은 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 이 역시 존재하지 않는다.

여기에서 "대각선"은 식에서 굵은 글씨로 처리된 등으로, 번째 소수의 소수 제 자리를 차례차례에 더듬고 간 부분에 해당한다. 실수 전체와 (0, 1] 과의 사이에 전단사 관계는 쉽게 증명할 수 있으며, 따라서 실수의 집합은 가산 집합이 아니다.

칸토어의 정리[편집]

칸토어의 정리(1890년)에 따르면, 임의의 집합 과 그 멱집합 사이에는 전단사 함수가 존재하지 않는다. 이 역시 대각선 논법을 이용해 증명할 수 있다. 이 증명에서는 각각의 집합 에 대해서 를 포함할지로 항상 다른 집합 를 만들어 내는 점이 대각선을 이용하고 있다.

실수의 집합은 자연수의 멱집합과 크기가 동일하기 때문에, 최초의 정리는 두 번째 정리의 특별한 경우가 된다.이 정리에 의해, 멱집합의 크기가 원래의 집합보다 커지는 것은 알 수 있지만, 그럼 그 사이에 다른 크기는 존재하는가 하는 문제를 생각할 수도 있고 이것은 연속체 가설로 불리고 있다.

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

증명[편집]

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

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

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

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

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

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

같이 보기[편집]