Skip to main content
LibreTexts - Ukrayinska

4.3: Зігзагоподібний метод Кантора

  • Page ID
    53110
  • \( \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}}\)

    Template:MathJaxZach

    Ми вже розглянули деякі «легкі» перерахування. Зараз ми розглянемо дещо складніше. Розглянемо набір пар натуральних чисел, який ми визначили в розділі 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\] І це встановлює наступне:

    Пропозиція\(\PageIndex{1}\)

    \(\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\).