4.7: Зменшення

Last updated
Save as PDF

Page ID: 53071

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

Ми показали$\Pow{\PosInt}$, що бути незліченним аргументом діагоналізації. Ми вже мали доказ того$\Bin^\omega$, що множина всіх нескінченних послідовностей$0$ s і$1$ s, незліченна. Ось ще один спосіб, який ми можемо довести, що$\Pow{\PosInt}$ це незліченно: Показати, що якщо$\Pow{\PosInt}$ підраховується, то також$\Bin^\omega$ підраховується. Оскільки ми знаємо,$\Bin^\omega$ що не підлягає зліку, не$\Pow{\PosInt}$ може бути ні. Це називається зведенням однієї проблеми до іншої - в цьому випадку ми зводимо проблему перерахування$\Bin^\omega$ до проблеми перерахування$\Pow{\PosInt}$. Рішення останнього - перерахування$\Pow{\PosInt}$ - дасть рішення для першого - перерахування$\Bin^\omega$.

Як зменшити проблему перерахування множини$B$ до проблеми перерахування множини$A$? Ми надаємо спосіб перетворення$A$ перерахування в перерахування$B$. Найпростіший спосіб зробити це - визначити суб'єктивну функцію$f\colon A \to B$. Якщо$x_1$,$x_2$,... перераховує$A$, то$f(x_1)$,$f(x_2)$,... перерахував би$B$. У нашому випадку ми шукаємо суб'єктивну функцію$f\colon \Pow{\PosInt} \to \Bin^\omega$.

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

Покажіть, що якщо є ін'єкційна функція$g\colon B \to A$, і$B$ незліченна, то так і є$A$. Зробіть це, показуючи, як ви можете використовувати,$g$ щоб перетворити$A$ перерахування в один з$B$.

Доказ теореми 4.6.2 шляхом скорочення.

Припустимо, що$\Pow{\PosInt}$ були підрахункові, і, таким чином, що існує перерахування його,$Z_{1}$,$Z_{2}$,$Z_{3}$,...

Визначте функцію,$f \colon \Pow{\PosInt} \to \Bin^\omega$ дозволивши$f(Z)$ бути послідовністю,$s_{k}$ такою, що$s_{k}(n) = 1$ iff$n \in Z$, і в$s_k(n) = 0$ іншому випадку. Це чітко визначає функцію, оскільки всякий раз$Z \subseteq \PosInt$, будь-хто$n \in \PosInt$$Z$ або є елементом чи ні. Наприклад, набір$2\PosInt = \{2, 4, 6, \dots\}$ позитивних парних чисел зіставляється з послідовністю$010101\dots$, порожній набір отримує зіставлено на карту$0000\dots$ і$\PosInt$ сам набір до$1111\dots$.

Це також є суб'єктивним: Кожна послідовність$0$ s і$1$ s відповідає деякому набору натуральних чисел, а саме той, який має в якості своїх членів ті цілі числа, що відповідають місцям, де послідовність має$1$ s Точніше, припустимо $s \in \Bin^\omega$. Визначити$Z \subseteq \PosInt$ по:\[Z = \Setabs{n \in \PosInt}{s(n) = 1}\nonumber\] Тоді$f(Z) = s$, як можна перевірити, порадившись з визначенням$f$.

Тепер розглянемо список\[f(Z_1), f(Z_2), f(Z_3), \dots\nonumber\] Оскільки$f$ є суб'єктивним, кожен член$\Bin^\omega$ повинен відображатися як значення$f$ для деякого аргументу, і тому повинен з'явитися у списку. Таким чином, цей список повинен перерахувати всі$\Bin^\omega$.

Так що, якби$\Pow{\PosInt}$ були підрахункові,$\Bin^\omega$ було б підраховано. Але$\Bin^\omega$ є незліченним (теорема 4.6.1). Отже$\Pow{\PosInt}$, незліченно. ◻

Легко заплутатися щодо напрямку, в якому йде скорочення. Наприклад, сюрктивна функція$g \colon \Bin^\omega \to B$ не встановлює, що$B$ є незліченним. (Розглянемо$g \colon \Bin^\omega \to \Bin$ визначено$g(s) = s(1)$, функція, яка відображає послідовність в і$0$ '$1$s до свого першого елемента. Він є суб'єктивним, тому що деякі послідовності починаються з,$0$ а деякі починаються с$1$. Але$\Bin$ є кінцевим.) Зауважте також, що функція$f$ повинна бути суб'єктивною, інакше аргумент не проходить через:$f(x_1)$$f(x_2)$,... тоді не буде гарантовано включати всі елементи$B$. Наприклад,\[h(n) = \underbrace{000\dots0}_{\text{$n$ $0$'s}}\nonumber\] визначає функцію$h\colon \PosInt \to \Bin^\omega$, але$\PosInt$ є підрахунковою.

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

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

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

Показати$\Nat^\omega$, що множина нескінченних послідовностей натуральних чисел є незліченним аргументом скорочення.

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

$P$Дозволяти множина функцій з множини натуральних чисел до множини$\{0\}$, і$Q$ нехай множина часткових функцій з множини натуральних чисел до множини$\{0\}$. Покажіть,$P$ що$Q$ підраховується, а не є. (Підказка: звести проблему перерахування$\Bin^\omega$ до перерахування$Q$).

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

$S$Дозволяти множина всіх суб'єктивних функцій від множини натуральних чисел до множини {0,1}, тобто$S$ складається з усіх сюрктивних$f\colon \PosInt \to \Bin$. Покажіть,$S$ що незліченно.

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

Показати, що набір всіх$\Real$ дійсних чисел є незліченним.