Мощность множества. 
Теория множеств

Понятие мощности множества служит для количественной характеристики множеств.

Множество, состоящее из конечного числа элементов, называется конечным. Множество, состоящее из бесконечного числа элементов, называется бесконечным.

В случае конечного множества для того, чтобы понять, сколько в нем элементов, нужно просто их посчитать. Но как поступать в случае бесконечного множества. Как количественно охарактеризовать бесконечное множество и тем более как сравнивать бесконечные множества по количеству элементов в них? На первый взгляд кажется абсурдным — как это одна бесконечность может быть больше или меньше другой. Оказывается, может.

Воспользуемся следующей идеей. Допустим, у нас есть конечное множество, причем мы знаем, сколько в нем элементов, и есть какое-то другое конечное множество, количество элементов в котором нам не известно. Как понять, совпадает количество элементов в этих множествах или нет. Можно поступить так: берем любой элемент из и ставим с ним в пару любой из, делаем это до тех пар, пока не израсходуем все элементы или. Если в итоге останутся элементы из или, которым не хватило пары, то и, очевидно, имеют разное число элементов, а если всем хватило пары (то есть, установилось, так называемое, взаимно-однозначное соответствие между элементами множеств и), то и состоят из одинакового количества элементов. Такой подход можно распространить для количественного сравнения любых множеств, конечных или бесконечных.

Введем аккуратно понятие взаимно-однозначного соответствия множеств. Из школы вам, наверняка, уже известно понятие функции. Вспомним, что это такое.

Пусть — непустые множества.

Определение 6.1.

Функцией называется правило, по которому каждому элементу — аргументу функции, ставится в соответствие единственный элемент , — значение функции.

Видно, что такое определение гарантирует однозначность только в одну сторону, то есть для каждого можно найти единственный такой, что. При этом в один и тот же могут переходить различные. Такие примеры вы в школе видели, например парабола дает одно и тоже значение при и. Итак сформулируем определение взаимно-однозначного соответствия.

Определение 6.2.

Функция называется взаимно-однозначной (по-другому, биекцией, взаимно-однозначным соответствием), если для каждого элемента найдется единственный элемент такой, что. Обозначение .

Определение 6.3.

Множества и имеют равные мощности, называются равномощными (количественно эквивалентными), если между их элементами можно установить взаимно-однозначное соответствие .

Если и количественно эквивалентны, то пишут (читается «мощность множества равна мощности множества «).

Если — конечное множество, то равномощное ему множество содержит одинаковое с ним количество элементов, поэтому полагают, где — количество элементов в .

Пример 6.1.

Если А={-9;0;7;23}, то |А|=4.

Если =Ш, полагают .

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

Определение 6.4.

Бесконечное множество называется счетным (счетной мощности), если оно равномощно множеству натуральных чисел, то есть (, — множество натуральных чисел).

Если — счетное, пишут .

Бесконечное множество, не являющиеся счетными, называются несчетными.

Пример 6.2 (примеры счетных множеств).

• 1) N={1;2;3;4;…} - множество натуральных чисел,
• 2) Z={0;1;-1;2;-2;3;-3;4;-4;…} - множество целых чисел,
• 3) Q={| m, n — целые числа, n?0} - множество рациональных чисел.

Определение 6.5.

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

Утверждение 6.1.

Множество действительных чисел несчетно.

Среди несчетных множеств отдельно выделяют так называемые множества мощности континуум.

Определение 6.6.

Говорят, что — множество мощности континуум (или имеет мощность континуум), если оно равномощно множеству действительных чисел ().

Если — множество мощности континуум, пишут .

Пример 6.3 (примеры множеств мощности континуум).

• 1) — множество действительных чисел,
• 2) все числовые промежутки, содержащие больше одной точки,
• 3) совокупность подмножеств множества натуральных чисел (),

4) множество бесконечных двоичных последовательностей .

Утверждение 6.2 (свойства мощностей множеств).

• 1) Всякое бесконечное подмножество содержит счетное подмножество,
• 2) Всякое подмножество счетного множества конечно или счетно,
• 3) Добавление к бесконечному множеству конечного или счетного множества не меняет его мощности.

Сравнение мощностей множеств Мощность множества считается меньшей, чем мощность множества, если в найдется подмножество равномощное, но в подмножество равномощное отсутствует.

То есть, .

Теорема 6.1 (Кантора-Бернштейна).

Если одновременно и, тогда .

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

Мощность совокупности подмножеств любого непустого множества больше мощности самого множества (Ш).

Следствие 6.1.

Существуют мощности больше любой наперед заданной.

Для подтверждения этого достаточно перейти от множества заданной мощности к совокупности его подмножеств и воспользоваться теоремой Кантора.

Замечание 6.1.

1) Если конечно и, то можно показать, что ,.

2) Для обозначения различных мощностей множеств используют так называемые кардинальные числа .

Видно, что для конечных множеств используются обычные числа, а для бесконечных — вводятся новые числа — бесконечные кардиналы, которых вы раньше, наверняка, не знали.

Самый маленький бесконечный кардинал — это счетный кардинал, затем начинаются несчетные кардиналы, первый из которых предположительно, в рамках континуум гипотезы, это — кардинал мощности континуум. Но справедливость этого факта до сих пор в общем случае не была, ни доказана, ни опровергнута.

Формулы включений и исключений Пусть — конечные множества. Причем нам известны их мощности и мощность пересечения. И мы хотим через эти известные значения выразить мощность объединения, то есть количество элементов в нем (Рис. 6.1).

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

.

позволяющую определить мощность объединения двух конечных множеств.

Аналогичную формулу можно выписать для случая трех множеств :

Таким же образом и в случае произвольного числа конечных множеств, процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название этих формул.

Пример 6.4.

В доме проживает 200 семей, из которых 180 имеют компьютер и 150 автомобиль, при этом 14 семей не имеют компьютер, но имеют автомобиль.

Сколько семей имеют и то и другое.

Введем обозначения — множество семей, имеющих компьютер, — множество семей, имеющих автомобиль. Итак, требуется найти .

По условию получаем.

, .

С одной стороны, имеем.

.

так как (доказательство этой формулы предлагается читателю в качестве упражнения),.

а с другой,.

.

значит,.

.

1.7 Метод математической индукции Метод математической индукции предназначен для доказательства утверждений, зависящих от натурального параметра. Он состоит из двух этапов:

1) база индукции

Утверждение проверяется для малых значений параметра .

2) шаг индукции

Проверяется верность утверждения для значения параметра равного в предположении, что оно верно для .

Пример 7.1.

1) Доказать формулу.

.

База индукции.

,.

Шаг индукции.

Доказано.

Можно доказать методом математической индукции формулу бинома Ньютона.

Кратко можно эту формулу записать так:

Числа называются биномиальными коэффициентами. Верхний индекс в обозначении коэффициентов показывает, в какой степени входит, а нижний — в какой в соответствующем коэффициенту слагаемом в сумме справа. Вообще говоря, переменные и в формуле (7.1) можно поменять местами, ведь от перемены мест слагаемых сумма не меняется, тогда индексы коэффициентов будут означать соответственно верхний — степень, а нижний — степень .

Обратите внимание, что сумма степеней и в каждом слагаемом в правой части формулы (7.1) равна, по-другому просто не может быть, если степень бинома равна .

Биномиальные коэффициенты вычисляются по следующей общей формуле, где (целые неотрицательные числа), причем ,.

Для быстрого нахождения биномиальных коэффициентов используют треугольник Паскаля (Рис. 7.1).

Рис. 7.1.

Попробуйте самостоятельно догадаться, как строится треугольник Паскаля. Это несложно.