Skip to main content
LibreTexts - Ukrayinska

3.2: Злічувані та незліченні набори

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

    Визначення

    Функція, як кажуть,\(\varphi: A \rightarrow B\) є відповідністю один до одного, якщо\(\varphi\) є як один до одного, так і на.

    Визначення

    Ми говоримо\(B\) множини\(A\) і мають однакову кардинальність, якщо існує відповідність один до одного\(\varphi: A \rightarrow B\).

    Позначаємо факт\(A\) і\(B\) маємо таку ж кардинальність шляхом написання\(|A|=|B| .\)

    Вправа\(\PageIndex{1}\)

    Визначте відношення для множин, встановивши\(A \sim B\) якщо і тільки якщо\(|A|=|B| .\) Показати, що це відношення є співвідношенням еквівалентності.

    Визначення

    Нехай\(A\) буде набір. Якщо, бо\(n \in \mathbb{Z}^{+}, A\) має кардинальність множини,\(\{1,2,3, \ldots, n\},\) ми говоримо,\(A\) є кінцевим і пишемо\(|A|=n .\) Якщо\(A\) має кардинальність\(\mathbb{Z}^{+},\) ми говоримо,\(A\) підраховується і писати\(|A|=\aleph_{0} .\)

    Приклад\(\PageIndex{1}\)

    Якщо ми\(\varphi: \mathbb{Z}^{+} \rightarrow \mathbb{Z}\) визначимо

    \[\varphi(n)=\left\{\begin{array}{ll}{\frac{n-1}{2},} & {\text { if } n \text { is odd, }} \\ {-\frac{n}{2},} & {\text { if } n \text { is even, }}\end{array}\right.\]

    то\(\varphi\) це листування один на один. Таким чином\(|\mathbb{Z}|=\aleph_{0}\).

    Вправа\(\PageIndex{2}\)

    \(A\)Дозволяти множина парних цілих чисел. Покажіть, що\(|A|=\aleph_{0}\).

    Вправа\(\PageIndex{3}\)

    Перевірте кожне з наступних дій:

    a Якщо\(A\) є непорожньою підмножиною,\(\mathbb{Z}^{+},\) то\(A\) є або скінченним, або підрахунковим.

    b Якщо\(A\) є непорожньою підмножиною обчислювальної множини,\(B,\) то\(A\) є або скінченним, або підрахунковим.

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

    Припустимо\(B\),\(A\) і є лічильними множинами. Тоді набір\(C=\)\(A \cup B\) підраховується.

    Доказ

    Припустимо\(A\) і\(B\) є неспільними, тобто\(A \cap B=\emptyset .\)\(\varphi: \mathbb{Z}^{+} \rightarrow A\)\(\psi: \mathbb{Z}^{+} \rightarrow B\) Дозволяти і бути один до одного відповідності. Визначте\(\tau: \mathbb{Z}^{+} \rightarrow C\) по

    \[\tau(n)=\left\{\begin{array}{ll}{\varphi\left(\frac{n+1}{2}\right),} & {\text { if } n \text { is odd, }} \\ {\psi\left(\frac{n}{2}\right),} & {\text { if } n \text { is even. }}\end{array}\right.\]

    Тоді\(\tau\) це листування один до одного, показуючи, що\(C\) підраховується.

    Якщо\(A\) і\(B\) не роз'єднані,\(\tau\) то на, але не один до одного. Однак у цьому випадку\(C\) має кардинальність нескінченної підмножини\(\mathbb{Z}^{+},\) і так підраховується. \(\quad\)Q.E.D.

    Визначення

    Непорожній набір, який не є кінцевим, вважається нескінченним. Нескінченний набір, який не піддається підрахунку, вважається незліченним.

    Вправа\(\PageIndex{4}\)

    Припустимо\(A\), є\(B \subset A\) незліченним і піддається зліченню. Покажіть,\(A \backslash B\) що незліченно.

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

    Припустимо\(B\),\(A\) і є підрахункові. Тоді\(C=A \times B\) підраховується.

    Доказ

    \(\varphi: \mathbb{Z}^{+} \rightarrow A\)\(\psi: \mathbb{Z}^{+} \rightarrow B\)Дозволяти і бути один на один відповідності. Дозвольте\(a_{i}=\varphi(i)\) і\(b_{i}=\psi(i) .\) визначте\(\tau: \mathbb{Z}^{+} \rightarrow C\), дозволяючи

    \[\tau(1)=\left(a_{1}, b_{1}\right),\]

    \[\tau(2)=\left(a_{1}, b_{2}\right),\]

    \[\tau(3)=\left(a_{2}, b_{1}\right),\]

    \[\tau(4)=\left(a_{1}, b_{3}\right),\]

    \[\tau(5)=\left(a_{2}, b_{2}\right),\]

    \[\tau(6)=\left(a_{3}, b_{1}\right),\]

    \[\tau(7)=\left(a_{1}, b_{4}\right),\]

    \[\vdots = \vdots\]

    Тобто сформувати нескінченну матрицю з\(\left(a_{i}, b_{j}\right)\) в\(i\) -му рядку і\(j\) й стовпці, а потім порахувати записи, зчитуючи вниз діагоналі справа наліво. Тоді\(\tau\) це листування один до одного і\(C\) піддається підрахунку.

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

    \(\mathbb{Q}\)піддається зліченню.

    Доказ

    За попередньою пропозицією,\(\mathbb{Z} \times \mathbb{Z}\) є зліченою. Нехай

    \[A=\{(p, q): p, q \in \mathbb{Z}, q>0, p \text { and } q \text { relatively prime }.\}\]

    Тоді\(A\) нескінченно і\(A \subset \mathbb{Z} \times \mathbb{Z},\) так\(A\) підраховується. Але очевидно\(|\mathbb{Q}|=|A|,\), що так\(\mathbb{Q}\) підраховується. \(\quad\)Q.E.D.

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

    Припустимо, для кожного\(i \in \mathbb{Z}^{+}, A_{i}\) є зліченою. Тоді

    \[B=\bigcup_{i=1}^{\infty} A_{i}\]

    піддається зліченню.

    Доказ

    Припустимо,\(A_{i}, i \in \mathbb{Z}^{+},\) множини попарно розмежовуються, тобто\(A_{i} \cap A_{j}=\emptyset\)\(i, j \in \mathbb{Z}^{+} .\) для всіх Для кожного\(i \in \mathbb{Z}^{+},\) нехай\(\varphi_{i}: \mathbb{Z}^{+} \rightarrow A_{i}\) буде відповідність один до одного. Потім\(\psi: \mathbb{Z}^{+} \times \mathbb{Z}^{+} \rightarrow B\) визначаються

    \[\psi(i, j)=\varphi_{i}(j)\]

    це листування один на один, і так\(|B|=\left|\mathbb{Z}^{+} \times \mathbb{Z}^{+}\right|=\aleph_{0}\).

    Якщо набори\(A_{i}, i \in \mathbb{Z}^{+},\) не роз'єднані, то\(\psi\) є на, але не один до одного. Але тоді існує підмножина\(P\)\(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) таких, що\(\psi: P \rightarrow B\) є відповідність один до одного. Оскільки\(P\) є нескінченною підмножиною обчислювальної множини,\(P\) підраховується і так\(|B|=\aleph_{0} .\)\(\quad\) Q.E.D.

    Якщо в попередній пропозиції ми дозволяємо, що для кожного\(i \in \mathbb{Z}^{+}, A_{i}\) є або скінченним, або підрахунковим, то\(B=\bigcup_{i=1}^{\infty} A_{i}\) буде або скінченним, або підрахунковим.