Мощностью конечного множества A={a1,a2,...,an,...}, называется число его элементов n (обозначение: |A|=n). Очевидно, что если А=В, то |A|=|B|. Кроме того, |Æ| = 0.
Примеры.
1. A ={-2,-1,0,1,2}, |A| = 5;
2. B ={b / b делится на 3 без остатка и b £ 21, bÎN}, |B| = 7.
Теорема 1.1 (о мощности разности). Пусть А и В - конечные множества и, кроме того, В Í А. Тогда |A\B| = |A| - |B|.
Теорема 1.2 (о мощности объединения непересекающихся множеств). Пусть А и В - конечные множества и, кроме того, АÇВ=Æ. Тогда |AÈB| = |A|+| В|.
Теорема 1.3 (о мощности объединения пересекающихся множеств). Пусть А и В - конечные множества. Тогда
|AÈB| = |A|+|B| - |АÇВ|. (1.1)
ÿ Представим объединение двух, в общем случае пересекающихся, множеств А и В в виде объединения непересекающихся множеств А и B\(АÇВ): AÈB = (A)È (B\(АÇВ)).
Тогда по теореме 1.2 |AÈB| = |(A)È(B\(АÇВ))| = |A| +|B\(АÇВ)|.
Так как (АÇВ)ÍВ, то по теореме 2.1 |B\(АÇВ)| = |B|-|АÇВ|.
Окончательно имеем |AÈB| = |A| +|B\(АÇВ)| = |A|+|B|-| АÇВ|. ÿ
Пример. В игральной колоде 36 карт. Сколькими способами можно извлечь из колоды туза или карту бубновой масти?
Решение. Пусть А - множество тузов в колоде, а В - множество карт бубновой масти. Очевидно, что
Обобщим теорему 1.3 на случай n множеств. Предположим, что даны подмножества A1,A2,...,An (необязательно различные) некоторого конечного множества X. Тогда имеет место следующая теорема.
Теорема 1.4 (принцип включения и исключения).
| AiÇ Aj | + | AiÇ AjÇ Ak |-...+(-1)n-1 |A1Ç A2Ç...Ç An |.
ÿ Применим индукцию по n. Для n=2 теорема справедлива (см. ф-лу 1.1). Предположим, что для произвольных подмножеств A1,A2,...,An-1 выполняется равенство
| AiÇ Aj |+| AiÇ AjÇ Ak |-...+(-1)n-2 |A1Ç A2Ç...Ç An |.
Применяя эту формулу к сумме
(A1È A2È...È An-1) Ç An = ,
получаем
| AiÇ AjÇ An |+...+(-1)n-2 |A1Ç A2Ç...Ç An |,
отсюда мощность объединения n подмножеств A1,A2,...,An множества Х будет равна:
| AiÇ Aj| +
+| AiÇ AjÇ Ak|-...+(-1)n-1 |A1Ç A2Ç...Ç An|.ÿ
Пример. В ящике хранятся разноцветные мячи. Известно, что в раскраске 14 мячей присутствует красный, 15 мячей - зелёный, 10 мячей - синий цвет; у 9 мячей - как красный, так и синий, 11 мячей - как красный, так и зелёный, 7 мячей - как синий, так и зелёный цвет; в раскраске 5 мячей присутствуют все три цвета. Сколько мячей в ящике?
Решение. Пусть А, В, С - множества мячей, в раскраске которых присутствует соответственно красный, зелёный и синий цвет. Тогда общее количество мячей составит:
В ожесточённом бою 70 из 100 пиратов потеряли один глаз, 75 - одно ухо, 80 - одну руку и 85 - одну ногу. Каково минимальное число потерявших одновременно глаз, ухо, руку и ногу?
Решение. Пусть A1, A2, A3, A4- множества пиратов, потерявших соответственно глаз, ухо, руку, ногу. Тогда В = (A1ÇA2ÇA3Ç A4) - это множество пиратов, потерявших одновременно глаз, ухо, руку и ногу.
Множество всех пиратов U можно представить в виде покрытия
Теорема 1.6. Для разбиения конечного множества A=A1È A2È...È Am, Ai ¹Æ, AiÇAj=Æ, i¹j, 1£ i, j £m справедливо равенство|A| = |A1|+|A2|+...+ |Am|. (правило суммы), которое доказывается аналогично формуле (1.2).
Теорема 1.7. (о мощности прямого произведения).
Пусть A1,A2,...,An- конечные множества и |A1|=m1, |A2|=m2,..., |An|=mn. Тогда мощность множества A1´A2´...´Anравна произведению мощностей A1,A2,...,An:
|A1´A2´...´An| = m1 m2 ... mn.
ÿ Применим индукцию по n.
1. n=2. Пронумеруем элементы множеств B=A1и C=A2 и составим декартово произведение B´C: B={b1,b2,...,bm1}, C={c1,c2,...,cm2},
Следствие. Пусть А - конечное множество и |A| = m. Тогда |An| = mn .
Пример.Сколько векторов длиной 3 со значениями компонент 0 или 1 можно составить?
Решение. Эти вектора представляют собой элементы множества B3, где B={0,1}. Общее число векторов с заданными свойствами равно мощности множества B3. Так как |B|=2, то |B3|=23=8.
| AiÇ Aj | + 
| AiÇ AjÇ Ak |-...+(-1)n-1 |A1Ç A2Ç...Ç An |.
| AiÇ Aj |+
| AiÇ AjÇ Ak |-...+(-1)n-2 |A1Ç A2Ç...Ç An |.
,
| AiÇ AjÇ An |+...+(-1)n-2 |A1Ç A2Ç...Ç An |,
| AiÇ Aj | +
|A1È A2È...È Ak| + |Ak+1| -
|A1|+|A2|+...+ |Ak|+ |Ak+1|.
,
,
m2 
(m1