3.2: Злічувані та незліченні набори
- Page ID
- 62459
Функція, як кажуть,\(\varphi: A \rightarrow B\) є відповідністю один до одного, якщо\(\varphi\) є як один до одного, так і на.
Ми говоримо\(B\) множини\(A\) і мають однакову кардинальність, якщо існує відповідність один до одного\(\varphi: A \rightarrow B\).
Позначаємо факт\(A\) і\(B\) маємо таку ж кардинальність шляхом написання\(|A|=|B| .\)
Визначте відношення для множин, встановивши\(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} .\)
Якщо ми\(\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}\).
\(A\)Дозволяти множина парних цілих чисел. Покажіть, що\(|A|=\aleph_{0}\).
Перевірте кожне з наступних дій:
a Якщо\(A\) є непорожньою підмножиною,\(\mathbb{Z}^{+},\) то\(A\) є або скінченним, або підрахунковим.
b Якщо\(A\) є непорожньою підмножиною обчислювальної множини,\(B,\) то\(A\) є або скінченним, або підрахунковим.
Припустимо\(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.
Непорожній набір, який не є кінцевим, вважається нескінченним. Нескінченний набір, який не піддається підрахунку, вважається незліченним.
Припустимо\(A\), є\(B \subset A\) незліченним і піддається зліченню. Покажіть,\(A \backslash B\) що незліченно.
Припустимо\(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\) піддається підрахунку.
\(\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.
Припустимо, для кожного\(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}\) буде або скінченним, або підрахунковим.