모두 적었다는 무한 문자열 목록, 대각선을 바꾸면 빠진 하나가 나와요

0과2로 된 무한 문자열을 모두 나열했다고 가정해요. 새 문자열의 n번째 자리를 목록 n번째 문자열의 n번째 자리와 다르게 정해요. 임의의 번호에서 다르다는 설명이 왜 목록 전체에 적용되는지 확인해요.

대각선 무늬가 반복되는 직물 표본

사진: Bevaringstenestene · CC BY-SA 4.0 · 원본 출처

0과2로만 이루어진 무한 문자열을 모두 나열했다고 가정해요. 새 문자열b의n번째 문자를 목록n번째 문자열의n번째 문자와 다르게 정해요. b가 목록 어디에도 없다는 이유를 설명해 볼까요? 실수의 소수 표현 대신 문자열로 묻는 장점도 말하라.

bn=2−ann,ann∈{0,2}b_n=2-a_{nn},\qquad a_{nn}\in\{0,2\}

대각선 구성과 전칭 조건

목록k번째 문자열과b를 비교하면k번째 자리에서 반드시 달라요. 이 논리는 어느k에도 적용되므로b는 목록의 어떤 문자열과도 같지 않아요. 따라서 모든 문자열을 자연수 순서로 나열했다는 가정이 성립하지 않아요.

0이면2,2이면0으로 바꾸기 때문에 새 문자열도 허용된 문자만 사용해요. 문자열로 문제를 쓰면0.999…와1처럼 같은 실수를 다른 소수 표현으로 쓰는 문제를 따로 해결할 필요가 없어요. 실수의 크기 증명으로 넘어갈 때에는 이런 표현의 중복을 점검해야 해요.

∀k∈N,bk≠akk\forall k\in\mathbb{N},\quad b_k\neq a_{kk}

첫 네 문자열을 임의로 적고 대각선 네 칸을 바꾸게 해요. 유한 예를 보여 준 뒤 임의의k에 대한 문장을 완성시켜 경험과 증명의 차이를 확인해요.

네 문자열만 보고 만든 네 글자 반례가 무한한 목록 전체 를 반박하는 증명은 아닌 이유는 무엇인가?

착안 원문: How Can Infinity Come in Many Sizes?. 대각선 논법을 실수 표기의 중복 문제가 없는 무한 문자열로 다시 구성했어요.

이 글 공유하기

개인정보 및 방문 통계 안내