힐베르트 호텔

1. 개요

힐베르트 호텔은 무한히 많은 객실을 가진 가상의 호텔을 상상한 사고실험이다. 모든 객실이 차 있는 상태에서 새로운 손님이나 무한한 수의 손님을 수용할 수 있다는 역설적인 상황을 보여준다. 유한한 호텔과는 달리, 힐베르트 호텔에서는 기존 투숙객들의 객실 번호를 변경하여 새로운 손님들을 수용할 수 있다. 소수 거듭제곱, 소인수분해, 인터리빙, 삼각수, 임의의 열거 방법 등 다양한 방법을 통해 무한히 많은 손님을 수용하는 방법을 제시한다. 힐베르트의 역설은 무한 집합의 개념을 설명하는 데 사용되며, 수학적 증명을 통해 참임이 증명된다. 이 역설은 대중문화에서도 자주 언급되며, 소설, 영화, 만화 등 다양한 매체에서 무한의 개념을 설명하는 데 활용된다.

2. 역설의 내용

힐베르트 호텔은 1, 2, 3 등 무한히 번호가 매겨진 객실이 있는 가상의 호텔이다. 이 호텔은 가산 무한 개의 객실을 가지고 있으며, 모든 객실이 꽉 차 있어도 새로운 손님을 받을 수 있다는 역설을 보여준다. 일반적인 유한한 호텔에서는 모든 객실이 차면 새로운 손님을 받을 수 없지만, 무한 호텔에서는 기존 손님과 새로운 손님, 심지어 무한한 수의 손님도 모두 수용 가능하다.

객실 수가 유한한 경우, "만실"과 "새 손님을 받을 수 없음"은 동치(비둘기집 원리)이지만, 무한 호텔에서는 그렇지 않다.

2.1. 유한 명의 새로운 손님

무한히 많은 손님들이 동시에 방을 옮기면, 호텔은 기존 손님과 추가 손님 모두를 수용할 수 있다. 1호실에 있는 손님은 2호실로, 2호실에 있는 손님은 3호실로 이동하는 식으로, 모든 손님을 현재 방 n에서 n+1호실로 옮긴다. 무한 호텔에는 마지막 방이 없으므로 모든 손님은 옮겨갈 방이 있다. 이렇게 하면 1호실이 비게 되고, 새로운 손님은 그 방으로 들어갈 수 있다. 이 절차를 반복하면 유한한 수의 새로운 손님들을 수용할 수 있다. 일반적으로 k명의 손님이 방을 원할 경우, 호텔은 같은 절차를 적용하여 모든 손님을 n호실에서 n + k호실로 옮길 수 있다.

어떤 손님이 호텔에 투숙을 희망한다고 가정할 때, 1호실의 손님을 2호실로, 2호실의 손님을 3호실로, n호실의 손님을 (n + 1)호실로 (동시에) 이동시킨다. 그러면 1호실이 빈 방이 되므로, 그 빈 방에 손님 한 명을 묵게 할 수 있다. 이 절차를 반복함으로써, 임의의 유한 명의 새로운 손님을 위한 방을 만들 수 있다.

2.2. 무한 명의 새로운 손님

또한 '가산 무한'개의 새로운 손님을 수용하는 것도 가능하다. 방 1에 있는 사람을 방 2로, 방 2에 있는 손님을 방 4로, 일반적으로 방 n에 있는 손님을 방 2n(2 곱하기 n)으로 옮기면 모든 홀수 번호 방(가산 무한)이 새로운 손님을 위해 비워지게 된다.

2.3. 무한 명의 손님을 태운 무한 대의 버스

무한 명의 승객을 태운 무한 대의 버스를 수용하는 방법에는 여러 가지가 있다. 대부분의 방법은 버스 좌석에 번호가 매겨져 있다는 것을 전제로 한다. 이 문제를 해결하기 위해 대응 함수를 사용할 수 있다. 각 방법에서 승객의 좌석 번호를 $n$, 타고 있는 버스의 호차 번호를 $c$라고 하면, $n$과 $c$가 대응 함수의 두 인수가 된다.

이후 내용은 각각의 방법에 대한 하위 섹션에서 자세하게 다루므로 여기서는 간략하게 설명을 생략한다.

2.3.1. 소수 거듭제곱을 이용하는 방법

i호실의 손님을 2ⁱ호실로 이동시켜 홀수 호실을 비운다. 1호차 단체 손님을 3ⁿ호실, 2호차 단체 손님을 5ⁿ호실에 묵게 한다. 일반적으로 c호차 단체 손님은 c번째 소수를 p로 하여, pⁿ호실에 묵게 한다. 이 방법으로는 몇몇 객실이 빈 객실이 된다. 구체적으로 15나 847 등 모든 소수 거듭제곱이 아닌 홀수 호실에는 아무도 묵지 않게 된다.

2.3.2. 소인수분해를 이용하는 방법

특정 좌석 s, 호차 c의 승객을 2^s3^c 호실에 묵게 한다(원래 호텔의 손님은 c=0, 1호차는 c=1로 한다). 모든 양의 정수는 유일하게 소인수 분해(산술의 기본 정리) 할 수 있으므로, 모든 손님이 방에 들어가고 같은 방에 2명 들어가지 않는다는 것을 알 수 있다. 예를 들어 2592 (2⁵3⁴) 호실의 손님은 4호차의 5번째 자리에 앉아 있던 승객이다. 소수 거듭제곱을 사용하는 방법과 마찬가지로, 이 방법에서는 몇몇 객실이 공실이 된다.

2.3.3. Interleaving method

각 승객에 대해, 십진법 등의 임의의 기수법으로 나타낸 n과 c의 자릿수를 비교하여 자릿수가 다른 경우, 같은 자릿수가 될 때까지 자릿수가 적은 쪽의 선행 영을 덧붙인다. 그리고 [호차 번호의 1자리]-[좌석 번호의 1자리]-[호차 번호의 2자리]-[좌석 번호의 2자리]-…와 같이 각 자릿수의 숫자를 interleave하여 객실 번호를 생성한다. 예를 들어 1729호실(즉, 1,729호실)에 있는 호텔(객차 #0) 투숙객은 01070209호실(즉, 1,070,209호실)로 이동하며, 789번 객차의 1234번 좌석에 있는 승객은 01728394호실(즉, 1,728,394호실)로 이동한다.

소수 거듭제곱을 사용하는 방법과는 달리, 이 방법은 호텔을 완전히 채우며, 인터리빙 과정을 반대로 수행하여 투숙객의 원래 객차와 좌석을 재구성할 수 있다. 먼저, 방 번호의 자릿수가 홀수이면 선행 영을 추가한다. 그런 다음 숫자를 두 개의 숫자로 디인터리빙한다. 객차 번호는 홀수 자릿수로 구성되고 좌석 번호는 짝수 자릿수로 구성된다. 물론, 원래 인코딩은 임의적이며 두 숫자의 역할이 바뀔 수 있다 (좌석-홀수 및 객차-짝수). 단, 일관되게 적용되어야 한다.

2.3.4. 삼각수를 이용하는 방법

원래 호텔의 투숙객을 (n² + n)/2 (즉, n번째 삼각수) 호실로 이동시킨다. 버스 단체 손님을 [(c + n - 1)² + (c + n - 1)]/2 + n (즉, (c + n - 1)번째 삼각수 + n) 호실에 숙박시킨다. 이렇게 하면 모든 객실이 중복 없이 채워진다.

이 대응 함수는 호텔을 1개 객실 너비의 깊이를 가진 무한히 높은 피라미드로 구조화하여 시각화할 수 있다. 피라미드의 최상단에 1호실이 있고, 다음 층에 2호실과 3호실이 있으며, 이하 동일하게 이어진다. 오른쪽 끝의 객실 집합으로 이루어진 열이 삼각수 호실에 대응한다. 이러한 객실이 (원래 호텔의 투숙객이 이동하여) 채워지면, 비어 있는 방은 원래 형태와 엄밀히 동일한 피라미드 형태가 된다. 따라서, 이 절차를 각 무한 집합(버스)마다 반복할 수 있다. 이를 한 대씩 수행하려면 무한한 단계 수가 필요하지만, 사전 계산 공식을 사용하면, 절차 중에 자신의 버스 순서가 왔을 때 승객은 자신의 방이 몇 번이 "될"지 결정할 수 있으며, 즉시 그곳으로 갈 수 있게 된다.

2.3.5. 임의의 열거 방법을 이용하는 방법

$S\; :=\; \backslash \{(a,\; b)\; \backslash mid\; a,\; b\; \backslash in\; \backslash mathbb\{N\}\backslash \}$라고 하자. $\backslash mathbb\{N\}$은 가산이므로 S^영어는 가산이며, 그 요소 s^영어₁, s^영어₂, ...을 열거할 수 있다. 여기서 s^영어_n = (a, b)라고 하고, a호차의 b번째 승객을 n호실에 배정한다(원래 호텔의 손님은 a^영어 = 0으로 한다). 이로써 모든 사람을 객실에 배정하는 함수가 만들어지며, 또한 이 배정은 어떤 객실도 남기지 않는다.

2.4. 더 깊은 무한의 계층

호텔이 바닷가에 인접해 있고, 무한대 척의 카페리가 와서, 각각 무한 대의 버스가 적재되어 있으며, 각각 무한 명의 승객이 타고 있다고 가정해 보자. 이는 3 "단계"의 무한을 포함하는 상황이며, 이전의 방법들을 확장하여 풀 수 있다.

소인수분해를 이용하는 방법은, 무한의 계층이 늘어날 때마다 새로운 소수를 추가함으로써 적용할 수 있다. 예를 들어, 2^s3^c5^f 와 같이 표현할 수 있는데, 여기서 f는 페리의 번호를 나타낸다.

소수 멱승을 사용하는 방법은, 소수의 멱승을 한 번 더 취함으로써 적용할 수 있으며, 작은 입력값에도 매우 큰 방 번호가 나온다. 예를 들어, 2번째 좌석 - 3번째 버스 - 2번째 페리 (주소 2-3-2)에 해당하는 승객의 방 번호는, 5⁴⁹ (밑은 2번째 홀수인 5, 지수는 3번째 홀수인 7의 2승 = 49)가 된다.

interleaving method에서는, 두 개가 아니라 세 개의 interleaving된 "strands"를 사용한다. 주소 2-3-2의 승객은 232호실로 가고, 주소 4935-198-82217의 승객은 008,402,912,391,587호실 (앞의 0은 제외)로 간다.

3. 분석

힐베르트의 역설은 진실 역설이다. 이는 직관에 반하는 결과로 이어지지만 수학적 증명을 통해 참임이 증명된다. "모든 방에 손님이 있다"와 "더 이상 손님을 수용할 수 없다"라는 명제는 무한히 많은 방이 있을 때 논리적 동치가 아니다.

이러한 상황은 직관에 반하는 것처럼 보일 수 있다. 무한한 것들의 집합은 유한한 것들의 집합의 속성과는 매우 다르다. 힐베르트의 그랜드 호텔의 역설은 칸토어의 초한수 이론을 사용하여 이해할 수 있다. 따라서 한 개 이상의 방이 있는 일반적인 (유한한) 호텔에서 홀수 번호의 방의 수는 전체 방의 수보다 분명히 적다. 그러나 힐베르트의 그랜드 호텔에서는 홀수 번호의 방의 양이 전체 방의 "수"보다 적지 않다. 수학적으로, 홀수 번호의 방을 포함하는 부분 집합의 기수는 모든 방의 집합의 기수와 같다. 실제로, 무한 집합은 동일한 기수의 진부분 집합을 갖는 집합으로 특징지어진다. 가산 집합(자연수와 같은 기수를 가진 집합)의 경우 이 기수는 $\backslash aleph\_0$이다.

다시 말하면, 모든 가산 무한 집합에 대해, 가산 무한 집합이 자연수를 포함하더라도 가산 무한 집합을 자연수 집합에 매핑하는 전단사 함수가 존재한다. 예를 들어, 정수의 몫으로 표현할 수 있는 수인 유리수의 집합은 자연수를 부분 집합으로 포함하지만, 유리수는 가산적이므로 자연수 집합보다 크지 않다. 즉, 자연수에서 유리수로의 전단사 함수가 존재한다.

무한 개의 객실이 있고, "만실"인 가상 호텔을 생각해 보자. 객실 수가 유한인 경우, "만실인 것"과 "새로 온 손님을 재울 수 없는 것"은 동치이지만(비둘기집 원리), 무한 호텔에서는 그렇지 않다.

4. 대중문화에서의 등장

* BBC Learning Zone^영어에서는 1996년 단편 교육 다큐멘터리 드라마 "[https://www.imdb.com/title/tt0443537/ Hotel Hilbert]"를 반복 방송했다. 젊은 여성 투숙객 피오나 나이트(Fiona Knight^영어, finite(유한)을 비튼 말)의 시각으로 본 호텔을 무대로 하며, 무한의 개념에 대해 교육하는 것을 목표로 했다.
* 수학자이자 SF 작가인 루디 라커의 소설 『White Light (novel)^영어』에는 힐베르트의 역설을 바탕으로 한 호텔이 등장하며, 이야기의 주인공이 게오르크 칸토어를 만나는 장면이 있다.
* 스티븐 백스터의 SF 소설 『트랜센던트』에는 호텔이 아닌 우주선 전사를 사용하는 방식으로 수정된 역설에 기반한 설명으로, 무한의 성질에 대한 간단한 논의가 있다.
* 제프리 A. 랜디스의 네뷸러 상 수상 단편 소설 「Ripples in the Dirac Sea^영어」에서는 무한으로 채워진 디랙의 바다가 여전히 입자를 받아들일 수 있는 이유를 설명하기 위해 힐베르트 호텔을 사용한다.
* 페터 회의 소설 『Miss Smilla's Feeling for Snow^영어』에서는, 호텔 지배인과 투숙객이 늦게 온 사람이 자신의 방과 사생활을 확보할 수 있도록 일부러 수고를 들인다는 점에 여주인공이 감탄한다.
* Ivar Ekeland^영어의 아동 소설 『The Cat in Numberland』에서는 "미스터 힐베르트"와 그의 아내가 모든 정수를 위해 무한 호텔을 운영하고 있다. 이야기는 유리수에 대한 삼각수를 이용하는 방법을 사용하여 진행된다.
* 윌 와일스의 소설 『시간 없는 호텔』에서는 무한히 큰 모텔을 소재로 하고 있으며, 악당의 이름은 "힐베르트"이다.
* 레지날드 힐의 소설 『이인관』에서는 등장인물 샘이 힐베르트 호텔의 역설을 언급한다.
* Naum Ya. Vilenkin^영어의 단편 소설 『이상한 호텔』(종종 스타니스와프 렘의 작품으로 오인됨)에서는 힐베르트의 무한 호텔이 무한한 수의 새로운 주인이 왔을 때 재편성되는 방법을 보여준다.
* John Roderick (musician)^영어과 켄 제닝스는 옴니버스 팟캐스트의 에피소드 "[https://web.archive.org/web/20180912165757/https://www.omnibusproject.com/podcasts/the-hilbert-hotel-entry-587lk0207.htm The Hilbert Hotel Entry]"에서 이 호텔에 대해 논의했다.
* 앨런 무어와 케빈 오닐의 만화 『리그 오브 엑스트라오디너리 젠틀맨』 시리즈의 네 번째 편 "템페스트"에는 인피니티라는 악당이 등장한다. 이야기에서는 악당이 힐베르트의 역설을 바탕으로 한 호텔에 갈 것이 암시된다. 게오르크 칸토어에 대해서도 언급된다.
* 쿠라타 에미의 만화 『1만 10초 이야기』에는 무한 호텔을 테마로 한 단편이 있다.