АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

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

Мощность множества А мы будем обозначать 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).

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

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

Задача. Известно, что из 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 (А)) = 2ⁿ.

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

Еⁿ ={(v ₁, v ₂,..., v _n): " v _k ÎЕ },

где Е - множество, содержащее 2 элемента: 0 и 1. Из следствия теоремы 2 вытекает, что card (Eⁿ) = (card(E))ⁿ = 2ⁿ. Покажем, что множества Eⁿ и b (А) равномощны. Пусть множество А = { а ₁, а ₂,..., а _n} и В некоторое подмножество А. Поставим в соответствие множеству В элемент (v ₁, v ₂,..., v _n), полагая

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

Дата добавления: 2015-09-27 | Просмотры: 748 | Нарушение авторских прав