Глава 1. ТЕОРИЯ МНОЖЕСТВ И БИНАРНЫХ ОТНОШЕНИЙ

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

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

Такой подход называется аксиоматическим [1].

При изучении всех разделов дискретной математики, в том числе и элементов теории множеств и бинарных отношений, мы также используем аксиоматический подход [1—6, 11].

Основные понятия теории множеств

Множество — совокупность объектов, хорошо различимых нашей интуицией или мыслью, обладающих неким сходством и объединенных в одно общее.

Элементы множества обозначаются маленькими латинскими буквами, сами множества — заглавными. Например, чтобы показать, что элемент а принадлежит множеству Л, мы пишем а е А, в противном случае а е А.

Во множество можно объединять самые разные объекты. Например, множество натуральных чисел А, множество целых чисел Z, множество действительных чисел /?, множество предметов в вашей комнате IV и т.д.

Элементами множества могут выступать другие множества, например /) = ^[1]. Такое множество V называется классом или семейством [2].

Количество элементов во множестве называется мощностью или кардинальным числом. Например, мощность множества М= {а, Ь, с} равна 3, М — 3. В зависимости от мощности множества могут быть конечные и бесконечные. Множество, в состав которого не входит ни одного элемента, называется пустым и обозначается как 0. Мощность пустого множества равна нулю. Но мощность множества С, элементом которого является пустое множество, равна единице, С = {0},С = 1.

Множества равномощны, если их мощности равны. Например, множества /) = ^[1] и К={а, Ъ} равномощны.

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

Если каждому элементу бесконечного множества можно поставить в соответствие натуральное число я, е N, причем только одно без пропусков и повторений, то это множество называется счетнобесконечным и его мощность равна |А| = А₀ (алеф-нуль), первому трансфинитному числу. Второе трансфинитное число А, алеф, равно мощности множества Я действительных чисел. Известно и третье

трансфинитное число А = 2^А = 2² °, алеф-один, равное множеству точек в пространстве, заданных координатами (х,у, г). Трансфинитные числа обозначают буквами еврейского алфавита.

Кантор создал шкалу трансфинитных чисел: алеф-ноль, алеф, алеф-один,... .

Считаем, что множество счетное, если выполняется один из двух случаев:

• • множество состоит из конечного числа элементов, т.е. его кардинальное число совпадает с одним из натуральных чисел;
• • множество счетно-бесконечное, т.е. его мощность совпадает

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

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

Множество А называется подмножеством В, если каждый элемент аI из А, я, е А, принадлежит одновременно и множеству В, а₁ е В, А В. В предельном случае множества Аи В могут состоять из одних и тех же элементов.

Если во множестве В найдется хотя бы один элемент х,-, который не принадлежит А, Зх/, х,- <е В, х,- й А, то А — собственное подмножество В, А с В. Пустое множество 0 всегда является подмножеством любого множества В.

Между понятиями «подмножество» и «собственное подмножество» существует значительная разница. Так, подмножество А может совпадать с самим множеством В, т.е. А < |2?|, но собственное подмножество С всегда состоит из меньшего количества элементов, чем В, т.е. |С| < В.

Например, рассмотрим два множества Л/, = {а, Ъ, с} и М₂ = {а, Ь, с, с!}. Множество М, является собственным подмножеством М₂, так как в М₂ имеется элемент б, не принадлежащий множеству М_х.

Множество В в приведенных выше определениях часто называют надмножеством (собственным надмножеством) множества А

Множества Л и В равны, если являются подмножествами (надмножествами) друг друга.

Для каждого множества М можно построить новое множество, элементами которого являются все подмножества М и только они. Тогда множество М называется универсумом и обозначается как /, а множество всех его подмножеств — буяеаном В(1).

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

Например, возьмем в качестве универсума / множество натуральных чисел на отрезке [1, 3], 1= {1, 2, 3}, тогда булеан В(1) = {0, {1}, {2}, {3}, {1,2}, {1,3}, {2, 3}, {1,2, 3}}. Если мощность универсума равна

ш, то мощность его булеана всегдаВ(1) = 2^т.

Теорема 1.1. Основная теорема о конечных множествах

Любое конечное множество не может быть эквивалентно никакому своему собственному подмножеству.

При определении множеств и подмножеств можно столкнуться с парадоксом Рассела, который заключается в следующем. Рассмотрим множество А всех множеств В, не содержащих себя в качестве элементов, А = {В/В Если множество Л существует, то содержит ли А в качестве элемента самого себя, т.е. А е А? При ответе на этот вопрос мы сталкиваемся с логическим противоречием: если А е А, то по определению элементов множества А ? А. Если А то А е А.