9.5: Підрахувальні набори

Для використання в доведенні теорем ідеї, що виникають при обговоренні готелю Infinity, потрібно викладати більш формально. Почнемо з визначень, які складають основу предмета.

Визначення\(9.6.1\).

Припустимо\(A\) і\(B\) є множинами.

1. \(A\)і\(B\) мають однакову кардинальність, якщо є біекція від\(A\) до\(B\).
2. \(A\)є незліченно нескінченним, якщо він має таку ж кардинальність, як\(\mathbb{N}^{+}\).
3. \(A\)підраховується, якщо або\(A\) є кінцевим, або незліченно\(A\) нескінченним.
4. \(A\)є незліченним, якщо не\(A\) підлягає зліку.

Зауваження\(9.5.2\).

1. У термінології попереднього розділу набір підраховується тоді і тільки тоді, коли всі його елементи можуть бути надані в готелі Infinity (див. Вправа\(9.5.6(3)\)).
2. Якщо вам кажуть показати, що\(A\) є незліченно нескінченним, безпосередньо з визначення, то ви повинні знайти біекцію від\(A\) до\(\mathbb{N}^{+}\). Однак, оскільки так добре відомо, що зворотна біекція є біекцією, прийнятно знайти біекцію від\(\mathbb{N}^{+}\) до\(A\), замість цього.

Зауваження\(9.5.3\).

Можна (і потрібно) думати про підрахункові множини як множини, елементи яких можуть бути перераховані в послідовності. Послідовність може мати лише скінченно багато термінів, або може тривати назавжди:

1. Безліч\(A\) є кінцевим, якщо його елементи можуть бути перераховані в послідовності\(a_{1}, a_{2}, \ldots, a_{n}), for some \(n\).
2. Якщо елементи\(A\) можуть бути перераховані в нескінченній послідовності\(a_{1}, a_{2}, a_{3}, \ldots), then we may define a bijection \(f: \mathbb{N}^{+} \rightarrow A) by \(f(i)=a_{i}\). Тому незліченно нескінченно.\(A\)
3. І навпаки, якщо\(A\) є зліченно нескінченним, то існує біекція\(f: \mathbb{N}^{+} \rightarrow A), so letting \(a_{i}=f(i)\) дає нескінченну послідовність\(a_{1}, a_{2}, a_{3}, \ldots) that lists the elements of \(A\).

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

Визначити\(\approx\) двійкове відношення для колекції всіх множин за\[A \approx B \quad \text { iff } \quad A \text { and } B \text { have the same cardinality. }\]

1. Покажіть, що\(\approx\) це відношення еквівалентності.
2. Що таке клас еквівалентності\(\mathbb{N}^{+}\)?

Наступний фундаментальний результат показує, що найменші нескінченні множини є підрахунковими:

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

1. Кожен нескінченний набір містить незліченно нескінченну підмножину.
2. Кожна підмножина обчислюваного множини є підрахунковою.

Доказ

1. З огляду на нескінченну множину\(A\), досить побудувати нескінченну\(a_{1}, a_{2}, a_{2}, \ldots\) послідовність різних елементів\(A\), бо тоді\(\left\{a_{1}, a_{2}, a_{3}, \ldots\right\}\) є незліченно нескінченною підмножиною\(A\).
   1. Оскільки\(A\) він нескінченний, він, звичайно, не порожній, тому має деякі елементи. \(a_{1}\)Дозволяти бути будь-який з цих елементів\(A\).
   2. Оскільки\(A\) нескінченно, ми знаємо, що a1 - не єдиний його елемент. \(a_{2}\)Дозволяти бути будь-який елемент,\(A\) крім\(a_{1}\). Тоді\(a_{1}\) і\(a_{2}\) є окремими елементами\(A\).
   3. Оскільки\(A\) це нескінченно, ми це знаємо\(a_{1}\) і не\(a_{2}\) є єдиними його елементами. \(a_{3}\)Дозволяти бути будь-яким елементом\(A\) крім\(a_{1}\) і\(a_{2}\). Потім\(a_{1}\)\(a_{2}\), і\(a_{3}\) є окремими елементами А
      .
      .
      .
      i. оскільки\(A\) це нескінченно, ми знаємо,\(a_{1}, a_{2}, a_{3}, \ldots, a_{i-1}\) що це не єдині його елементи. \(a_{i}\)Дозволяти бути будь-який елемент,\(A\) крім\(a_{1}, a_{2}, a_{3}, \ldots, a_{i-1}\). Тоді елементи\(a_{1}, a_{2}, a_{3}, \ldots, a_{i}\) розрізняються.
      .
      .
      .

Продовження цього індуктивного процесу дає бажану нескінченну\(a_{1}, a_{2}, a_{3}, \ldots\) послідовність різних елементів\(A\).

2. Враховуючи\(M\) підмножину обчислювальної\(A\) множини, ми хочемо показати, що\(M\) підраховується. Ми можемо припустити, що\(M\) це нескінченно, бо інакше це, очевидно, підраховується. Таким чином, ми хочемо, щоб показати є послідовність\(m_{1}, m_{2}, m_{3}, \ldots\), яка перераховує всі елементи\(M\).
   Щоб спростити позначення, давайте спочатку розглянемо випадок, де\(A=\mathbb{N}^{+}\).
   1. Випадок 1. Припустимо\(A=\mathbb{N}^{+}\). Нехай
      1. \(m_{1}\)бути найменшим елементом\(M\),
      2. \(m_{2}\)бути найменшим елементом\(M \backslash\left\{m_{1}\right\}\),
      3. \(m_{3}\)бути найменшим елементом\(M \backslash\left\{m_{1}, m_{2}\right\}\),
      4. \(m_{4}\)бути найменшим елементом\(M \backslash\left\{m_{1}, m_{2}, m_{3}\right\}\),
         .
         .
         .
         (i)\(m_{i}\) бути найменшим елементом\(M \backslash\left\{m_{1}, m_{2}, \ldots, m_{i-1}\right\}\). (Іншими словами,\(m_{i}\) це найменший елемент того\(M\), що не в\(\left\{m_{1}, m_{2}, \ldots, m_{i-1}\right\}\).)
         .
         .
         .

Для кожного\(m \in M), notice that if we let \(k\) бути кількість елементів\(M\), які менше\(m\), то\(m_{k+1}=m\). Тому кожен елемент\(m\)\(M\) з'являється в послідовності\(m_{1}, m_{2}, m_{3}, \ldots\).

2. Випадок 2. Загальний випадок. Це залишають як вправу.

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

1. Повна справа 2 у доведенні теореми\(9.5.5\). [Підказка: Якщо\(M\) нескінченно, то\(A\) має бути нескінченним (чому?). Перерахуйте елементи послідовності\(a_{1}, a_{2}, a_{3}, \ldots\) та застосуйте аргумент Case 1.]\(A\)
2. Припустимо\(f: A \rightarrow B\), що,\(f\) що один до одного, і що піддається\(B\) зліченню. Покажіть,\(A\) що підраховується.
   [Підказка: Якщо\(f\) це не на, ви хочете використовувати той факт, що кожна підмножина обчислюваного множини є підрахунковим.]
3. Показати, що\(A\) множина підлягає підрахунку, якщо існує функція один до одного\(f: A \rightarrow \mathbb{N}^{+}\).

Зауваження\(9.5.7\).

Математики вважають лічильні множини малими - хоча вони можуть бути нескінченними, вони майже як кінцеві множини. Розглянемо наступні основні властивості скінченних множин:

1. Будь-яка підмножина скінченної множини є скінченною.
2. Об'єднання двох скінченних множин є скінченним.
3. У загальному плані об'єднання скінченно багатьох скінченних множин є кінцевим.
4. Якщо у вас два кінцевих множини, то ви можете зробити з них тільки скінченно багато впорядкованих пар. (Тобто декартове добуток двох скінченних множин є скінченним.)
5. Якщо у вас є лише скінченно багато дротиків, щоб кинути, то ви можете вразити ними лише скінченно багато речей. Тобто якщо\(f: A \rightarrow B\), і\(A\) є кінцевим,\(f(A)\) то зображення кінцеве

Всі перераховані вище твердження залишаються вірними, коли слово «кінцевий» замінюється на «лічильний». Перше твердження було встановлено в Тм. \(9.5.5(2)\); інші містяться в наступній важливій теоремі:

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

1. Зліченний союз лічильних множин підлягає підрахунку.
2. Декартовий добуток двох лічильних множин підлягає підрахунку.
3. Образ обчислювальної множини підлягає підрахунку.

Зауваження\(9.5.9\).

Ось більш точні твердження тверджень теореми\(9.5.8\):

1. Якщо\(A_{1}, A_{2}, A_{3}, \ldots\) є якась послідовність лічильних множин, то союз\[\bigcup_{i=1}^{\infty} A_{i}=A_{1} \cup A_{2} \cup A_{3} \cup \cdots\]
   є підрахунковим. Крім того, якщо\(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\) є якась скінченна послідовність лічильних множин, то союз\[\bigcup_{i=1}^{n} A_{i}=A_{1} \cup A_{2} \cup A_{3} \cup \cdots \cup A_{n}\]
   є підрахунковим.
2. Якщо\(A\) і\(B\) є будь-якими підрахунковими множинами, то\(A \times B\) підраховується.
3. Якщо\(f: A \rightarrow B\), і\(A\) підраховується, то\(f(A)\) є підрахунковим.

Доказ

1. Враховуючи або нескінченну\(A_{1}, A_{2}, A_{3}, \ldots\) послідовність лічильних множин, або скінченну послідовність\(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\), A з лічильних множин, ми хочемо показати, що об'єднання множин є підрахунковим. Підмножини обчислювальної множини є підрахунковими, тому немає ніякої шкоди в тому, щоб припустити:
   • послідовність нескінченна (тому що додавання додаткових членів до послідовності зробить об'єднання більшим), і
   • кожна з множин нескінченна (тому що заміна\(A_{i}\) нескінченною надмножиною зробить об'єднання більшим).

Тепер метод нумерації напр. \(9.4.3(7)\)показує, що є функція ono\(g: \mathbb{N}^{+} \rightarrow \bigcup_{i=1}^{\infty} A_{i}\). Отже, з 3., робимо висновок, що\(\bigcup_{i=1}^{\infty} A_{i}\) є підрахунковим.

2. Враховуючи підрахункові\(A\) набори і\(B\), ми хочемо показати, що\(A \times B\) підраховується. Підмножини обчислювальної множини є підрахунковими, тому немає ніякої шкоди в тому, щоб припустити, що\(A\) і\(B\) є нескінченними (оскільки заміна A і B нескінченними надмножинами зробить декартовий добуток більшим). Нехай
   • \(a_{1}, a_{2}, a_{3}, \ldots\)бути списком елементів\(A\), і
   • \(b_{1}, b_{2}, b_{3}, \ldots\)бути списком елементів\(B\),

Далі елементи\(A \times B\) наведені в наступній таблиці (або матриці):\ [\ begin {масив} {cccccc}
\ left (a_ {1}, b_ {1}\ праворуч) &\ left (a_ {1}, b_ {1}\ right) &\ left (a_ {1}, b_ {3}\ праворуч) &\ left (a_ {1}, b_ {4}\ праворуч) &\ ліворуч (a_ {1}, b_ {5}\ праворуч) &\ cdots\
\ ліворуч (a_ {2}, b_ {1}\ праворуч) &\ ліворуч (a_ {2}, b_ {2}\ праворуч) &\ ліворуч (a_ {2}, b_ {3}\ праворуч) &\ ліворуч (a_ {2}\ праворуч) &\ cdots\\ ліворуч (a_ {3}, b_ {1}
\ праворуч) &\ ліворуч (a_ {3}, b_ {2}\ праворуч) &\ ліворуч (a_ {3}, b_ {3}\ праворуч) &\ ліворуч (a_ {3}, b_ {4}\ праворуч) & ;\ ліворуч (a_ {3}, b_ {5}\ праворуч) &\ cdots
\\ ліворуч (a_ {4}, b_ {1}\ праворуч) &\ ліворуч (a_ {4}, b_ {2}\ праворуч) &\ ліворуч (a_ {4}, b_ {4}\ праворуч) &\ ліворуч (a_ {4}) &\ ліворуч (a_ {4}, b_ {5}\ праворуч) &\ cdots\
\ ліворуч (a_ {5}, b_ {1}\ праворуч) &\ ліворуч (a_ {5}, b_ {2}\ праворуч) & ;\ лівий (a_ {5}, b_ {3}\ праворуч) &\ лівий (a_ {5}, b_ {4}\ праворуч) &\ лівий (a_ {5}, b_ {5}\ праворуч) &\ cdots\
\ vdots &\ vdots &\ vdots &\ vdots &\ ddots
\ кінець {масив}\]

Метод нумерації напр. \(9.4.3(7)\)визначає біекцію від\(A \times B \text { to } \mathbb{N}^{+}\). Так\(A \times B\) підраховується.

3. Припустимо\(f: A \rightarrow B\), і\(A\) є зліченою. \(B\)Замінивши на\(f(A)\), ми можемо припустити, що\(f\) це на; тоді ми хочемо показати, що\(B\) підраховується. За допомогою вправи\(9.5.6(2)\) досить визначити функцію один-на-один\(g: B \rightarrow A\). Функція\(f\) знаходиться на, так що, для кожного\(b \in B\), є деякі\(a \in A\), такі, що\(f(a)=b\); Таким чином, для кожного\(b \in B\), ми можемо вибрати,\(g(b)\) щоб бути елементом\(A\) такого, що\[f(g(b))=b\]
   Тоді\(g: B \rightarrow A\), і все, що залишається, це показати, що г один- до-одному. Враховуючи\(b_{1}, b_{2} \in B\), що таке\(g\left(b_{1}\right)=g\left(b_{2}\right)\), у нас\(f\left(g\left(b_{1}\right)\right)=b_{1}\) і\(f\left(g\left(b_{2}\right)\right)=b_{2}\). Тому\[b_{1}=f\left(g\left(b_{1}\right)\right)=f\left(g\left(b_{2}\right)\right)=b_{2}\]
   Так\(g\) один до одного, за бажанням.

Теореми цього розділу дозволяють легко показати, що багато множин піддаються підрахунку. Ось кілька важливих прикладів:

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

Показати, що кожен з наступних наборів є підрахунковим.

1. \(\mathbb{N}^{+}\).
2. \(\mathbb{N}\). [Підказка:\(\mathbb{N}=\mathbb{N}^{+} \cup\{0\}\).]
3. \(\mathbb{Z}\). [Підказка: Нехай\(\mathbb{Z}^{-}=\{n \in \mathbb{Z} \mid n<0\}\), так\(\mathbb{Z}=\mathbb{N} \cup \mathbb{Z}^{-}\). Набір\(\mathbb{Z}^{−}\) - це зображення\(\mathbb{N}^{+}\) під функцією.]
4. \(\mathbb{Q}\). [Підказка: Нехай\(\mathbb{Z}^{+}\) буде набір натуральних чисел,\(\mathbb{Q}\) так і зображення\(\mathbb{Z} \times \mathbb{Z}^{\times}\) під функцією\(f(a, b)=a / b\).]

Дуже важливо пам'ятати, що\(\mathbb{Q}\) є підрахунковим. Оскільки\(\mathbb{N}\) і\(\mathbb{Z}\) є підмножинами\(\mathbb{Q}\), це означає, що\(\mathbb{N}\) і також\(\mathbb{Z}\) підраховуються.

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

1. Припустимо\(A\), незліченно нескінченна, і\(b \notin A\). Покажіть, прямо з визначення, що\(A \cup\{b\}\) є незліченно нескінченним.
2. Припустимо\(A\), незліченно нескінченна, і\(a \in A\). Покажіть, прямо з визначення, що\(A \backslash\{a\}\) є незліченно нескінченним.
3. Припустимо\(B\),\(A\) і є незліченно нескінченними і неспільними. Покажіть, прямо з визначення, що\(A \cup B\) є незліченно нескінченним.
4. Припустимо,\[A_{1} \text { is disjoint from } B_{1}, \quad A_{1} \text { and } A_{2} \text { have the same cardinality, }\]
   \[A_{2} \text { is disjoint from } B_{2}, \text { and } B_{1} \text { and } B_{2} \text { have the same cardinality. }\]
   Показати, що (\(A_{1} \cup B_{1}\)) має ту саму кардинальність, що і (\(A_{2} \cup B_{2}\)).
5. Припустимо\(A\), нескінченно. Показати, що є належна\(B\) підмножина\(A\), така, яка\(B\) має таку ж кардинальність, як\(A\). [Підказка: Поєднуйте теорему\(9.5.5(1)\) з вправами (2) та (4).]

ІНША ТЕРМІНОЛОГІЯ.

Деякі математики не вважають кінцеві множини «підрахунковими», тому терміни «лічильний» і «зліченно нескінченний» є синонімами їх. Потім, набір, який є або скінченним, або незліченно нескінченним, кажуть, що «максимум підраховується». Інші математики стверджують, що незліченно нескінченний набір «перечислимо».