05. Мощность множеств. Конечные множества

Определение. Если для двух множеств А и В существует биекция А на В, то говорят что они имеют Равную мощность. Если же существует инъекция множества А на В и не существует биекции между ними, то говорят, что мощность множества А меньше мощности множества В.

Первый зародыш общего понятия равномощности появляется у Галилея, заметившего, что отображение n ® n2 устанавливает биекцию между натуральными числами и их квадратами. Этот пример был приведен Галилеем в качестве контрпримера к “аксиоме”: “целое больше части”. Понятие равномощных множеств было введено Больцано.

Мощность множества А мы будем обозначать card(A). По определению, если множества А и В равномощны, то пишут card(A) = card(B). Если же мощность множества А меньше мощности В, то соответственно пишут card(A)<card(B). В этом случае, согласно определению, множество А равномощно некоторой части множества В.

Если рассмотреть отношение “иметь равную мощность” на множестве всех множеств, то нетрудно проверить, что оно является отношением эквивалентности.

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

В случае, когда в конечном множестве А содержится n элементов, говорят, что его мощность равна n и пишут card(А)=n.

Теорема 1. Для конечных множеств справедливы равенства:

А) если АÇВ=Æ, то card(АÈВ) = card(A)+card(B);

Б) если АÇВ¹Æ, то card(АÈВ) = card(A)+card(B)-card(AÇB).

Доказательство. Осуществляется прямым счетом элементов множества АÈВ. В случае а) из хÎАÈВ Þ либо хÎА и хÏВ, либо хÏА и хÎВ. Из этого уже следует утверждаемое. В случае же б) множество АÈВ можно разбить на следующие части: элементы хÎА и хÏВ, элементы хÎВ и хÏА и, наконец элементы хÎА и хÎВ.

Следствие. Если АÍВ, то card(B-A) = card(B)-card(A).

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

Card(A´B) = card(A)´card(B).

Доказательство. Пусть А={а1, а2, ..., аn} и В={в1, в2, ..., вm}. Тогда А´В= {(аi, вj): i=1, 2,..., n; j=1, 2,..., m}= {(а1, в1), (а1, в2), ..., (а1, вm)}È{(а2, в1), (а2, в2), ..., (а2, вm)}È.....È{(аn, в1), (аn, в2),..., (аn, вm)}. Каждое из множеств, входящих в выписанное объединение, не пересекается с остальными и содержит точно m элементов. Всего множеств в объединении n штук. По предыдущей теореме получаем необходимое равенство.

Следствие. Справедливо равенство card(An) = (card(A))n.

Задача. Известно, что из 100 студентов живописью увлекается 28 человек, спортом - 42 человека, музыкой - 30, живописью и спортом - 10, живописью и музыкой - 8, спортом и музыкой - 5, живописью, спортом и музыкой - 3. Найти количество студентов, занимающихся только спортом; не увлекающихся ничем.

Решение. Обозначим первой большой буквой множество студентов, увлекающихся тем или иным видом (например, Ж – множество студентов, увлекающихся живописью). Множество всех студентов обозначим через U. Тогда нас интересует card(С – (ЖÈМ)) и card(U –(ЖÈМÈС)). Из теоремы 1 и ее следствия, свойств операций над множествами имеем:

Card(С – (ЖÈМ)) = card(С – ((ЖÈМ)ÇС))) =

= card(С) –card((ЖÇС)È(МÇС)) =

= card(С) – (card(ЖÇС) + card(МÇС) – card(ЖÇМÇС)) =

= 42 – (10 + 5 – 3) = 30.

Card(U – (ЖÈМÈС)) = card(U) – card(ЖÈМÈС) =

= 100 – (card(ЖÈМ) + card(С) – card((ЖÈМ)ÇС) =

= 100 – (card(Ж) + card(М) – card(ЖÇМ) + 42 card((ЖÇС)È(МÇС))) =

= 100 –(28 + 30 – 8 + 42 – (card(ЖÇС) + card(МÇС) – card(ЖÇМÇС))) =

= 100 – (92 – (10 +5 – 3)) = 100 – (92 – 12) = 20.

Теорема 3. Если card(А) = n, то card(B(А)) = 2n.

Доказательство. Рассмотрим множество

Еn ={(V1, V2, ..., VN): " VK ÎЕ },

Где Е - множество, содержащее 2 элемента: 0 и 1. Из следствия теоремы 2 вытекает, что card (En) = (card(E))n = 2n. Покажем, что множества En и B(А) равномощны. Пусть множество А = {А1, А2, ..., АN} и В некоторое подмножество А. Поставим в соответствие множеству В элемент (V1, V2, ..., VN), полагая

Несложно проверить, что данная функция является инъекцией и сюръекцией множества B(А) на множество Е. Таким образом, card(B(A)) = 2n.

Задачи.

1. Можно ли сказать, что если А = В, то А и В равномощны, и наоборот, если А и В равномощны, то А=В?

4. Доказать, что для любых трех конечных множества А, В, С справедливо равенство, называемое формулой включения и исключения:

Card(AÈBÈC) = card(A)+card(B)+card(C) – card(AÇB) – card(AÇC) – card(BÇC) +card(AÇBÇC).

< Предыдущая		Следующая >