13.2: Властивості

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

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

1. Кожна\(\mathbb{N}\) підмножина підрахунку.
2. Якщо є ін'єкція,\(A \hookrightarrow \mathbb{N}\text{,}\) то набір\(A\) підраховується.
3. Припустимо\(B\),\(A \subseteq B\text{.}\) якщо підраховується, то так\(A\text{.}\)
4. Припустимо\(A\),\(A \subseteq B\text{.}\) якщо не підраховується, то так\(B\text{.}\)
5. Якщо\(A\) і\(B\) підраховуються, то\(A\cup B\) і обидва\(A\cap B\) піддаються зліченню.

Контур доказу.

1. Припустімо,\(A \subseteq \mathbb{N}\text{.}\) якщо\(A\) кінцевий, то він підраховується за визначенням. Так\(\vert A \vert = \infty\text{.}\) припустимо, що Ми можемо побудувати послідовність\(\{a_k\}\), яка містить кожен елемент\(A\) точно один раз наступним чином.

\ begin {align*} a_0 & =\ text {найменше число в} A,\\ a_1 & =\ text {наступне найменше число в} A,\\ a_2 & =\ text {наступне найменше число в} A,\\ &\;\ vdots\ end {align*}
Отже,\(A\) є підрахунковим.

2. Якщо\(f: A \hookrightarrow \mathbb{N}\) ін'єкційний, то\(f: A \rightarrow f(A)\) це біекція, так що\(A\) і його зображення\(f(A)\) мають однаковий розмір. Але\(f(A)\) підраховується Заявою 1, тому, використовуючи визначення підрахунку разом з Фактом 12.3.2, зробіть висновок, що\(A\) підраховується.
3. Якщо\(B\) підраховується, то за визначенням існує\(f\vert _A: A \rightarrow \mathbb{N}\) біекція\(f: B \rightarrow \mathbb{N}\text{.}\) Потім - ін'єкція. Застосувати заяву 2.
4. Це контрапозитив заяви 3, за загальним припущенням\(A \subseteq B\text{.}\)
5. Для\(A \cap B\text{,}\) розгляду\(A \cap B \subseteq A\) та застосування Заява 3.

Тепер розглянемо\(A \cup B\text{.}\) Для простоти ми будемо вважати\(A \cap B = \emptyset\text{,}\) так, що\(A \cup B = A \sqcup B\text{.}\) Оскільки\(A\) і\(B\) є підрахунковими, ми можемо записати їх елементи як послідовності:

\ begin {align*} A & =\ {\, a_0,\, a_1,\, a_2,\,\ ldots\,\,\ ldots\,\}, & B & =\ {\, b_0,\, b_1,\, b_2,\ ldots\,\,\ ldots\,\}\ текст {.} \ end {align*} Потім
ми можемо записати елементи\(A \sqcup B\) в послідовності, перемежовуючи ці дві послідовності:

\ begin {рівняння*} A\ sqcup B =\ {\, a_0,\, b_0,\, a_1,\, b_1,\, a_2,\, b_2,\,\ ldots\,\ ldots\,\}\ текст {.} \ end {рівняння*}

Чекпойнт\(\PageIndex{1}\)

Довести\(A \cup B\) є підрахунковим навіть у випадку\(A \cap B \ne \emptyset\text{.}\)

Підказка.

Розглянемо набори

\ begin {align*} A '& = A\ маленький набір мінус (A\ cap B), & B' & = B\ маленький setмінус (A\ cap B), & C & = A '\ sqcup B'. \ end {align*}
Тоді\(A\cup B\) є нероз'єднаним об'єднанням\(C\) і\(A\cap B\text{.}\)

Приклад\(\PageIndex{1}\): Primes are countable.

Набір простих чисел є підрахунковим, оскільки він є підмножиною\(\mathbb{N}\text{.}\)

Приклад\(\PageIndex{2}\): Unit interval is uncountable.

Одиничний\((0,1)\) інтервал у рядку дійсного числа є незліченним, оскільки він містить незліченну\(\scr{C}\) підмножину з Lemma 13.1.1.

Теорема\(\PageIndex{1}\)

Набір\(\mathbb{R}\) незліченний.

Доказ

Це випливає з Лемми 13.1.1 та Заява 4 Пропозиції\(\PageIndex{1}\).

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

Набір декартових добуток\(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\) є незліченним, оскільки він має незліченну підмножину:\(x\) -вісь має той самий розмір, що і\(\mathbb{R}\text{.}\)