9.1: Визначення та основні властивості
- Page ID
- 65156
Неофіційно кардинальність множини - це кількість елементів, які він містить. (Про це йшлося в\(3.2.14\) позначеннях.)
Яка кардинальність кожного з цих наборів? (Вам не потрібно показувати свою роботу або виправдовувати свої відповіді.)
- \(\#\{1,2,3,4\}=\)
- \(\#\{\mathrm{a}, \mathrm{e}, \mathrm{i}, \mathrm{o}, \mathrm{u}\}=\)
- \(\#\{\mathrm{a}, \mathrm{l}, \mathrm{b}, \mathrm{e}, \mathrm{r}, \mathrm{t}, \mathrm{a}\}=\)
- \(\text { 4) } \# \varnothing=\)
- \(\#\{\varnothing\}=\)
- \(\#\{k \in\{1,2, \ldots, 10\} \mid k \neq 7\}=\)
Неформального розуміння кардинальності недостатньо на курсах вищої математики, тому нам потрібно вивчити цю ідею більш ретельно.
Кардинальність\(\{a, b, c\}\) дорівнює 3. Діти вчаться перевіряти це, підраховуючи:\[1(\text { for } \mathrm{a}), \quad 2(\text { for } \mathrm{b}), \quad 3(\text { for } \mathrm{c}) .\]
Їх вчать привласнювати рівно одне число кожному елементу набору (і не пропускати жодних чисел у міру їх підрахунку). Математики висловлюють цю ідею більш витонченим способом: якщо ми визначимо функцію\(f:\{\mathrm{a}, \mathrm{b}, \mathrm{c}\} \rightarrow\{1,2,3\}\) за\[f(\mathrm{a})=1, f(\mathrm{~b})=2, f(\mathrm{c})=3,\]
потім\(f\) - біекція.
Загалом, якщо множина\(A\) має\(n\) елементи, то підрахунок елементів один за іншим визначає біекцію від\(A\) до\(\{1,2,3, \ldots, n\}\). Це спостереження призводить до наступного офіційного визначення.
- \(A\)Дозволяти бути множиною і\(n\) бути натуральним числом. Ми говоримо, що кардинальність\(A\) є\(n\) (і пишемо\(\# A = n\)), якщо є біекція від\(A\) до\(\{1,2,3, \ldots, n\}\).
- Набір\(A\) є кінцевим, якщо є деякі\(n \in \mathbb{N}\), такі, що\(\# A = n\).
- Безліч\(A\) нескінченний, якщо він не кінцевий.
- Не всі набори є кінцевими. Наприклад,\(\mathbb{N}\) є нескінченним (див. Вправа\(9.2.8(5)\)).
- Ми побачимо в теоремі\(9.1.20\), що кожна підмножина скінченної множини є кінцевим.
Оскільки визначення\(\# A\) ґрунтується на двосторонніх, кожне доказ про кардинальність покладатиметься на факти про бі'єкції.
Показати\(\#\{1,2,3, \ldots, n\}=n\), для кожного\(n \in \mathbb{N}\).
Подряпини. Визначення кардинальності говорить нам, що якщо\(A\) є якийсь набір, і нам потрібно показати\(\# A = n\), то нам потрібно знайти біекцію від\(A\) до\(\{1,2,3, \ldots, n\}\). У цій проблемі ми маємо\(A=\{1,2,3, \ldots, n\}\). Тому нам потрібно знайти біекцію від\(\{1,2,3, \ldots, n\}\) до\(\{1,2,3, \ldots, n\}\). Таким чином, нам потрібно знайти біекцію від набору до себе. Вправа\(6.6.9\) говорить нам, що карта ідентичності є такою функцією.
Рішення
ДОКАЗ.
З вправи ми знаємо\(6.6.9\), що карта ідентичності\(I_{\{1,2, \ldots, n\}}\) - це біекція від\(\{1,2, \ldots, n\}\) до\(\{1,2, \ldots, n\}\), так\(\#\{1,2, \ldots, n\}=n\).
АЛЬТЕРНАТИВНЕ ДОКАЗ.
Визначте\(f:\{1,2,3, \ldots, n\} \rightarrow\{1,2,3, \ldots, n\}\) по\(f(k) = k\).
Ми стверджуємо, що\(f\) це біекція. Іншими словами, ми стверджуємо, що\(f\) це один до одного і на.
(один-на-один) З огляду\(i_{1}, i_{2} \in\{1,2,3, \ldots, n\}\), такий, що\(f(i_{1}) = f(i_{2})\), у нас є\(i_{1} = i_{2}\). Так\(f\) само один до одного.
(на) Дано\(j \in\{1,2,3, \ldots, n\}\), нехай\(i = j\). Потім\(f(i) = i = j\). Так\(f\) і на.
Оскільки\(f\) це як один до одного, так і на, це біекція. На цьому доказ претензії завершено.
Тому виникає біекція (а саме\(f\)) від\(\{1,2,3, \ldots, n\}\) до\(\{1,2,3, \ldots, n\}\). Отже,\(\#\{1,2,3, \ldots, n\}=n\).
Оскільки порожній набір не має елементів, його кардинальність повинна дорівнювати 0. Хоча це може бути неочевидним, визначення\(9.1.3\) погоджується з цим спостереженням. Щоб переконатися в цьому, важливо усвідомити, що для будь-якого\(n \in \mathbb{N}\) позначення\(\{1,2, \ldots, n\}\) - це просто інша назва множини\(\{i \in \mathbb{N} \mid 1 \leq i \leq n\}\). Зокрема, якщо\(n = 0\), то\[\{1,2, \ldots, n\}=\{i \in \mathbb{N} \mid 1 \leq i \leq n\}=\{i \in \mathbb{N} \mid 1 \leq i \leq 0\}=\varnothing .\]
Тому, ввівши\(n = 0\) приклад,\(9.1.5\) говорить нам про це\(\# \varnothing=0\), як і очікувалося.
Визначення\(\# A\) вказує, що існує біекція від\(A\) до\(\{1,2,3, \ldots, n\}\). Наступна вправа показує, що немає ніякої шкоди, якщо ви вирішите, щоб ін'єкція пішла іншим шляхом.
Нехай\(A\) буде набір. Бо\(n \in \mathbb{N}\), покажіть\(\# A = n\), чи є біекція від\(\{1,2,3, \ldots, n\}\) до\(A\). [Підказка: Використовуйте вправу\(6.7.13(1)\).]
Bijections можна використовувати, щоб показати, що два набори мають однакову кардинальність, не знаючи, скільки елементів вони мають.
У суспільстві Married\(6.6.2\) of Example (де кожен чоловік одружений на жінці, і навпаки), зрозуміло, що чоловіків і жінок повинно бути рівно однакова кількість. (Якби жінок було більше, ніж чоловіків, то або якась жінка була б незаміжньою, або більше однієї жінки довелося б одружитися з одним і тим же чоловіком. Точно так само, якщо чоловіків було більше, ніж жінок.) Це правда, хоча ми не маємо уявлення про те, скільки жінок чи чоловіків є в суспільстві. Все, що ми знаємо, це те, що проте багато жінок є точно так само, як і кількість чоловіків.
Це спостереження формалізовано в наступній пропозиції.
Припустимо\(A\) і\(B\) є кінцевими множинами. Тоді\(\# A = \# B\) якщо і тільки в тому випадку, якщо є біекція від\(A\) до\(B\).
- Доказ
-
\((\Rightarrow)\)Нехай\(n\) буде кардинальність\(A\). За визначенням це означає\[\text { there is a bijection } f: A \rightarrow\{1,2, \ldots, n\} \text {. }\]
За припущенням,\(n\) це також кардинальність\(B\), так\[\text { there is also a bijection } g: B \rightarrow\{1,2, \ldots, n\} \text {. }\]
Зворотна біекція - це біекція (див. Вправа\(6.7.13(1)\)), а склад біекцій - це біекція (див. Вправа\(6.8.12(1)\)), так\(g^{-1} \circ f\) це біекція від\(A\) до\(B\).
\((\Leftarrow)\)Ми залишаємо це як вправу.
Доведіть пропозицію\(9.1.9(\Leftarrow)\). [Підказка: Використовуйте вправу\(6.8.12(1)\).]
- Покажіть, що якщо\(\# A_{1} = \# A_{2}\), то\(\# (A_{1} \times B) = \# (A_{2} \times B)\). [Підказка: Якщо\(f : A_{1} \rightarrow A_{2}\) це біекція, визначте\(g : A_{1} \times B \rightarrow A_{2} \times B\) за\(g\left(a_{1}, b\right)=\left(f\left(a_{1}\right), b\right)\).]
- Показати, що якщо\(\{a_{0}\}\) є будь-який набір тільки з одним елементом, то\(\#\left(\left\{a_{0}\right\} \times B\right)=\# B\). [Підказка: Визначити\(f: B \rightarrow\left\{a_{0}\right\} \times B\) по\(f(b)=\left(a_{0}, b\right)\).]
- Припустимо,\(f : A \rightarrow B\) це один-на-один, і\(X \subset A\). Показати\(\# f(X) = \# X\).
У початковій школі ми дізнаємося, що якщо у Аліси є\(m\) яблука, а у Боба\(m+n\) є\(n\) яблука, то сума - загальна кількість яблук, яке є у двох з них. Однак цей простий приклад передбачає, що Аліса і Боб не поділяють жодного з яблук; набір яблук Аліси повинен бути відрізаний від набору яблук Боба.
Наступний результат узагальнює цей приклад.
Якщо\(A\) і\(B\) є нез'єднаними скінченними множинами, то\ [\ # (A\ cup B) =\ # A +\ # B.
- Доказ
-
Нехай\(m = \# A\) і\(n = \# B\). Тоді існують упередження.\[f:\{1,2, \ldots, m\} \rightarrow A \quad \text { and } \quad g:\{1,2, \ldots, n\} \rightarrow B .\]
Визначити функцію\ (h:\ {1,2,\ ldots, m+n\}\ rightarrow (A\ cup B)) за допомогою\ [h (k) =\ left\ {\ begin {масив} {cl}
f (k) &\ text {якщо} k\ leq m\
g (k-m) &\ text {if} k>m
\ end {масив}\ праворуч.(Зверніть увагу\(k \in\{1,2, \ldots, m+n\}\), що якщо\(k > m\), і\(m + 1 \leq k \leq m + n\), то, так\(1 \leq k − m \leq n\); отже,\(k − m\) знаходиться в області\(g\), тому вираз має\(g(k − m)\) сенс.)
Щоб завершити доказ, достатньо показати, що\(h\) це біекція; таким чином, нам потрібно лише показати, що\(h\) є один до одного і на.
(на) Враховуючи\(y \in A \cup B\), у нас є або\(y \in A \text { or } y \in B\), і ми розглядаємо ці дві можливості як окремі випадки.
- Припустимо\(y \in A\). Так\(f\) як на, є деякі\(k \in\{1,2, \ldots, m\}\) з\(f(k) = y\). Тоді, тому що\(k \leq m\), ми маємо\[h(k)=f(k)=y .\]
- Припустимо\(y \in B\). Так\(g\) як на, є деякі\(k \in\{1,2, \ldots, n\}\) з\(g(k) = y\). Потім\(k+m \in\{1,2, \ldots, m+n\}\) і\(k + m > m\), так\[h(k+m)=g((k+m)-m)=\eta(k)=y .\]
Оскільки\(y\) є довільним елементом\(A \cup B\), ми робимо висновок, що\(h\) є на.
(один-на-один) Ми залишаємо це як вправу.
Показати, що функція,\(h\) визначена в доказ Пропозиції\(9.1.13\), є один до одного.
Припустимо,\(B\) це скінченна множина.
- Для всіх\(b \in B\), покажіть це\(\#(B \backslash\{b\})=\# B-1\).
- Покажіть, що якщо\(A \subset B\), то\(\# A \leq \# B. [Hint: \(\# B=\# A+\#(B \backslash A) \geq \# A\).]
- Показати, що якщо\(A_{1}\) і\(A_{2}\) є нез'єднаними\(B\) підмножинами, то\(\# A_{1}+\# A_{2} \leq \# B\).
- (Складніше) Припустимо\(B \neq \varnothing\). Показати, що якщо\(S \subset \mathcal{P}(B)\), і немає двох елементів не\(S\) з'єднані, то\(\# S \leq \frac{1}{2} \# \mathcal{P}(B)\).
[Підказка: Ви можете припустити (без доказів), що\(\mathcal{P}(B)\) є кінцевим. Якщо\(X \in S\), то\(\bar{X} \notin S\).] - Показувати,\(\# B = 0\) якщо і тільки якщо\(B=\varnothing\).
Наступне узагальнення Пропозиції\(9.1.13\) стосується об'єднання будь-якої кількості множин, а не лише двох.
Якщо\(A_{1}, A_{2}, \ldots, A_{n}\) є попарно-незв'язними скінченними множинами, то\[\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right)=\# A_{1}+\# A_{2}+\cdots+\# A_{n} .\]
[Підказка: Індукт на\(n\), використовуючи пропозицію\(9.1.13\) та вправу\(4.5.7\).]
У зауваження було зазначено\(6.1.7\), що якщо\(A\) і\(B\) є кінцевими множинами, то\(\#(A \times B)=\# A \cdot \# B\). Тепер ми можемо довести це, після використання вправи\(9.1.16\) для вирішення наступної вправи:
Припустимо\(A_{1}, A_{2}, \ldots, A_{m}\), є попарно-незв'язні скінченні множини. Покажіть, що якщо\(A=A_{1} \cup \cdots \cup A_{m}\), то\[\#(A \times B)=\#\left(A_{1} \times B\right)+\#\left(A_{2} \times B\right)+\cdots+\#\left(A_{m} \times B\right) .\]
[Підказка:\(A_{i} \times B\) набори попарно розмежовуються, і їх об'єднання є\(A \times B\).]
Для будь-яких скінченних множин\(A\) і\(B\), у нас є\[\#(A \times B)=\# A \cdot \# B.\]
- Доказ
-
Нехай\(m = \# A\). Тоді немає ніякої шкоди в припущенні\(A=\{1,2, \ldots, m\}\) (див. Вправа\(9.1.11(1)\)). Тому\[A=\{1\} \cup\{2\} \cup \cdots \cup\{m\},\]
і множини попарно\(\{1\},\{2\}, \cdots,\{m\}\) розмежовуються, тому\ [\ begin {вирівняний}
\ # (\ Лямбда\ раз B) &=\ # (\ {1\}\ times B)\ text { }\ # (\ {2\}\ раз B) +\ cdots\ текст {. }\ # (\ {m\}\ раз B)\\
&=\ # B+\ # B+\ cdots+\ # B\ quad (м\ текст {додані})\\
&= m\ cdot\ # B\\
&=\ # A\ cdot\ # B.
\ end {вирівняний}\](Перша лінія: Вправа\(9.1.17\) друга лінія: Вправа\(9.1.11(2)\))
Припустимо\(A\) і\(B\) є кінцевими множинами, і\(m, n \in \mathbb{N}\). Доведіть:
- Якщо\(m \leq n\), то існує функція один до одного\(f:\{1,2, \ldots, m\} \rightarrow\{1,2, \ldots, n\}\).
- Якщо\(\# A \leq \# B\), то існує функція один до одного\(f: A \rightarrow B\). [Підказка: Використовуйте попередню вправу.]
- Якщо\(m \geq n > 0\), то існує функція ono\(f:\{1,2, \ldots, m\} \rightarrow\{1,2, \ldots, n\}\).
- Якщо\(A\) і\(B\) є непорожніми\(\# A \geq \# B\), а, то існує функція onto\(f : A \rightarrow B\). [Підказка: Використовуйте попередню вправу.]
Розмови вправ в\((9.1.19)\) вірні, і важливі. Вони будуть розглянуті в розділі\(9.2\).
Ми закінчуємо розділ основним фактом, який може здатися очевидним (і було згадано в Зауваження\(9.1.4(2)\)), але це було б важко або неможливо довести без використання індукції.
Кожна підмножина будь-якого скінченного множини є кінцевим.
- Доказ
-
\(P(n)\)Визначте, щоб бути твердженням\[\text { If } A \text { is any set with } \# A=n \text {, then every subset of } A \text { is finite. }\]
- Базовий кейс. Припустимо\(n = 0\), і нехай\(B\) буде будь-який підмножина\(A\). Тепер\(\# A = n = 0\) так\(A=\varnothing\). Оскільки єдиним підмножиною порожнього набору є порожній набір, ми маємо\(B = \varnothing\). Отже\(\# B = 0\), так\(B\) і скінченно.
- Індукційний крок. Припустимо\(n \geq 1\), і\(P(n − 1)\) це правда, і нехай\(B\) бути будь-який підмножина\(A\). Ми можемо припустити\(B\), що це належна підмножина\(A\). (В іншому випадку ми маємо\(B = A\), так\(\# B = \# A = n\), що означає, що\(B\) є кінцевим.) Таким чином, існує\(a \in A\), таке що\(a \notin B\). Нехай\(A^{\prime}=A \backslash\{a\}\). Потім\(\# A^{\prime} = n − 1\), таким чином, індукційна гіпотеза говорить нам, що кожна\(A^{\prime}\) підмножина є кінцевим. Оскільки\(B \subset A^{\prime}\), робимо висновок, що\(B\) є кінцевим.