Определение. Если для двух множеств А и В существует биекция А на В, то говорят что они имеют равную мощность. Если же существует инъекция множества А на В и не существует биекции между ними, то говорят, что мощность множества А меньше мощности множества В.
Первый зародыш общего понятия равномощности появляется у Галилея, заметившего, что отображение 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 штук. По предыдущей теореме получаем необходимое равенство.
Задача. Известно, что из 100 студентов живописью увлекается 28 человек, спортом - 42 человека, музыкой - 30, живописью и спортом - 10, живописью и музыкой - 8, спортом и музыкой - 5, живописью, спортом и музыкой - 3. Найти количество студентов, занимающихся только спортом; не увлекающихся ничем.
Решение. Обозначим первой большой буквой множество студентов, увлекающихся тем или иным видом (например, Ж – множество студентов, увлекающихся живописью). Множество всех студентов обозначим через U. Тогда нас интересует card(С – (ЖÈМ)) и card(U –(ЖÈМÈС)). Из теоремы 1 и ее следствия, свойств операций над множествами имеем:
где Е - множество, содержащее 2 элемента: 0 и 1. Из следствия теоремы 2 вытекает, что card (En) = (card(E))n = 2n. Покажем, что множества En и b(А) равномощны. Пусть множество А = {а1, а2, ..., аn} и В некоторое подмножество А. Поставим в соответствие множеству В элемент (v1, v2, ..., vn), полагая
Несложно проверить, что данная функция является инъекцией и сюръекцией множества b(А) на множество Е . Таким образом, card(b(A)) = 2n.
