4.1. Мощность множества. Правила суммы, произведения, степени

Понятие мощности множества возникает при сравнении множеств по числу элементов.

Определение. Множества А и В называются эквивалентными (обознача-ется А ~ В), если существует биективное отображение f: А ↔ В.

Для любых множеств А, В, С выполняются следующие свойства:

1. А ~ А;

2. если А ~ В, то В ~ А;

3. если А ~ В и В ~ С, то А ~ С.

Определение. Мощностью множества А называется класс всех множеств, эквивалентных множеству А ( обозначается | А | ).

Эквивалентные множества А и В называются равномощными, т.к. | А | ‌= | В |.

Если множество А имеет ровно n элементов, то его называют конечным множеством, и пишут | А | = n. Таким образом, мощностью конечного множества является число его элементов. Множество не являющееся конечным, называется бесконечным.

Если А ~ N , где N = { 0, 1, 2, … } – множество натуральных чисел , то мно-жество А называется счетным: ‌‌ ‌‌| А | = N.

Если А ~ 2 , то множество А называется континуальным или континуумом:

| А | = 2 .

Определение. Декартовым произведением множеств А и В называется множество, обозначаемое А В, элементами которого являются упорядоченные пары ( а, в ), где а А , в В.

Например. Пусть А = { а1, а2 }, В = { в1, в2, в3 }. Тогда

А В = { ( а1, в1 ), ( а1,в2 ), ( а1,в3 ), ( а2,в1 ), ( а2,в2 ), ( а2, в3 ) }.

Определение. Пусть Х – конечное множество. Декартовы степени множества Х определяются формулами

Х = Х , Х = Х Х , …, Х = Х Х .

Определение. Пусть А и В непустые множества. Обозначим через В - множество отображений, действующих из А в В, т.е. f В ↔ f : А → В . Множество В называется множеством степень.

Для конечных множеств справедливы следующие правила.

Правило суммы. Если | А | = n, | В | = m, то | А В | = n + m - | А ∩ В |,

и | А В | = m + n в том и только в том случае, когда А ∩ В = Ø.

Правило произведения. Если | А | = n , | B | = m , то | А В | = n · m.

Правило степени. Если | А | = n , | В | = m , то | А | = n .

Если Х – конечное множество, то

|Х | = | Х | .

Правило включения-исключения. Пусть Х ,…, Х – конечные множества, тогда справедлива формула

| Х Х … Х | = ( | Х | + … + | Х | ) – ( | Х ∩ Х | + | Х ∩ Х | + … +

+ | Х ∩ Х | ) + ( | Х ∩ Х ∩ Х | + … + | Х ∩ Х ∩ Х | ) + … +

+ (-1 ) | Х ∩ Х ∩…∩Х |

Замечание. Правило суммы является следствием этой формулы.

Основной принцип комбинаторики.

Если А ~ В , то | А | = | В |. Этот принцип является главным рабочим инструментом комбинаторики, т.е. он позволяет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если | А | = n , то с элементами множества А можно работать как с числами 0, 1, …, n-1.

Задача. Из города А в город В ведет три дороги, а из города В в город С – четыре. Сколькими способами можно добраться из города А в город С через город В?

Обозначим через АВ – множество дорог из А в В, через ВС – множество дорог из В в С. Тогда задача сводится к нахождению числа элементов в декартовом произведении АВ ВС , т.е. число способов будет равно

| АВ ВС | = | АВ | · | ВС | = 3 · 4 = 12.

Задача. Из города А в город В ведет три дороги, из города В в город С – четыре. Из А в С есть пять дорог, не проходящих через В. Сколькими способами можно попасть из А в С?

Обозначим через АВС множество всех способов добраться из А в С через В. Через АС обозначим множество способов добраться из А в С минуя В. Эти множества не пересекающиеся , поэтому число способов попасть из А в С определяется по правилу суммы и будет равно

| АВС | + | АС | = 12 + 5 = 17 .

Задача Сколько существует способов разослать семь писем в различные организации, если доставка осуществляется четырьмя курьерами?

Обозначим через К и П – множество курьеров и множество писем. Каждый способ доставки определяется указанием для каждого письма, какой из курьеров его доставляет, т.е. способ доставки это отображение множества писем во множество курьеров.

Тогда число способов доставки писем определяется по правилу степени и будет

равно

| К | = | К | = 4 = 16 384.

Задача. В кабину лифта девятиэтажного дома вошло три пассажира. Каждый из пассажиров может выйти на любом из восьми этажей. Сколькими способами может осуществиться разгрузка лифта.

Обозначим через П и Э множество пассажиров и множество этажей. Способ разгрузки лифта – это указание, на каком этаже выходит конкретный пассажир, т.е. сопоставление пассажиру этажа, на котором он выходит. Тогда число способов разгрузки лифта определяется по правилу степени и будет равно

| Э | = | Э | = 8 = 512.