9.3: Кардинальність Союзу

Ми знаємо, що якщо\(A\) і\(B\) є неспільними, то кардинальність\(A \cup B\) є\(\# A+\# B\). Ось формула, яка працює навіть тоді, коли множини не розмежовуються:

Пропозиція\(9.3.1\).

Для будь-яких скінченних множин\(A\) і\(B\), у нас є

\[#(A \cup B)=\# A +\# B-\#(A \cap B).\]

Доказ

З вправи\(4.5.6\), ми знаємо\(A \backslash B\), що\(B \backslash A\), і\(A \cap B\) є попарно-розрізненими, і що їх союз є\(A \cup B\), так\[\#(A \backslash B)+\#(B \backslash A)+\#(A \cap B)=\#((A \backslash B) \cup(B \backslash A) \cup(A \cap B))=\#(A \cup B) .\]

Крім того, у нас є\ [\ begin {вирівняний}
\ # A &=\ # ((A\ зворотний слеш B)\ cup (A\ cap B))\\
&=\ # (A\ backslash B) +\ # (A\ cap B)
\ end {вирівняний}\]

(Перший: Вправа\(4.5.4(2)\) друга: Вправа\(4.5.5(4)\)).

Аналогічно у нас\[\# B=\#(B \backslash A)+\#(A \cap B).\]

Тому\ [\ begin {вирівняний}
\ # A+\ # B & =(\ # (A\ зворотний слеш B) +\ # (A\ cap B)) + (\ # (B\ зворотна коса риска A) +\ # (A\ cap B)\\
=\ # (A\ backslash B) +\ # (B\ зворотна слеш A) +2\ # (A\ cap B)\\
&=\ # (А\ чашка B) +\ # (А\ ковпачок B).
\ end {вирівняний}\]

Бажаний висновок виходить шляхом віднімання\(\#(A \cap B)\) з обох сторін.

Малюнок\(9A\). Сума\(\# A+\# B\) включає в себе всі елементи\(A \cup B\), але підраховує елементи\(A \cap B\) двічі, так\(\# A+\# B=\#(A \cup B)+\#(A \cap B)\). Тому\(\#(A \cup B)=\# A+\# B-\#(A \cap B)\).

Приклад\(9.3.2\).

Нехай\(A=\{\mathrm{p}, \mathrm{r}, \mathrm{o}, \mathrm{n}, \mathrm{g}\}\) і\(B=\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\). Тоді

Рішення

\[\# A=5, \# B=5, \text { and } \#(A \cap B)=\#\{\mathrm{r}, \mathrm{o}, \mathrm{n}\}=3,\]

так Пропозиція\(9.3.1\) говорить нам, що\[\#(A \cup B)=\# A+\# B-\#(A \cap B)=5+5-3=7 .\]

Це правильно, так як # (A B) = # {p, r, o, n, g, h, s} = 7.

Приклад\(9.3.3\).

Кожен з 4000 студентів в Modern U володіє або мобільний телефон або iPod (або обидва). Опитування показують, що:

• 3500 студентів володіють мобільним телефоном, і
• 1000 студентів володіють iPod.

Скільки студентів володіють як стільниковий телефон, так і iPod?

Рішення

Нехай

• \(S\)бути набором всіх студентів в Modern U,
• \(C\)бути набір студентів, які володіють мобільним телефоном, і
• \(I\)бути набір студентів, які володіють iPod.

Тоді, за припущенням,\[\# S=4000, \quad \# C=3500, \quad \# I=1000\]

Оскільки кожен студент володіє або стільниковий телефон або iPod, у нас є\(S=C \cup I\). Тому пропозиція\(9.3.1\) говорить нам, що\[\# S=\#(C \cup I)=\# C+\# I-\#(C \cap I),\]

так\[\#(C \cap I)=\# C+\# I-\# S=3500+1000-4000=500 \text {. }\]

Отже, є рівно 500 студентів, які володіють як стільниковий телефон, так і iPod.

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

1. Припустимо\(\# U=15\)\(\# V=12\),, і\(\# (U \cap V)=4\). Знайти\(\# (U \cup V )\).
2. Припустимо\(\# R=13\)\(\# S=17\),, і\(\# (R \cup S)=25\). Знайти\(\# (R \cap S)\).
3. Припустимо\(\# J = 300\)\(\# (J \cup L) = 500\),, і\(\# (J \cap L) = 150\). Знайти\(\# L\).
4. У невеликому університеті є 90 студентів, які приймають або обчислення або лінійну алгебру (або обидва). Якщо клас обчислення має 70 учнів, а клас лінійної алгебри - 35 учнів, то скільки студентів беруть як обчислення, так і лінійну алгебру?
5. (важче) Припустимо\(A\)\(B\), і\(C\) є кінцевими множинами. Показати\ [\ begin {вирівняний}
   \ # (A\ чашка B\ чашка C) =\ # A+\ # B+\ # C\\
   -\ # (A\ cap B) -\ # (A\ cap C) -\ # (B\ cap C)\\
   &+\ # (A\ cap B\ cap C).
   \ end {aligned}\]
   [Підказка: У нас є формули для\(\#((A \cup B) \cup C)\) і\(\# (A \cup B)\). Ще одна корисна формула походить від рівності\((A \cup B) \cap C=(A \cap C) \cup(B \cap C) .]\).]

Наступні вправи - приклади іншого типу застосування формули для кардинальності союзу.

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

1. Припустимо\(B\),\(A\) і є підмножинами скінченної множини\(C\). Покажіть, що якщо\(\# A+\# B>\# C\), то\(A \cap B \neq \varnothing\). [Підказка: Використовуйте пропозицію,\(9.3.1\) щоб показати це\(\#(A \cap B) \neq 0\).]
2. Показати, що якщо\(A\) це набір не менше 600 натуральних чисел, які менше 1000, то два числа в\(A\) відрізняються рівно на 100. [Підказка: Дозвольте\(B=\{a+100 \mid a \in A\}\), і використайте попередню вправу, щоб показати це\(A \cap B \neq \varnothing\).]

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

1. Припустимо\(A_{1}, A_{2}, \ldots, A_{n}\), є кінцеві множини. Показати\[\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \leq \# A_{1}+\# A_{2}+\cdots+\# A_{n} .\]
   [Підказка: крок індукції використовує пропозицію\(9.3.1\).]
2. Доведіть принцип голубиного отвору (\(9.2.1\)).
   [Підказка: Контрапозитивний стверджує, що якщо\(\# A_{i} \leq 1\) для кожного\(i\), то\(\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \leq n\).]

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

Узагальнюючи вправу\(9.3.4(5)\), формула включення-виключення обчислює кардинальність об'єднання будь-якої кількості множин:\[\left|A_{1} \cup \cdots \cup A_{n}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1 \leq i<j \leq n}\left|A_{i} \cap A_{j}\right|+\sum_{1 \leq i<j<k \leq n}\left|A_{i} \cap A_{j} \cap A_{k}\right|-\cdots+(-1)^{n+1}\left|A_{1} \cap \cdots \cap A_{n}\right|.\]

(Знак +/− залежить від кількості множин, що перетинаються: додаються непарні перетину, а парні перетину віднімаються, що узгоджується як з Пропозицією, так\(9.3.1\) і з Вправою\(9.3.4(5)\).) Ця формула нам не потрібна, але ви можете прочитати про неї в підручнику з комбінаторики (або у Вікіпедії).