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

Визначення

Функція, як кажуть,$\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}$ буде або скінченним, або підрахунковим.