Глава 2. Теория множеств

Глава 2. Теория множеств

Одним из основополагающих понятий математики является понятие множества. Множество — совокупность объектов, которые мы представляем себе как единое целое [29, 60]. Эти объекты называются элементами множества. Принадлежность некоторого элемента a множеству A можно указать так: a ∈ A, читается данная запись следующим образом: «a является элементом множества A» или «элемент a принадлежит множеству A». Если a не принадлежит A, то пишут a ∉ A.

Указать, какие элементы принадлежат множеству, можно несколькими способами, наиболее распространёнными из которых являются следующие [4, 9]:

1. перечислением элементов A = {a1, a2, . . . , an}, элементы множества A заключают в фигурные скобки и разделяют запятыми;
2. с помощью характеристического предиката A = {x: P(x)}. Характеристический предикат — это высказывание, позволяющее установить принадлежность объекта x множеству A. Если для некоторого x предикат P(x) принимает истинное значение, то x ∈ A, в противном случае x ∉ A.

Специальные обозначения множеств

Некоторые часто встречающиеся множества имеют специальные обозначения [27]:

• N = {1, 2, 3, . . .} — множество натуральных чисел,
• Z = {0, ±1, ±2, ±3, . . .} — множество целых чисел,
• Q = {p/q: p, q целые, q ≠ 0} — множество рациональных чисел.

Множество вещественных чисел обозначают R = (−∞, +∞), а комплексных — C.

Рассмотрим множество вещественных чисел, удовлетворяющих неравенствам a ⩽ x ⩽ b, где a < b. Такое множество будем называть сегментом или замкнутым отрезком и обозначать через [a, b], т. е. [a, b] = {x: a ⩽ x ⩽ b}.

Интервалом или открытым отрезком называется множество (a, b) = {x: a < x < b}.

Подмножества и операции над множествами

Множество A называется подмножеством множества B (обозначение: A ⊆ B), если x ∈ A ⇒ x ∈ B, т. е. все элементы A принадлежат множеству B. Два множества являются равными (A = B) тогда и только тогда, когда A ⊆ B и B ⊆ A. Если A ⊆ B и A ≠ B, то A называют собственным подмножеством множества B (A ⊂ B).

Универсальное множество U содержит в качестве подмножества любое из множеств, встречающихся в рассматриваемой задаче. Пустое множество, которое не содержит ни одного элемента, обозначается символом ∅. Считается, что пустое множество является подмножеством любого множества.

Рассмотрим основные операции на множествах:

• A ∪ B = {x: x ∈ A или x ∈ B} — объединение множеств A и B,
• A ∩ B = {x: x ∈ A и x ∈ B} — пересечение множеств A и B,
• A B = {x: x ∈ A и x ∉ B} — дополнение множества B до A, или теоретико-множественная разность A и B,
• A = {x: x ∉ A} — дополнение множества A (до универсального множества U),
• A △ B = {x: (x ∈ A и x ∉ B) или (x ∈ B и x ∉ A)} — симметрическая разность двух множеств A и B. Симметрическую разность двух множеств можно выразить через операции объединения, пересечения и дополнения: A △ B = (A ∩ B) ∪ (A ∩ B).

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

Пример 2.1

Пусть универсальным множеством является R. Тогда для множеств A = [0, 1] и R+ = (0, ∞) имеем:

• A ∪ R+ = [0, ∞),
• A ∩ R+ = (0, 1],
• A R+ = {0},
• R+ A = (1, ∞),
• A = (−∞, 0) ∪ (1, ∞),
• R+ = (−∞, 0],
• A △ R+ = R+ △ A = {0} ∪ (1, ∞).

Диаграммы Венна

Для наглядной иллюстрации соотношений теории множеств применяются диаграммы Венна. На диаграмме Венна изображают прямоугольник, точки которого представляют элементы универсального множества U. Подмножества множества U изображают кругами или эллипсами в этом прямоугольнике. Примеры некоторых часто встречающихся множеств приведены на рис. 2.1, 2.2.

Законы алгебры множеств

Основные законы алгебры множеств представлены в таблице 2.1. Если сравнить таблицы 2.1 и 1.2, то видно соответствие между законами алгебры множеств и законами алгебры логики.

Если в произвольном тождестве алгебры логики произвести замену операций ∪ ⇄ ∩ и множеств ∅ ⇄ U, то получится двойственное тождество. Последнее утверждение носит название закона двойственности, который наглядно иллюстрируется таблицей 2.1: каждое из тождеств левой колонки двойственно соответствующему тождеству правой, и наоборот.

Т а б л и ц а 2.1. Законы алгебры множеств

Законы идемпотентности	A ∪ A = A; A ∩ A = A
Свойства пустого и универсального множества	A ∪ ∅ = A; A ∪ U = U; A ∩ U = A; A ∩ ∅ = ∅
Свойства дополнения	A ∪ A = U; U = ∅; A ∩ A = ∅; ∅ = U; A = A
Законы коммутативности	A ∪ B = B ∪ A; A ∩ B = B ∩ A
Законы ассоциативности	A ∪ (B ∪ C) = (A ∪ B) ∪ C; A ∩ (B ∩ C) = (A ∩ B) ∩ C
Законы дистрибутивности	A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Законы поглощения	A ∪ (A ∩ B) = A; A ∩ (A ∪ B) = A
Законы де Моргана	(A ∪ B) = A ∩ B; (A ∩ B) = A ∪ B

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

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

Для вычисления мощности объединения двух конечных множеств можно воспользоваться формулой включений и исключений: |A ∪ B| = |A| + |B| − |A ∩ B|.

Показательным множеством (или булеаном) P(A) называется множество, элементы которого — все подмножества множества A, т. е. P(A) = {X : X ⊆ A}. Мощность булеана можно определить по формуле |P(A)| = 2|A|, в связи с чем используется ещё одно обозначение для булеана множества A, а именно 2A [9].

Счётные и несчётные множества

Понятие мощности можно обобщить на случай бесконечных множеств. Два множества A и B называются равномощными, если между их элементами существует взаимно однозначное соответствие, при котором каждому элементу из одного множества соответствует один и только один элемент другого. Множества, равномощные множеству натуральных чисел N, называются счётными, мощность таких множеств обозначается символом ℵ0 (читается «алеф нуль»). Множества Z и Q являются счётными, объединение конечного (и даже счётного) числа счётных множеств также счётно.

Теорема о несчётном множестве. Множество чисел интервала (0, 1) несчётно.

Докажем данное утверждение методом «от противного». Пусть существует способ, согласно которому каждому вещественному числу xk интервала (0, 1), где k = 1, 2, . . . , ставится в соответствие некоторое натуральное число. Запишем каждое из чисел xk в виде бесконечного десятичного разложения: xk = 0,xk1xk2 . . . xkk . . .

Диагональная процедура Кантора

Введём в рассмотрение число ex = 0,ex1ex2 . . . exk . . . , определённое в соответствии со следующим правилом: exk = 1, если xkk ≠ 1, и exk = 2, если xkk = 1.

Число ex не содержит в своей десятичной записи нулей и девяток, что позволяет исключить из рассмотрения последовательности вида 0,4999 . . . = 0,5000 . . . Заметим, что ex отличается от x1 в первом знаке после запятой, от x2 — во втором знаке, и т. д. В силу этого для любого k ∈ N выполняется неравенство ex ≠ xk. Следовательно, нельзя занумеровать все числа из интервала (0, 1), и множество чисел из интервала (0, 1) не является счётным. Теорема о несчётном множестве доказана.

Отметим, что рассмотренный способ построения вспомогательного числа ex носит название диагональной процедуры Кантора.

Мощность континуума и декартово произведение

Мощность интервала (0, 1) называют мощностью континуума и обозначают через c. Мощность континуума имеют множество всех иррациональных чисел R Q и множество вещественных чисел R. Мощность множества 2N равна мощности континуума.

Множество A × B = {(a, b): a ∈ A и b ∈ B} называется декартовым или прямым произведением множеств A и B. Элементы (a, b) множества A × B называются упорядоченными парами. Мощность прямого произведения конечных множеств A и B равна |A × B| = |A| × |B|.

Декартово произведение произвольного числа множеств определяется следующим образом: A1 × A2 × . . . × An = {(a1, a2, . . . , an): ai ∈ Ai, i = 1, 2, . . . , n}. Если все множества Ai совпадают, Ai = A, то для обозначения прямого произведения пишут An. Произвольный элемент множества An называется вектором.

Пример 2.2

Пусть A = {∅}, B = {1, 2}. Перечислим элементы множеств A × B и (2A)2.

Решение. Согласно определению декартова произведения множеств, элементы A × B являются всевозможными упорядоченными парами (a, b), где a ∈ A, b ∈ B. Таким образом, A × B = {(∅, 1), (∅, 2)}.

Булеан множества A состоит из всех подмножеств множества A = {∅}, значит, 2A = {∅, {∅}}. Осталось выписать элементы декартова произведения (2A)2 = 2A × 2A: (2A)2 = {(∅, ∅), (∅, {∅}), ({∅}, ∅), ({∅}, {∅})}.

Битовые строки и характеристические векторы

Битовой строкой (длины n) называется элемент множества Bn, где B = {0, 1}. Если A ⊆ U, где U = {u1, u2, . . . , un} — универсальное множество, то характеристическим вектором a множества A называется строка бит длины n вида (a1, a2, . . . , an), где ai = 1, если ui ∈ A, и ai = 0 — в противном случае. Характеристические векторы используют для моделирования операций на конечных множествах.

Пример 2.3. Пусть U = {1, 2, . . . , 10}. Запишем характеристические векторы множеств A, B, A, A ∪ B, A ∩ B, если A = {1, 2, 3}, B = {2, 4, 6, 8, 10}.

Решение. Обозначим характеристический вектор множества A через a, множества B — через b. Имеем: a = (1, 1, 1, 0, 0, 0, 0, 0, 0, 0), b = (0, 1, 0, 1, 0, 1, 0, 1, 0, 1).

Операциям отрицания, объединения, пересечения множеств соответствуют логические операции не, или, и над величинами 1 ≡ И, 0 ≡ Л. Следовательно, множество A представляется битовой строкой не a = (0, 0, 0, 1, 1, 1, 1, 1, 1, 1), множество A ∪ B — битовой строкой a или b = (1, 1, 1, 1, 0, 1, 0, 1, 0, 1), множество A ∩ B — битовой строкой a и b = (0, 1, 0, 0, 0, 0, 0, 0, 0, 0).

Примечание о корректности теории

Строго говоря, используемое в настоящем пособии понятие множества не является математически корректным. Внутренняя противоречивость теории множеств, построенной на таком определении, следует из анализа парадокса Рассела и других парадоксов [37, 53]. В настоящее время используются аксиоматические системы, на которых строится непротиворечивая теория множеств, среди них наиболее известна система аксиом Цермело–Френкеля [76].