9.4: Готель Infinity і кардинальність нескінченних наборів

Last updated
Save as PDF

Page ID: 65128

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Вищезазначене обговорення кардинальності включало в себе наступний важливий факт, який з'явився в Пропозиції$9.1.9$:

Дві скінченні$A$$B$ множини і мають однакову кардинальність тоді і тільки тоді, коли є біекція від$A$ до$B$.

Розширення цієї властивості на всі множини (а не лише кінцеві) є визначенням кардинальності для нескінченних множин:

Визначення$9.4.1$.

Два$A$ набори і$B$ мають однакову кардинальність, якщо існує біекція від$A$ до$B$.

Дві основні ідеї будуть розроблені в решті цієї глави:

Багато наборів мають таку ж кардинальність, як і$\mathbb{N}^{+}$. Це найменші нескінченні множини, і вони, як кажуть, незліченно нескінченні.
Не всі множини незліченно нескінченні: деякі набори більш нескінченні, ніж інші! Кажуть, що ці набори незліченні.

Почнемо з неформального обговорення деяких ідей, які беруть участь у підрахунку, а не відразу дивимося на офіційне визначення. По-перше, простий приклад за участю скінченних множин.

Приклад$9.4.2$.

Припустимо, готель має n номерів, пронумерованих$1,2,3, \ldots, n$.

Якщо$A$ це екскурсійна група$n$ людей$a_{1}, a_{2}, \ldots, a_{n}$, то у діловодця готелю явно не виникне труднощів присвоїти кожному з людей кімнату:$a_{i}$ можна поставити в номер$i$. Не залишиться порожніх кімнат.
$clipboard_e122265d5d1a1bd46a9257cd8250b6136.png$
Тепер, якщо$b$ приїжджає інша людина, яка хоче кімнату, то ситуація безнадійна. Немає можливості дати кожному з цих$n+ 1$ людей кімнату, не змушуючи двох з них розділити кімнату. Загалом:
Якщо гостей більше, ніж готельних номерів, то не у всіх може бути номер.
Це повторення принципу Pigeonhole$(9.2.1)$ SS.

Приклад$9.4.3$ (Hotel Infinity).

Тепер розглянемо готель з нескінченно великою кількістю номерів, пронумерованих$1,2,3, \ldots$. (Є по одній кімнаті для кожного$i \in \mathbb{N}^{+}$.)

Якщо$A$ це екскурсійна група$n$ людей$a_{1}, a_{2}, \ldots, a_{n}$, то у діловодця готелю, очевидно, не виникне труднощів подарувати кожному з людей номер:$a_{i}$ можна поставити в номер$i$. Залишиться багато порожніх кімнат.
$clipboard_eb3b04728bac7255d2bfa251e7a68d2e6.png$
Навіть якщо$A$ він нескінченний, а не кінцевий, з людьми$a_{1}, a_{2}, \ldots$, готельний клерк може вмістити їх усіх, поставивши$a_{i}$ в номер$i$. Не залишиться порожніх кімнат.
$clipboard_ed1c5ac7d5dd9d5a766839989fe26cf01.png$
Тепер припустимо, що, крім цієї туристичної групи, є ще одна людина$b$, яка також хоче кімнату. Незважаючи на те, що готель вже заповнений, готельний клерк може впоратися з цією ситуацією досить легко, перемістивши всіх в сусідню кімнату, щоб звільнити місце для$b$. Тобто, клерк може поставити У\[b \text { into room } 1 \text { and } a_{i} \text { in room } i+1 \text {. }\]
кожного буде своя кімната.
$clipboard_ed72140e3369dada470004e144b0add34.png$
Та ж ідея працює, навіть якщо замість однієї людини є ціла група$B$$n$ людей,$b_{1}, b_{2}, \ldots, b_{n}$ які хочуть кімнати. Клерк може поставити\[b_{j} \text { in room } j, \quad \text { and } \quad a_{i} \text { in room } i+n \text {. }\]
$clipboard_e0680c2a2ef92e8bc7fc859158b672342.png$
Може здатися, що виникла б проблема, якщо друга група$B$ складається з нескінченно багатьох людей$b_{1}, b_{2}, b_{3}, \ldots$, але розумний готельний клерк може вмістити навіть таку ситуацію. Зверніть увагу, що є нескінченно багато непарних номерів, тому всі вони$A$ можуть бути розміщені в цих кімнатах, а також є нескінченно багато парних номерів, тому всі вони$B$ можуть бути поміщені там. Точніше, клерк може поставити\[a_{i} \text { in room } 2 i-1, \quad \text { and } \quad b_{j} \text { in room } 2 j \text {. }\]
$clipboard_eede67c73df7d162d2f8bcb7d3a327411.png$
Навіть якщо є кілька з цих незліченно нескінченних туристичних груп, а не тільки 2 з них, вони всі можуть бути розміщені. А саме, припустимо, що існують$n$ тур-групи$A_{1}, A_{2}, A_{3}, \ldots, A_{n}$, і складіть таблицю (або матрицю) з$n$ нескінченно довгими рядками, в якій перераховані елементи$A_{i}$ в$i$ -му рядку. Тобто, якщо$a_{i, 1}, a_{i, 2}, a_{i, 3}, \ldots$ це список людей у$A_{i}$, то таблиця виглядає так:
\ begin {масив} {ccccccc}
A_ {1}: & a_ {1,1} & a_ {1,2} & a_ {1,3} & a_ {1,4} & a_ {1,5} &\ cdots\\
A_ {2}: & a_ {2,1} & a_ {2,2}} & a_ {2,3} & a_ {2,4} & a_ {2,5} &\ cdots\\
A_ {3}: & a_ {3,1} & a_ {3,2} & a_ {3,3} & a_ {3,4} & a_ {3,5} &\ cdots
\\\ vdots &\ vdots &\ vdots &\ vdots\\
A_ {n}: & a_ {n, 1} & a _ {n, 2} & a_ {n, 3} & a_ {n, 4} & a_ {n, 5} &\ cdots
\ кінець {масив}

Ми можемо призначити кімнати$1,2,3, \ldots$ до записів цієї таблиці, відрахувавши 1-й стовпець (від 1 до$n$), потім 2-й стовпець (починаючи з$n + 1$), потім 3-й стовпець (продовжуючи з того місця, де ми зупинилися після 2-го стовпця) тощо, як зазначено тут:\ [\ begin {array} {ccccccc}
1 & n+1 & 2 n+1 & 3 n+1 & 4 n+1 &\
cdots\\ a_ {1,1} & a_ {1,2} & a_ {1,3} & a_ {1,4} & a_ {1,5} &\\\\ Стрілка вниз &\\ вниз &\\ вниз &\\
cdots\\ 2 & n+2 4 п
+2 &\ cdots\\
a_ {2,1} & a_ {2,2} & a_ {2,3} & a_ {2,4} & a_ {2,5} &\\\ Стрілка вниз &\\ Стрілка вниз і\\
cdots\\ 3 & n+3 & 3 n+3 & 3 n+3 & 4 n+3 n+3 n+3 & 4
n+3 n+3 & 3 n+3 n+3 n+3 n+3 & 4 n+3\\ cdots\
a _ {3,1} & a_ {3,2} & a_ {3,3} & a_ {3,4} & a_ {3,5} &\\\\ стрілка вниз &\\ стрілка вниз &
\\ вниз &\\ cdots\\ vdots &\ vdots &\ vdots &
\ vdots &\ vdots &\ vdots &\ vdots &\ vdots &\
\ vdots &\ стрілка вниз &\ стрілка вниз &\\ вниз &\ cdots\\
n & 2 n & 3 n & 4 n & 5 n &\ cdots\\
a_ {n, 1} & a_ {n, 2} & a_ {n, 3} & a_ {n, 4} & a_ {n, 5} &
\ end {масив}\]

Це призначає різний номер кімнати кожному з людей, тому у кожного є своя кімната.

Зауваження.

Інший спосіб для готельний клерк знайти це рішення - відзначити, що існує нескінченно багато номерів, які збігаються з$i$ модулем$n$, тому всі вони$A_{i}$ можуть бути розміщені в цих кімнатах.
Видно, що гість$a_{i,j}$ закріплений за номером$i+ (j −1)n$, але у нас немає необхідності в цій формулі.

Йдучи далі, навіть якщо було нескінченно багато нескінченних екскурсійних груп$A_{1}, A_{2}, \ldots$, всі вони могли бути розміщені. (Ми припускаємо, що кожна екскурсійна група незліченно нескінченна, і що кількість груп незліченно нескінченна.) Щоб побачити це, почніть з розгляду нескінченно великої таблиці (або матриці),$A_{i}$ в якій перераховані елементи у тому рядку:\ [\ begin {array}
{ccccccc} A_ {1}: & a_ {1,2} & a_ {1,3} & a_ {1,4} & a_ {1,5} &\ cdots\\
A_ {2}: & a_ {1,4} _ {2,1}$i$ & a_ {2,2} & a_ {2,3} & a_ {2,4} & a_ {2,5} &\ cdots\\
A_ {3}: & a_ {3,1} & a_ {3,2} & a_ {3,3} & a_ {3,4} & a_ {3,5} &\ cdots\
A_ {4}: & a_ {4,1} a_ {4,2} & a_ {4,3} & a_ {4,4} & a_ {4,5} &\ cdots\
A_ {5}: & a_ {5,1} & a_ {5,2} & a_ {5,3} & a_ {5,4} & a_ {5,5} &\ cdots\\\ vdots &
\ vdots &\ vdots &\ vdots &\ vdots &\ vdots &\ ddots
\ end {масив}\]
Ми можемо призначити кімнати$1,2,3, \ldots$ до записів цієї таблиці наступним чином:
- Почніть з 1 у верхньому лівому куті.
- Потім помістіть 2 у верхній частині другого стовпчика і рухайтеся по діагоналі (вниз і вліво), щоб розмістити 3.
- Потім поставте 4 у верхній частині третього стовпчика і рухайтеся по діагоналі (вниз і вліво), щоб розмістити 5 і 6.
- Потім поставте наступне число (а саме 7) на першому відкритому місці у верхньому ряду (а саме вгорі четвертого стовпчика), і рухайтеся по діагоналі (вниз і вліво), щоб розмістити наступні цифри (а саме 8, 9 і 10), поки в першому стовпчику не буде поміщено число (а саме 10).
- Продовжуйте, рухаючись до першого відкритого місця у верхньому ряду, і повторюючи нескінченно.
  $clipboard_efe2ae33b99a17d7ee8d6b38ec6bfbf42.png$

Ніякі записи таблиці не пропускаються з нумерації, а номери номерів не повторюються, тому у кожного гостя є своя кімната.

Зауваження

Можна показати, що guest$a_{i,j}$ поміщено до кімнати (i+j−1 2) + i, але у нас немає потреби у цій формулі.

Може здатися, що Hotel Infinity міг вмістити кожен набір туристів, але це не так. Наприклад, ми побачимо в розділі$9.6$, що якщо всі реальні номери хочуть номери в готелі, то деякі з них доведеться ділитися. Іншими словами, множина$\mathbb{R}$ дійсних чисел незліченна.

ІНША ТЕРМІНОЛОГІЯ.

Готель Infinity часто називають «Готелем Гільберта» на честь німецького математика Девіда Гільберта (1862—1943), який, мабуть, першим розповідав про такий готель (на лекціях у Німеччині в 1924 році).

Визначення\(9.4.1\).

Приклад\(9.4.2\).

Приклад\(9.4.3\) (Hotel Infinity).

Зауваження.

Зауваження

ІНША ТЕРМІНОЛОГІЯ.