4.6: Незліченні набори

Last updated
Save as PDF

Page ID: 53059

$ \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

Деякі множини, такі як безліч$\PosInt$ натуральних чисел, нескінченні. Поки що ми бачили приклади нескінченних множин, які всі були підрахунковими. Однак існують також нескінченні множини, які не мають цієї властивості. Такі набори називаються незліченними.

Перш за все, мабуть, вже дивно, що існують незліченні набори. Для будь-якого лічильного$A$ множини існує суб'єктивна функція$f \colon \PosInt \to A$. Якщо набір є незліченним, такої функції немає. Тобто, жодна функція відображення нескінченно багато елементів to не$A$ може вичерпати все з$A$.$\PosInt$ Таким чином, є «більше» елементів,$A$ ніж нескінченно багато позитивних цілих чисел.

Як би довести, що набір незліченний? Ви повинні показати, що такої суб'єктивної функції не може існувати. Аналогічно, ви повинні показати, що елементи$A$ не можуть бути перераховані в один спосіб нескінченний список. Найкращий спосіб зробити це - показати, що кожен список елементів$A$ повинен залишити принаймні один елемент; або що жодна функція не$f\colon \PosInt \to A$ може бути суб'єктивною. Ми можемо зробити це за допомогою діагонального методу Кантора. З огляду на список елементів$A$, скажімо,$x_1$,$x_2$,,..., ми будуємо ще один елемент,$A$ який за своєю конструкцією не може бути в цьому списку.

Наш перший приклад - це набір всіх$\Bin^\omega$ нескінченних, негаппісних послідовностей$0$'s та$1$'s.

Теорема$\PageIndex{1}$

$\Bin^\omega$незліченна.

Доказ. Припустимо, шляхом протиріччя,$\Bin^\omega$ тобто, припустимо, що існує список$s_{1}$$s_{2}$,$s_{3}$,$s_{4}$,,... всіх елементів$\Bin^\omega$. Кожен з них сам по собі$s_i$ є нескінченною послідовністю$1$'s і$0$'s. Давайте назвемо$j$ -й елемент$i$ -ої послідовності в цьому списку$s_i(j)$. Тоді$i$ -а послідовність$s_i$ дорівнює\[s_i(1), s_i(2), s_i(3), \dots\nonumber\]

Ми можемо організувати цей список, і елементи кожної послідовності$s_i$ в ньому, в масиві:\[\begin{array}{c|c|c|c|c|c} & 1 & 2 & 3 & 4 & \dots \\\hline 1 & \mathbf{s_{1}(1)} & s_{1}(2) & s_{1}(3) & s_1(4) & \dots \\\hline 2 & s_{2}(1)& \mathbf{s_{2}(2)} & s_2(3) & s_2(4) & \dots \\\hline 3 & s_{3}(1)& s_{3}(2) & \mathbf{s_3(3)} & s_3(4) & \dots \\\hline 4 & s_{4}(1)& s_{4}(2) & s_4(3) & \mathbf{s_4(4)} & \dots \\\hline \vdots & \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots} \end{array}\nonumber\] Мітки вниз збоку дають номер послідовності в списку$s_1$$s_2$,,...; цифри у верхній мітці елементів окремих послідовності. Наприклад,$s_{1}(1)$ це ім'я для будь-якого числа, a$0$ або a$1$, є першим елементом у послідовності$s_{1}$, і так далі.

Тепер ми будуємо нескінченну$0$ послідовність$\overline{s}$, з і$1$ які не можуть бути в цьому списку. Визначення$\overline{s}$ буде залежати від переліку$s_1$,$s_2$,... Будь-який нескінченний список нескінченних послідовностей з$0$ і$1$ 's породжує нескінченну послідовність,$\overline{s}$ яка гарантовано не з'явиться у списку.

Для визначення вказуємо$\overline{s}$, які всі його елементи, тобто вказуємо$\overline{s}(n)$ для всіх$n \in \PosInt$. Ми робимо це, зчитуючи діагональ масиву вище (звідси назва «діагональний метод»), а потім змінюючи кожен$1$ на a$0$ і кожен$0$ на a$1$. Більш абстрактно ми$\overline{s}(n)$ визначаємо бути$0$ або$1$ відповідно до того,$n$ -й елемент діагоналі$s_n(n)$, є$1$ або$0$. \[\overline{s}(n) = \begin{cases} 1 & \text{if $s_{n}(n) = 0$}\\ 0 & \text{if $s_{n}(n) = 1$}. \end{cases}\nonumber\]Якщо вам подобаються формули краще, ніж визначення за відмінками, ви також можете визначити$\overline{s}(n) = 1 - s_n(n)$.

Ясно$\overline{s}$ це нескінченна послідовність$0$ з і$1$ в, так як це просто дзеркальна послідовність в послідовності з і$0$ '$1$s, які з'являються на діагоналі нашого масиву. Так$\overline{s}$ є елементом$\Bin^\omega$. Але це не може бути в списку$s_1$$s_2$,... Чому б і ні?

Це не може бути першою послідовністю у списку$s_1$, оскільки вона відрізняється від$s_1$ першого елемента. Що б$s_1(1)$ там не було, ми$\overline{s}(1)$ визначили протилежне. Це не може бути другою послідовністю у списку, тому що$\overline{s}$ відрізняється від$s_2$ другого елемента: if$s_2(2)$$\overline{s}(2)$ is$0$$1$, is, і навпаки. І так далі.

Точніше: якби$\overline{s}$ були в списку, були б$k$ такі, що$\overline{s} = s_{k}$. Дві послідовності ідентичні, якщо вони узгоджуються в кожному місці, тобто для будь-якого$n$,$\overline{s}(n) = s_{k}(n)$. Так, зокрема, приймаючи$n = k$ як особливий випадок,$\overline{s}(k) = s_{k}(k)$ доведеться провести. $s_k(k)$є або$0$ або$1$. Якщо це так,$0$ то$\overline{s}(k)$ має бути$1$ —ось як ми визначили$\overline{s}$. Але якщо$s_k(k) = 1$ тоді, знову ж таки через те, як ми визначили$\overline{s}$,$\overline{s}(k) = 0$. У будь-якому випадку$\overline{s}(k) \neq s_{k}(k)$.

Ми почали з припущення, що існує список елементів$\Bin^\omega$,,$s_1$$s_2$,... З цього списку ми побудували послідовність,$\overline{s}$ яка, як ми довели, не може бути в списку. Але це, безумовно, послідовність з і$0$ '$1$s, якщо всі$s_i$ є послідовності з$0$' s і$1$ 's, тобто,$\overline{s} \in \Bin^\omega$. Це показує, зокрема, що не може бути списку всіх елементів$\Bin^\omega$, оскільки для будь-якого такого списку ми також могли б побудувати послідовність$\overline{s}$ гарантовано не буде в списку, тому припущення, що є список всіх послідовностей в $\Bin^\omega$призводить до протиріччя. ◻

Цей метод доказування називається «діагоналізацією», оскільки він використовує діагональ масиву для визначення$\overline{s}$. Діагоналізація не повинна включати наявність масиву: ми можемо показати, що множини не підлягають підрахунку, використовуючи подібну ідею, навіть якщо немає масиву і немає фактичної діагоналі.

Теорема$\PageIndex{2}$

$\Pow{\PosInt}$не підлягає зліченню.

Доказ. Діємо так само, показуючи, що для кожного списку підмножин$\PosInt$ існує підмножина$\PosInt$ яких не може бути в списку. Припустимо, що нижче наведено список підмножин$\PosInt$: Тепер\[Z_{1}, Z_{2}, Z_{3}, \dots\nonumber\] ми визначаємо набір,$\overline{Z}$ такий$n \in \PosInt$, що для будь-якого,$n \in \overline{Z}$ iff$n \notin Z_{n}$:\[\overline{Z} = \Setabs{n \in \PosInt}{n \notin Z_n}\nonumber\]$\overline{Z}$ явно множина натуральних чисел, так як за припущенням$Z_n$ кожне є, і таким чином$\overline{Z} \in \Pow{\PosInt}$. Але$\overline{Z}$ не може бути в списку. Щоб показати це, ми встановимо, що для кожного$k \in \PosInt$,$\overline{Z} \neq Z_k$.

Так нехай$k \in \PosInt$ буде довільним. Ми визначили$\overline{Z}$ так, що для будь-якого$n \in \PosInt$,$n \in \overline{Z}$ якщо$n \notin Z_n$. Зокрема, взявши$n=k$,$k \in \overline{Z}$ іфф$k \notin Z_k$. Але це показує$\overline{Z} \neq Z_k$, що, оскільки$k$ є елементом одного, а не іншого, і так$\overline{Z}$ і$Z_k$ мають різні елементи. Так як$k$ був$\overline{Z}$ довільним, немає в списку$Z_1$,$Z_2$,... ◻

Попереднє доказ не згадував діагональ, але ви можете думати про це як про діагональ, якщо ви зобразите її таким чином: Уявіть набори$Z_1$$Z_2$,,..., записані в масиві, де кожен елемент$j \in Z_i$ вказаний у$j$ -му стовпці. Скажімо, перші чотири набори в цьому списку є$\{1,2,3,\dots\}$$\{2, 4, 6, \dots\}$,$\{1,2,5\}$,, і$\{3,4,5,\dots\}$. Тоді масив буде починатися з\[\begin{array}{r@{}rrrrrrr} Z_1 = \{ & \mathbf{1}, & 2, & 3, & 4, & 5, & 6, & \dots\}\\ Z_2 = \{ & & \mathbf{2}, & & 4, & & 6, & \dots\}\\ Z_3 = \{ & 1, & 2, & & & 5\phantom{,} & & \}\\ Z_4 = \{ & & & 3, & \mathbf{4}, & 5, & 6, & \dots\}\\ \vdots & & & & & \ddots \end{array}\nonumber\] Тоді$\overline{Z}$ це набір, отриманий шляхом зниження діагоналі, залишаючи будь-які числа, які з'являються уздовж діагоналі і включають ті,$j$ де масив має прогалину в$j$ -му рядку/стовпці. У наведеному вище випадку ми б випустили$1$ і$2$,$3$ включивши$4$, випустили тощо.

Проблема$\PageIndex{1}$

Покажіть,$\Pow{\Nat}$ що не можна злічити діагональним аргументом.

Проблема$\PageIndex{2}$

Показати, що множина функцій не$f \colon \PosInt \to \PosInt$ злічується за допомогою явного діагонального аргументу. Тобто показати, що якщо$f_1$,$f_2$,..., це список функцій і кожна$f_i\colon \PosInt \to \PosInt$, то є деякі$\overline{f}\colon \PosInt \to \PosInt$ немає в цьому списку.