4.3: Зігзагоподібний метод Кантора
- Page ID
- 53110
Ми вже розглянули деякі «легкі» перерахування. Зараз ми розглянемо дещо складніше. Розглянемо набір пар натуральних чисел, який ми визначили в розділі 1.5 таким чином:\[\Nat \times \Nat = \Setabs{\tuple{n,m}}{n,m \in \Nat}\nonumber\] Ми можемо організувати ці впорядковані пари в масив, як так:\[\begin{array}{ c | c | c | c | c | c} & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \dots \\ \hline \mathbf 0 & \tuple{0,0} & \tuple{0,1} & \tuple{0,2} & \tuple{0,3} & \dots \\ \hline \mathbf 1 & \tuple{1,0} & \tuple{1,1} & \tuple{1,2} & \tuple{1,3} & \dots \\ \hline \mathbf 2 & \tuple{2,0} & \tuple{2,1} & \tuple{2,2} & \tuple{2,3} & \dots \\ \hline \mathbf 3 & \tuple{3,0} & \tuple{3,1} & \tuple{3,2} & \tuple{3,3} & \dots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}\nonumber\] Очевидно, кожна впорядкована пара в\(\Nat \times \Nat\) буде з'являтися рівно один раз в масиві. Зокрема,\(\tuple{n,m}\) з'явиться в\(n\) -му рядку і\(m\) стовпці. Але як ми організуємо елементи такого масиву в «одновимірний» список? Шаблон у масиві нижче демонструє один із способів зробити це (хоча, звичайно, є багато інших варіантів):\[\begin{array}{ c | c | c | c | c | c | c} & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 &\dots \\ \hline \mathbf 0 & 0 & 1& 3 & 6& 10 &\ldots \\ \hline \mathbf 1 &2 & 4& 7 & 11 & \dots &\ldots \\ \hline \mathbf 2 & 5 & 8 & 12 & \ldots & \dots&\ldots \\ \hline \mathbf 3 & 9 & 13 & \ldots & \ldots & \dots & \ldots \\ \hline \mathbf 4 & 14 & \ldots & \ldots & \ldots & \dots & \ldots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots&\ldots & \ddots\\ \end{array}\nonumber\] Цей шаблон називається зигзагоподібним методом Кантора. Він перераховує\(\Nat \times \Nat\) наступним чином:\[\tuple{0,0}, \tuple{0,1}, \tuple{1,0}, \tuple{0,2}, \tuple{1,1}, \tuple{2,0}, \tuple{0,3}, \tuple{1,2}, \tuple{2,1}, \tuple{3,0}, \dots\nonumber\] І це встановлює наступне:
\(\Nat \times \Nat\)піддається зліченню.
Доказ. Давайте\(f \colon \Nat \to \Nat\times\Nat\) візьмемо кожен\(k \in \Nat\) кортеж\(\tuple{n,m} \in \Nat \times \Nat\) такий, що\(k\) є значенням\(n\) го рядка і\(m\) го стовпця в зигзагоподібному масиві Кантора. ◻
Цей прийом також досить красиво узагальнює. Наприклад, ми можемо використовувати його для перерахування множини впорядкованих трійок натуральних чисел, тобто:\[\Nat \times \Nat \times \Nat = \Setabs{\tuple{n,m,k}}{n,m,k \in \Nat}\nonumber\] Ми вважаємо декартовим\(\Nat \times \Nat\) добутком з\(\Nat\), тобто,\[\Nat^3 = (\Nat \times \Nat) \times \Nat = \Setabs{\tuple{\tuple{n,m},k}}{n, m, k \in \Nat }\nonumber\] і таким чином ми можемо перерахувати\(\Nat \times \Nat \times \Nat\) \(\Nat^3\)з масивом, позначаючи одну вісь з перерахуванням\(\Nat\), а іншу вісь з перерахуванням\(\Nat^2\):\[\begin{array}{ c | c | c | c | c | c} & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \dots \\ \hline \mathbf{\tuple{0,0}} & \tuple{0,0,0} & \tuple{0,0,1} & \tuple{0,0,2} & \tuple{0,0,3} & \dots \\ \hline \mathbf{\tuple{0,1}} & \tuple{0,1,0} & \tuple{0,1,1} & \tuple{0,1,2} & \tuple{0,1,3} & \dots \\ \hline \mathbf{\tuple{1,0}} & \tuple{1,0,0} & \tuple{1,0,1} & \tuple{1,0,2} & \tuple{1,0,3} & \dots \\ \hline \mathbf{\tuple{0,2}} & \tuple{0,2,0} & \tuple{0,2,1} & \tuple{0,2,2} & \tuple{0,2,3} & \dots\\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}\nonumber\] Таким чином, використовуючи метод, подібний до зигзагоподібного методу Кантора, ми можемо аналогічно отримати перерахування \(\Nat^3\). І ми можемо продовжувати йти, отримання перерахування\(\Nat^n\) для будь-якого натурального числа\(n\). Отже, у нас є:
Пропозиція\(\PageIndex{2}\)
\(\Nat^n\)підраховується, для кожного\(n \in \Nat\).