Мощность множества

Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n равна 2ⁿ.

Множества, эквивалентные множеству всех действительных чисел, принадлежащих интервалу [0,1] имеют мощность континуума. Название «континуум» происходит от латинского слова continuum (непрерывное).

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

|А B| = |А| + |B| - |А B|,

т.е. мощность объединения двух множеств равно сумме количеств их элементов за вычетом числа общих их элементов. По индукции можно вывести формулу для определения мощности объединения любого количества множеств. Для трех множеств А, В, С она имеет вид

|А B C| = |А| + |B| + |C| - |А B| - |А B| - |А C| - |C B| + |А B C|. Для n множеств А₁,..., А_n мощность равна

|А₁ А₂ … А_n| = |А₁| + |А₂| + … + |А_n| -

- |А₁ А₂| - … - |А₁ А_n| - |А₂ А₃| - … - |А₂ А_n| - … - |А_n-1 А_n| +

+ |А₁ A₂ A₃| + … + |А₁ A₂ A₃| + … + |А₁ A₂ A_n| + … + |А_n-2 A_n-1 A_n| + (-1)^n-1 |А₁ A₂ A₃ … A_n|.

Конечное множество А имеет мощность k, если оно равномощно отрезку 1.. k;:

.

Если множество А конечно, | А| = k, то элементы А всегда можно перенумеровать, то есть поставить в соответствие элементам номера из отрезка 1..k с помощью некоторой процедуры. Наличие такой процедуры подразумевается, когда употребляется запись А = {а₁,...,а_k}.

По определению .

Мощность множества М это число его элементов, обозначается как . Здесь | М | - количество элементов конечного множества М, в дальнейшем называемое мощностью множества

Пример.

Множество натуральных чисел бесконечно, |, поскольку оно равномощно своему собственному подмножеству чётных чисел.

ТЕОРЕМА 1 Любое непустое конечное множество равномощно некоторому отрезку натурального ряда:

|А| = |1...k|.

доказательство

Рассмотрим следующую программу.

i = 0 { счётчик элементов }

wihle do

select { выбираем элемент }

i = i + 1 { увеличиваем счётчик }

{ ставим элементу в соответствие номер }

А: = А - x { и удаляем элемент из множества }

end while

Если эта процедура не заканчивает работу, то она даёт соответствие А ~ N. что невозможно ввиду конечности А. Значит, процедура заканчивает работу при i = k. Но в этом случае построено взаимно-однозначное соответствие А~1..k.

ТЕОРЕМА 2 Любой отрезок натурального ряда конечен:

.

доказательство

От противного. Пусть существуют бесконечные отрезки натурального ряда. Рассмотрим наименьшее п такое, что |1..п| = ∞. Тогда отрезок 1..п, равномощен некоторому своему собственному подмножеству А, |1..п| = |А|, то есть существует взаимно-однозначное соответствие f из отрезка 1..п в подмножество А. I: Обозначим . Рассмотрим соответствие из отрезка 1..n-1 в его собственное множество А - i, задаваемое следующим правилом:

if f(x) < i then f(x) else f(x) -1 end if.

Это соответствие является взаимно однозначным, а значит, отрезок 1..n-1 является бесконечным, что противоречит выбору п.

СЛЕДСТВИЕ Различные отрезки натурального ряда неравномощны:

п≠т=> \1..п\ ≠ |1..т|.

доказательство

Пусть для определённости п > т. Тогда . Если |1..п| = |1..т|, то |1..т| = ∞, что противоречит теореме.

Пример.

Условия равенства (неравенства) множеств

Множества М_а и М_b совпадают (равны),если у них одни и те же элементы. Символически это запишется следующим образом

М_а = М_b М_а М_b и М_b М_а

Если множество М_a - подмножество множества М_b и множество М_b - подмножество множества М_a, то оба этих множества состоят из одних и тех же элементов. Такие множества называются равными: М_а = М_b ,.