Skip to main content
LibreTexts - Ukrayinska

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

  1. Last updated
  2. Save as PDF
  • Page ID
    65143

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

    Попередній розділ показав, що багато наборів (включаючи\(\mathbb{N}\)\(\mathbb{Z}\), і\(\mathbb{Q}\)) піддаються підрахунку. Тепер ми побачимо, що деякі набори не підлягають зліченню.

    9.6А. Реалів є незліченними.

    Ось, мабуть, найважливіший приклад незліченного набору:

    Теорема\(9.6.1\).

    Безліч\(\mathbb{R}\) дійсних чисел є незліченним.

    \(\mathbb{R}\)Якби були підрахунковими, то всі його підмножини були б підрахунковими. Таким чином, щоб встановити теорему\(9.6.1\), досить знайти незліченну підмножину\(\mathbb{R}\). Ось кілька відомих прикладів підмножин:

    Позначення\(9.6.2\).

    Для\(a, b \in \mathbb{R}\) з\(a < b\):

    • відкритий інтервал:\((a, b)=\{x \in \mathbb{R} \mid a<x<b\}\).
    • замкнутий інтервал:\([a, b]=\{x \in \mathbb{R} \mid a \leq x \leq b\}\).
    • напіввідкритий інтервал:\([a, b)=\{x \in \mathbb{R} \mid a \leq x<b\}\) або\((a, b]=\{x \in \mathbb{R} \mid a<x \leq b\}\).

    Ми побачимо, що всі ці інтервали незліченні. Ось один із прикладів:

    Теорема\(9.6.3\).

    Інтервал\([0, 1)\) незліченний.

    Доказ

    ЗА ПРОТИРІЧЧЯМ.

    Припустимо\([0, 1)\), є підрахунковим. (Це призведе до протиріччя.) Це означає, що існує список\(x_{1}\)\(x_{2}\)\(x_{3}\),,,. всіх чисел в\([0, 1)\). Для отримання протиріччя ми будемо використовувати метод під назвою Аргумент діагоналізації Кантора. Він був відкритий математиком Георгом Кантором в 19 столітті.

    Кожне число в\([0, 1)\) може бути записано як десяткове число у вигляді 0. \(d_{1}d_{2}d_{3}\)., де кожна\(d_{k}\) - цифра (0, 1, 2, 3, 4, 5, 6, 7, 8 або 9). Зокрема, ми можемо написати кожен\(x_{i}\) в такому вигляді:\[x_{i}=0 . x_{i, 1} x_{i, 2} x_{i, 3} x_{i, 4} x_{i, 5} \ldots\]

    Тоді ми можемо скласти список усіх цих десяткових знаків (опускаючи провідні 0 у кожному з них):\ [\ begin {вирівняні}
    x_ {1} =&. x_ {1,1} x_ {1,2} x_ {1,3} x_ {1,4} x_ {1,5}\ cdots\\ x_ {2} =&. x_ {2,1} x_ {2,1}
    x_ {2,2} x_ {2,2} x_ {2,2} x_ {2,2} x_ {2,2} x_ {2,2} _ {2,3} x_ {2,4} x_ {2,5}\ cdots\\
    x_ {3} =&. x_ {3,1} x_ {3,2} x_ {3,3} } x_ {3,4} x_ {3,5}\ cdots\\ x_ {4} =&.
    x_ {4,1} x_ {4,2} x_ {4,3} x_ {4,4} x_ {4,5}\ cdots\\ x_ {5} =&. x_ {5,1} x_ {5,2} x_ {5,3} x_ {5,3}
    x_ {5,4} x_ {5,3} x_ {5,4} x_ {5,4} x_ {5,4} x_ {5,4} x_ {5,4} x_ {5,4} x_ {5,4} x_ {5,4} _ {5,5}\ cdots
    \\ vdots &\ vdots
    \ кінець {вирівняні}\]

    Права частина може розглядатися як масив цифр, і тепер ми зосередимося на\(x_{i,i}\) діагональних записах цього масиву, які обведені в наступному малюнку:

    clipboard_e206aa7796c5d632f4a040bdfa5f4776b.png

    Вони утворюють послідовність\(x_{1,1}, x_{2,2}, x_{3,3}, \ldots\).

    Ключ до доказу полягає в тому, щоб зробити нову\(d_{1}, d_{2}, d_{3}, \ldots\) послідовність цифр, таку, що\[d_{1} \neq x_{1,1}, \quad d_{2} \neq x_{2,2}, \quad d_{3} \neq x_{3,3}, \text { etc. }\]

    Це означає, що кожен член нової послідовності відрізняється від відповідного члена діагональної послідовності. (Ця ідея вибору послідовності, яка повністю відрізняється від діагоналі, називається діагоналлю Кантора, тому що її винайшов математик Георг Кантор.) Також, щоб уникнути проблем, що виходять від того\(.999 \cdots=1.000 \cdots\), що, не варто використовувати цифри 0 і 9. Послідовність\(\left\{d_{i}\right\}\) може бути побудована різними способами: просто обов'язково вибирайте кожну\(d_{i}\) цифру, яка не є\(x_{i,i}\) (і не є 0 або 9). Наприклад, ми могли б дозволити\[d_{i}= \begin{cases}1 & \text { if } x_{i, i} \neq 1 \\ 5 & \text { if } x_{i, i}=1\end{cases}\]

    Тепер нехай\[d=0 . d_{1} d_{2} d_{3} \ldots \in[0,1).\]

    Для кожного\(i\) ми переконалися в тому\(d_{i} \neq x_{i, i}\), що це означає, що\(i\) й цифра d відрізняється від\(i\) ї цифри\(x_{i}\). Тому для кожного\(i\) у нас є\(d \neq x_{i} \text { * }\). Так\(d\) це елемент того\([0, 1)\), що немає в списку\(x_{1}, x_{2}, x_{3}, \ldots\). Це суперечить тому, що\(x_{1}, x_{2}, x_{3}, \ldots\) є списком всіх чисел в\([0, 1)\).

    Вправа\(9.6.4\).
    1. Показати, що інтервал\((0, 1)\) є незліченним. [Підказка:\ ([0,1) =( 0,1)\ чашка\ {0\}) незліченна.]
    2. Припустимо\(a, b \in \mathbb{R}\). Покажіть, що якщо\(a < b\), то інтервал\((a, b)\) має таку ж кардинальність, як\((0, 1)\). [Підказка: Визначити\(f:(0,1) \rightarrow(a, b)\) по\(f(x)=a+(b-a) x\).]
    3. Припустимо\(a \in \mathbb{R}\). Показати, що інтервал\((a, \infty)\) має ту саму кардинальність, що і\((0, 1)\). [Підказка: Визначити\ (f: (0,1)\ стрілка вправо (a,\ infty)) за\ (f (x) =( 1/x) +a-1).]
    Слідство\(9.6.5\).

    Якщо\(a, b \in \mathbb{R}\) і\(a < b\), то інтервали\((a, b)\)\([a, b]\),\([a, b)\),,\((a, b]\) і незліченні.

    Вправа\(9.6.6\).

    Вирішіть, які з наступних наборів є підрахунковими, а які - незліченними. (Вам не потрібно виправдовувати свої відповіді.)

    1. Замкнутий інтервал\([3,3.1]\)
    2. \(\{1,2,3, \ldots, 1000\}\)
    3. \(\mathbb{Z} \times \mathbb{Z}\)
    4. \(\mathbb{Z} \times \mathbb{Q}\)
    5. \(\mathbb{R} \times \mathbb{N}\)
    6. \(\mathbb{R} \backslash \mathbb{Q}\)
    7. \(\mathbb{Q} \backslash \mathbb{R}\)
    8. \((\mathbb{R} \backslash \mathbb{Q}) \cap(\mathbb{Q} \backslash \mathbb{R})\)
    9. \((\mathbb{R} \backslash \mathbb{Q}) \cup(\mathbb{Q} \backslash \mathbb{R})\)
    10. \((\mathbb{R} \backslash \mathbb{Q}) \times(\mathbb{Q} \backslash \mathbb{R})\)
    11. \(\{x \in \mathbb{R} \mid 2<x<3\}\)
    12. \(\left\{x \in \mathbb{R} \mid x^{2}=3\right\}\)
    13. \(\left\{x \in \mathbb{R} \mid x^{2}+12<3\right\}\)
    14. \(\left\{x \in \mathbb{R} \mid x^{2}+3<12\right\}\)
    15. \ (\ ліворуч\ {x\ in\ mathbb {Q}\ середина x^ {2} +3<12\ вправо\})
    16. \ (\ {(x, y)\ in\ mathbb {R}\ раз\ mathbb {R}\ середина x-y = 1\})
    17. \(\{(x, y) \in \mathbb{R} \times \mathbb{R} \mid x-y \in \mathbb{Z}\}\)
    18. \(\{(x, y) \in \mathbb{Z} \times \mathbb{R} \mid x-y \in \mathbb{Q}\}\)
    19. \ (\ ліворуч\ {(x, y)\ in\ mathbb {R} ^ {2}\ середина x^ {2} +y^ {2} =1\ праворуч\})
    20. \ (\ лівий\ {(x, y)\ in\ mathbb {R} ^ {2}\ середина x^ {2} +y^ {2} =-1\ вправо\})

    9.6Б. Кардинальність силових установок.

    Якщо\(A\) є скінченною множиною, то\(\mathcal{P}(A)\) множина всіх підмножин також\(A\) є скінченною. (Дійсно,\(\# \mathcal{P}(A)=2^{\# A}\).) Однак це твердження не залишається істинним, коли слово «скінченний» замінюється на «лічильний»:

    Вправа\(9.6.7\).

    Покажіть,\(\mathcal{P}\left(\mathbb{N}^{+}\right)\) що незліченно. [Підказка: Для будь-якого\(f: \mathbb{N}^{+} \rightarrow \mathcal{P}\left(\mathbb{N}^{+}\right)\) набору\(\left\{i \in \mathbb{N}^{+} \mid i \notin f(i)\right\}\) немає в образі\(f\).]

    Для кожного набору\(A\), а не лише підрахункових, той самий аргумент показує, що\(\mathcal{P}(A)\) кардинальність більше, ніж кардинальність\(A\). Таким чином, немає «найбільшого» нескінченного безлічі. Для кожного набору завжди знайдеться якийсь набір, який має набагато більшу кардинальність.

    Вправа\(9.6.8\).

    Для кожного набору\(A\) показувати не існує функції onto\(f: A \rightarrow \mathcal{P}(A)\). [Підказка: Набір\(\{a \in A \mid a \notin f(a)\}\) не вказано на зображенні\(f\).]

    Попередні вправи дуже тісно пов'язані з класичним парадоксом:

    Приклад\(9.6.9\) ("Barber Paradox").

    Припустимо, є місто з одним перукарем, і цей перукар - людина. Крім того, припустимо, що перукар голить саме тих чоловіків у місті, які не голяться. Точніше, якщо\(B\) Барбер, а\(M\) є будь-який чоловік в місті, то\[B \text { shaves } M \quad \text { iff } \quad M \text { does not shave } M\]

    Тепер ми запитуємо:\[\text { Does the barber shave himself? }\]

    Рішення

    Це питання - парадокс:

    • Якщо відповідь позитивна, то перукар голиться сам. Але перукар не голить чоловіків, які голяться самі, тому це означає, що перукар не голиться сам. Але ми вже говорили, що перукар дійсно голиться сам, так що це нісенітниця.
    • Якщо відповідь ні, то перукар не голиться сам. Але перукар дійсно голить будь-якого чоловіка, який не голиться сам, так це означає, що перукар і зовсім голиться сам. Але ми вже говорили, що перукар не голиться сам, так що це нісенітниця.

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

    Те ж міркування показує, що немає безлічі, яка б містила саме ті набори, які не містять себе. (Інакше питання «Чи містить набір сам себе?» був би парадокс. Розумієте чому?) Рішення Вправи\(9.6.7\) і\(9.6.8\) засновані на одній ідеї.

    _________________
    \(\text { * }\)\(d\) Цифри тільки 1 і 5, тому не проблема, що числа, що закінчуються 000., також можуть бути виражені у вигляді іншої десяткової коми, яка закінчується 999..