Действительно, чтобы получить сюръективное отображение X →Y необходимо для каждого из m элементов множества Y указать множество прообразов. Такие множества

прообразов представляют собой разбиение множества X (число разбиений равно Snm ).

Для каждого разбиения, устанавливая взаимно однозначные соответствие между блоками разбиения множества X и соответствующими им образами, можно построить

m! различных сюръективных отображений. Числа S(n,m) = Snm m! называются

числами Стирлинга первого рода.

7. Число Белла

Число всех разбиений n-элементного множества называется числом Белла и обозначается Bn . По определению

n

B0 =1 и Bn = ∑Snm при n > 0 .

m=0

n

Теорема. Bn+1 = ∑Cnk Bk .

k =0

Доказательство. Пусть X – множество всех разбиений множества {1, 2,..., n +1} . Рассмотрим все подмножества множества {1, 2,..., n +1} , содержащие n +1. Для каждого такого множества A рассмотрим все разбиения, которые содержат A в качестве

(состоящих из a элементов, один из которых равенn +1) равно Cna−1 . Следовательно,

§6. Мощности множеств

1.Мощность конечного множества

Как уже отмечалось, если А – конечное множество, то его мощность A есть

количество элементов, принадлежащих А. Легко видеть, что

1). Если A ∩ B = , то A B = A + B .

2). В общей ситуации: A B =| A | + | B | − A ∩ B . 3). | A \ B |=| A | − | A ∩ B |.

Теорема1. Если A1 ,…, An – конечные множества, то

| Α1 ×Α2 × .....×Αn |= A1 A2 ...... An .

Доказательство непосредственно следует из подсчета числа различных n-ок.

25

Следствие. Если А – конечное множество, то An = A n

Теорема 2. Два конечных множества равномощны тогда и только тогда, когда

между ними существует биекция.

Доказательство очевидно.

Следствие. Никакое собственное подмножество или надмножество конечного

некоторое множество М, элементы которого определяются по n-ке описанным выше способом. Поскольку биективные множества имеют равное количество элементов

(теорема 2) и Bn =2n (следствие к теореме 1), то Ω (A) = 2n, что и требовалось доказать.

2. Мощности бесконечных множеств. Счетные множества

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

Установить биекцию с множеством натуральных чисел N фактически означает: сопоставить каждому элементу рассматриваемого множества номер, т.е. пронумеровать все элементы, или другими словами – пересчитать.

Конечное или счетное множество называется не более чем счетным.

Примеры и свойства счетных множеств.

•Множество четных чисел 2N – счетное. Действительно, биекцию 2N → N задает, например, отображение 2n a n .

•Множество целых чисел Z счетно. Соответствующей биекцией, очевидно, является следующее отображение

•Объединение не более чем счетного множества счетных множеств – счетно. Доказательство. Можно считать, что все множества и элементы в них уже

}, Α2 = {a21 , a22 , a23 , a24 , ...},

}…. Расположим все элементы, 43 43 4441 4231 32 33 34

объединения A1 A2 A3 A4 ... следующим образом и пронумеруем в порядке, указанном стрелкой (рис. 6.1).

26

Понятно, что при указанном способе рассмотрения элементов всякий элемент рано или поздно получит свой номер. Если Αi имеют непустые пересечения и в процессе

нумерации встречаются элементы уже ранее пронумерованные, то их будем пропускать

расположим так же, как и в предыдущем примере (в виде бесконечной вправо и вниз прямоугольной таблицы) и пронумеруем аналогично. Таким образом, произведение двух счетных множеств – счетно. Дальше по индукции для любого числа множителей.

•Множество Q – рациональных чисел счетно.

есть объединение счетного количества счетных множеств.

•Множество алгебраических чисел A (корней всевозможных многочленов с целыми коэффициентами) – счетно (докажите).

3.Несчетные множества. Мощность континуума

Теорема(Кантор).

Множество всех действительных чисел из отрезка [0; 1] – несчетно.

Доказательство. Представим все числа в двоичной системе счисления в виде бесконечных двухзначных дробей (в случае конечных дробей дополним справа нулями до бесконечности). Предположим, что количество рассматриваемых чисел счетно. Расположим их в порядке возрастания номеров:

27

Легко видеть, что этого числа нет среди пронумерованных, так как оно отличается от 1-го числа в 1-ом разряде, от второго – во 2-ом разряде, от третьего – в 3- ем разряде, … . Полученное противоречие показывает, что множество действительных чисел из отрезка [0; 1] не является счетным.

Определение. Мощность множества действительных чисел отрезка[0; 1]

называется мощностью континуума.

Примеры.

1)Множество всех действительных чисел R имеет мощность континуума. Доказательство. Прежде всего, отметим, что любые два отрезка равномощны.

например, формулой g(x) = tg x .

2)Множество иррациональных чисел имеет мощность континуума, так как оно равно R \ Q, а Q – счетно.

3)Множество трансцендентных чисел имеет мощность континуума. Действительно, оно равно R\A, где A – счетное множество алгебраических чисел.

4)Множество комплексных чисел C.

5)Множество непересекающихся окружностей на плоскости.

4. Кардинальные числа. Гипотеза континуума

Теорема. Булеан счетного множества имеет мощность континуума. Доказательство. Пусть A = {a1 , a2 ,..., an ,...}. Построим биекцию Ω(A)→[0, 1].

равномощны, что и требовалось доказать.

Для обозначения мощностей бесконечных множеств используются так называемые кардинальные числа. Мощность счетного множества обозначается0 (алеф− ноль). Мощность континуума – 1 (алеф− один).

Поскольку Ω(A) = 2 A для конечных множеств и булеан счетного множества

имеет мощность континуума, то и для бесконечных множеств имеем: 2 0 = 1 .

Можно показать, что вообще (теорема Кантора) булеан всякого множества A имеет мощность большую чем A (и всякое его подмножество). Таким образом,

2 1 = 2 , ... , 2 n = n+1 , …

Подобно тому, как не существует наибольшего натурального числа, не существует множества, имеющего наибольшую мощность.

Континуум – гипотеза утверждает, что всякое бесконечное подмножество R имеет мощность 0 или 1 , т.е. нет множеств, мощности которых выражаются

промежуточными «дробными» кардинальными числами. В более общей форме, не существует бесконечных множеств, имеющих другие мощности, кроме

i , i N {0} .

28