Как найти дополнение объединения множеств

---

Набор — это набор предметов.

Мы обозначаем набор с помощью заглавной буквы, а элементы в наборе определяем с помощью фигурных скобок. Например, предположим, что у нас есть некоторый набор под названием «A» с элементами 1, 2, 3. Мы запишем это так:

А = {1, 2, 3}

В этом руководстве объясняются наиболее распространенные операции с множествами, используемые в теории вероятностей и статистике.

Союз

Определение: Объединение множеств A и B — это множество элементов, которые находятся либо в A, либо в B.

Обозначение: А ∪ В

Примеры:

• {1, 2, 3} ∪ {4, 5, 6} = {1, 2, 3, 4, 5, 6}
• {1, 2} ∪ {1, 2} = {1, 2}
• {1, 2, 3} ∪ {3, 4} = {1, 2, 3, 4}

Перекресток

Определение: Пересечение множеств A и B — это множество элементов, которые находятся как в A, так и в B.

Обозначение: А ∩ В

Примеры:

• {1, 2, 3} ∩ {4, 5, 6} = {∅}
• {1, 2} ∩ {1, 2} = {1, 2}
• {1, 2, 3} ∩ {3, 4} = {3}

Дополнение

Определение: Дополнением множества A называется множество элементов, которые входят в универсальное множество U, но не входят в A.

Обозначение: A’ или A c

Примеры:

• Если U = {1, 2, 3, 4, 5, 6} и A = {1, 2}, то A c = {3, 4, 5, 6}
• Если U = {1, 2, 3} и A = {1, 2}, то A c = {3}

Разница

Определение: Разность множеств А и В — это множество элементов, которые есть в А, но отсутствуют в В.

Обозначение: А – Б

Примеры:

• {1, 2, 3} – {2, 3, 4} = {1}
• {1, 2} – {1, 2} = {∅}
• {1, 2, 3} – {4, 5} = {1, 2, 3}

Симметричная разница

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

Обозначение: А Δ В

Примеры:

• {1, 2, 3} ∆ {2, 3, 4} = {1, 4}
• {1, 2} ∆ {1, 2} = {∅}
• {1, 2, 3} Δ {4, 5} = {1, 2, 3, 4, 5}

Декартово произведение

Определение: Декартово произведение множеств A и B — это множество упорядоченных пар из A и B.

Обозначение: А х В

Примеры:

• Если A = {H, T} и B = {1, 2, 3}, то A x B = {(H, 1), (H, 2), (H, 3), (T, 1), ( Т, 2), (Т, 3)}
• Если A = {T, H} и B = {1, 2, 3}, то A x B = {(T, 1), (T, 2), (T, 3), (H, 1), ( Н, 2), (Н, 3)}

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

Допустим, нам нужно найти все целые числа, которые удовлетворяют неравенству

. Нам дано универсальное множество целых чисел:

Целые числа, которые удовлетворяют неравенству:

Допустим, у нас есть множество

— подмножество некоторого универсального множества

. Дополнение

— это все остальные элементы из

, которые не вошли в

.

В нашем примере выше, дополнение для

— это множество, содержащее все целые числа, которые не удовлетворяют неравенству:

.

Мы можем проиллюстрировать это определение на другом примере. Если нашим универсальным множеством являются города России, то возможным подмножеством является множество городов миллионников:

Москва, Санкт-Петербург, Новосибирск, Екатеринбург, Казань, Нижний Новгород, Челябинск, Самара, Уфа, Ростов-на-Дону, Омск, Волгоград, Воронеж, Краснодар, Красноярск, Пермь

.

Тогда дополнением

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

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

. Над именем исходного множества может стоять черточка или символ подчеркивания. Мы будем использовать

.

В этом уроке мы подробно рассмотрим дополнение множества, его определение и свойства.

---

Самостоятельная работа

«Теория систем и системный анализ»

И. Б. Родионов

Лекция 13: Операции над множествами. Упорядоченное множество

1. Объединение множеств

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

Объединение X и Y обозначается через X∪Y

Формально x∈X∪Y ⇔ x∈X или x∈Y

Пример 1. Если X={1,2,3,4,5} и Y={2,4,6,8}, то

X∪Y={1,2,3,4,5,6,7,8}

Пример 2. Если X={x:x — отл.гр.}, и Y={x:x — gib.}, то

X∪Y={x:x — или отл., или gib}.

Пример 3. Если X — множество точек левого круга и Y — множество точек правого круга, то

X∪Y — заштрихованная область, ограниченная обоими кругами.

Понятие объединения можно распространить и на большее число множеств, на систему множеств. Обозначим через М={X₁,X₂, …,X_n} совокупность n множеств X₁,X₂, …,X_n, называемую иногда системой множеств. Объединение этих множеств

∪X_i=∪(X∈M), Х=X₁∪X₂∪…∪X_n

представляет собой множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств данной системы М.

Для объединенных множеств справедливы:

• X∪Y = Y∪X — коммутативный закон
• (X∪Y)∪Z = X∪(Y∪Z) = X∪Y∪Z — ассоциативный закон,

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

Очевидно, что X∪∅ = X. Отсюда можно видеть, что ∅ играет роль нуля в алгебре множеств.

2. Пересечение множеств

Пересечение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y.

Пересечение множеств обозначается X∩Y.

Формально x∈X∩Y ⇔ x∈X и x∈Y

Пример 4. X={1,2,3,4,5} Y={2,4,6,8} X∩Y = {2,4}

Пример 5. Если Х — множество точек левого круга, а Y — множество точек правого круга, то X∩Y представляет собой заштрихованную область, являющуюся общей частью обоих кругов.

Множества X и Y называются непересекающимися (дизъюнктными), если они не имеют общих элементов, то есть если X∩Y=∅.

Пример 7. {1,2,3} и {4,5,6}

В отличие от алгебры чисел, где могут быть три возможности: a<b, a=b, b<a между двумя множествами X и Y может быть одно из 5 cотношений:

X=Y; X⊂Y; Y⊂X; X∩Y=∅ и X и Y находятся в общем положении.

Говорят, что множества X и Y находятся в общем положении, если выполняются три условия:

1. существует элемент множества X, не принадлежащий Y;
2. существует элемент множества Y, не принадлежащий X;
3. существует элемент, принадлежащий как X, так и Y.

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

∩X=∩X_i=X₁∩X₂∩…∩X_n

Пересечение множеств представляет собой множество, элементы которого принадлежат каждому из множеств системы М.

Для пересечения множеств справедливы:

• X∩Y=Y∩X — коммутативный закон
• (X∩Y)∩Z = X∩(Y∩Z) = X∩Y∩Z — ассоциативный закон

Заметим также, что имеет место соотношение X∩∅=∅.

Пример 8. A={a,b}, B={b,c}, C={a,c}.

A∩B∩C=∅, хотя A∩B={b}, B∩C={c}

3. Разность множеств

Разность множеств определена только для двух множеств. Разностью множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат X и не принадлежат Y.

Обозначается: XY.

Формально: x∈XY ⇔ x∈X и x∉Y

Пример 9. (см. Пример 1) X={1,2,3,4,5}, Y={2,4,6,8}, XY={1,3,5}, YX={6,8}

Разность множеств не обладает свойством коммутативности.

XY≠YX

Если AB=∅, то A⊂B — поставить ? обратно

при A∩B≠∅

4. Универсальное множество

Роль нуля в алгебре множеств играет пустое множество. А нет ли такого множества, которое играет роль «1», т.е. удовлетворяет условию: X∪I = X, что означает, что пересечение или «общая часть» множества I и множества X для любого множества X совпадает с самим этим множеством. Это возможно лишь в том случае, если множество I содержит все элементы, из которых может состоять множество X, так что любое множество X полностью содержится в множестве I.

Множество I, удовлетворяющее этому условию, называется полным, или универсальным, или единичным.

Если при некотором рассмотрении участвуют только подмножества некоторого фиксированного множества, то это самое большое множество будем считать универсальным и обозначать I.

Пример 12 (Пример 1). I — множество целых чисел

Пример 13 (Пример 2). I — множество студ. гр.

Пример 14 (Пример 3). I — лист бумаги, доска

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

Универсальное множество обладает интересным свойством, которое не имеет аналогии в обычной алгебре, а именно, для любого множества X справедливо соотношение X∪I = I.

5. Дополнение множества

Множество, определяемое из соотношения X¯ = IX, называется дополнением множества X (до универсального множества I).

На диаграмме множество X¯ представляет собой незаштрихованную область.

Формально: X = {x: x∈I и x∉X}.

Из определения следует, что X и X¯ не имеют общих элементов. Х∩X¯=∅.

Кроме того, не имеется элементов I, которые не принадлежали бы ни X, ни X¯ (его дополнению), так как те элементы, которые не принадлежат X, принадлежат X¯ (его дополнению). Следовательно, Х∪X¯=I.

Из симметрии данной формулы относительно Х и X¯ следует не только то, что X¯ является дополнением Х, но и что Х является дополнением X¯. Но дополнение X¯ есть X¯ ¯. Таким образом, X¯ ¯=X¯.

С помощью операции дополнения представим разность множеств:

XY = {x: x∈X и x∉Y} ={ x: x∈X и x∈Y¯ }, т.е. XY= Х∩Y¯.

Порядок выполнения операций:

1. дополнение;
2. пересечение;
3. объединение, разность.

Для изменения порядка используют скобки.

6. Разбиение множества

Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств.

Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.

Пример. Продукция предприятия: — высший сорт, I, II, брак.

Рассмотрим некоторое множество M и систему множеств

М = {X₁, X₂, …, X_n}

Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям:

1. Любое множество X из M является подмножеством множества М

   ∀X∈M: X⊆M;

2. Любые два множества X и Y из М являются непересекающимися

   ∀X∈М, ∀Y∈M: X≠Y → X∩Y=∅.

3. Объединение всех множеств, входящих в разбиение, дает множество M

   X₁∪X₂∪…∪ X_n=M.

7. Тождества алгебры множеств

С помощью операций объединения, пересечения и дополнения из множеств можно составлять различные алгебраические выражения.

Если алгебраические выражения V(X,Y,Z) и S(X,Y,Z) представляют собой одно и то же множество, то их можно приравнять друг другу, получая алгебраическое тождество вида V(X,Y,Z) = S(X,Y,Z)

1. (X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогичное дистрибутивному закону (a+b)c=(a+c)(b+c) в обычной алгебре).
2. (X∩Y)∪Z = (X∪Z)∩(Y∪Z)
3. Если Y⊆X, то X∩Y=Y, X∪Y=X. Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит пересечение этих множеств, то есть общая множеств Х и Y совпадает с Y. В объединение множеств X и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества Х. Следовательно, X∪Y совпадает с X.
4. Пусть в примере 3 Y=X. Тогда, учитывая, что X⊆X, то X∩Х=Х, X∪Х=X. (идемпотентность).
5. Докажем тождество (X∪Y)¯=X¯∩Y¯. Предположим, что х∈(X∪Y)¯, то есть х∉X∪Y. Это значит, что х∉X и х∉Y, то есть и x&isinX¯ и x&isinY¯;. Следовательно, x∈X¯∩Y¯. Предположим теперь, что y∈X¯∩Y¯, то есть y∈X¯ и y∈Y¯. Это значит, что y∉X и y∉Y, то есть что y∉X∪Y. Следовательно, y∈(X∪Y)¯.
6. Тождество (X∩Y)¯=X¯∪Y¯. Обычно тождества 5) и 6) называются тождествами де-Моргана.
7. (AB)∩C=(A∩C)B=(A∩C)(B∩C)
8. AB=A(A∩B)
9. A=(A∩B)∪(AB)

Дополнение к занятию «операции над множествами»

Множество элементов, принадлежащих или A, или B, называют симметричной разностью или дизьюнктивной суммой.

S = A⊕B = (AB)∪(BA) = (A∩B¯)∪(A¯∪B) = (A∪B)∩(A∩B)¯

Для симметрической разности выполняются следующие законы:

1. 1) A⊕B = B ⊕A — коммутативность,
2. 2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,
3. 3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,
4. 4) A ⊕А = ∅
5. 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.

Упорядоченное множество

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

Пример 1. Множество людей, стоящих в очереди, множество слов в фразе, алфавит. Во всех этих множествах место каждого элемента является вполне определенным и не может быть произвольно изменено.

Число элементов кортежа называется его длиной. Обозначают кортеж скобками «< >», иногда круглыми «( )». А=<a₁, a₂, …, a_n>. Кортежи длины 2 называются упорядоченными парами, 3 — тройками, n-ками.

Частный случай: кортеж длины 1 — <a>

кортеж длины 0 — < > или ∧ — пустой кортеж.

Отличие кортежа и обыкновенного множества: в кортеже могут быть одинаковые элементы.

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

Так, кортеж <a₁, a₂> может рассматриваться как точка на плоскости или вектор, проведенный из начала координат в данную точку. Тогда компоненты a₁, a₂ — проекции вектора на оси 1 и 2.

Пр₁ <a₁, a₂> = a₁, Пр₂ <a₁, a₂> = a₂, Пр_i <a₁, a₂, a₃>= a_i, Пр₁2 <a₁, a₂, a₃>= <a₁, a₂> — двухэлементный кортеж. Проекция кортежа на пустое множество осей — пустой кортеж.

Обобщая эти понятия, будем рассматривать упорядоченное n-элементное множество вещественных чисел (a₁, …, a_n) как точку в воображаемом n–мерном пространстве (иногда называемом гиперпространством), или как n-мерный вектор. При этом компоненты n-элементного кортежа а будем рассматривать как проекции этого кортежа на соответствующие оси.

Пр_i a = a_i, i=1,2,…,n

Пр_i,j,…,l a = <a_i, a_j, …, a_l>, i=1,2,…,n

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.

<a₁, …, a_m> = <b₁, …, b_n> ⇔ m = n и a₁ = b₁, b₁ = b₂, …

Компонентами кортежа (вектора) могут быть также компоненты кортежи (векторы):

Пример. Слова в предложении,

A = < <a₁, a₂>, <a₁, a₃>, <a₂, a₃> >

Прямое произведение множеств

Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.

Формально: X*Y = {<x,y>: x∈X, y∈Y}

Пример 2. Пусть X=<1,2>, Y=<1,3,4>

Тогда X*Y={<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4> } См. рис. а).

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

Прямое произведение изменяется при изменении порядка сомножителей т.е.

X*Y ≠ Y*X

Прямое произведение множеств X₁, X₂, …, X_n — это множество, обозначаемое X₁*X₂*…*X_n и состоящее из всех тех и только тех кортежей длины n, правая компонента которых принадлежит X₁, вторая — X₂ и т.д.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Аналогично X₁*X₂*…*X_n = ∅ тогда и только тогда, когда хотя бы одно из множеств X₁, X₂, …, X_n является пустым.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

M^s=M*M*…*M, M¹=M, M⁰=∧.

Обычно R — множество вещественных чисел, тогда R²=R*R — вещественная плоскость и R³=R*R*R — трехмерное вещественное пространство.

Пример. A={a,b,c,d,e,f,g,h}, B={1,2,3, …,8}

Тогда A*B ={a₁, a₂, a₃, …, h7, h8} — множество обозначающее все 64 клеток шахматной доски.

Пример. Пусть A — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества обычно называют алфавитами. Элементы множества a_n называются словами длины n в алфавите A. Множество всех символов в алфавите A — это множество A^* = ∪Aⁱ = A¹∪A²∪A³… . При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями.

СЛОВО ⇔ <С,Л,О,В,О>

Теорема. Пусть a₁, a₂, …, a_n — конечные множества и |a₁| = m₁, |a₂|=m₂, …, |a_n|=m_n. Тогда мощность множества a₁*a₂*a₃*…*a_n равна произведению мощностей a₁, a₂, …, a_n

|a₁*a₂*…*a_n|=|a₁|*|a₂|*|a₃|*…*|a_n|= m₁*m₂*…*m_n

Следствие |a_n|=|A|ⁿ

Проекция множества.

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

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Пример. Пусть М={<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тогда Пр₂М={2,1,3}, Пр₃M={3}, Пр₄M={4,5,3}, Пр₂₄M={<2,4>,<1,5>,<3,3>}, Пр₁₃M={<1,3>,<2,3>,<3,3>}, Пр₁₅M={<1,5>,<2,5>,<1,3>}, Пр₂₅M={<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно что если М=Х*Y то Пр₁М=Х, Пр₂М=Y

и если Q⊆Х*Y то Пр₁Q⊆Х и Пр₂Q⊆Y

Пример. V={<a,b,d>,<c,b,d>,<d,b,b>}

Пр₁V={a,c,d}

Пр₂V={b}

Пр₃V={d,b}

Пр₁2V={<a,b>,<c,b>,<d,b>}

Пр₂3V={<b,d>,<b,b>}

Пр₁3V={<a,d>,<c,d>,<d,b>}

Пусть V — множество векторов одинаковой длины S.

Пр_iV ={Пр_iv/v∈Y}, Пр_ii…ikv = { Пр_ii…ikv/v∈Y}.

Если V =A₁*A₂*…*A_n, то Пр_ii…ikV=A_i1*A_i2*…*A_ik.

В общем случае Пр_iV — вовсе не обязательно прямое произведение: оно может быть подмножеством.

В этом параграфе
будут рассмотрены три простые операции,
которые можно производить над множествами:
объединение, пересечение и разность
(дополнение) множеств.

Опр.1.2.1.
Пусть даны множества А
и В.
Их объединением
называется множество С,
состоящее из элементов, принадлежащих
хотя бы одному из множеств А,
В.

Объединение
множеств обозначается символами «+»
и ««:
.
Пусть, например, А={-6,
-3, 0, 3, 6} B={0,
2, 4, 6, 8}. Тогда .
Геометрически объединение множеств
изображено на рис. 2.

Аналогично
определяется объединение большего
числа множеств.

Опр.1.2.2.
Объединением множеств А₁,
А₂,
А₃,
…, А_n
(обозначение
называется множество, состоящее из
элементов, принадлежащих хотя бы одному
из множеств А₁,
А₂,
А₃,
…, А_n.

Свойства операции объединения.

Теор.
1.2.1. Справедливы
следующие равенства:

1. (коммутативность);

2. (АВ)С=А(ВС)
   (ассоциативность);

3. Если ,
   то АВ=
   А;

4. А
   Ø= А.

Док-во.
Формулы, подобные формулам 1-2, обычно
доказываются так. Берётся элемент,
принадлежащий правой части равенства,
и доказывается, что он принадлежит левой
части. В результате для формулы 1,
например, будет доказано, что .
Затем берётся элемент, принадлежащий
левой части, и доказывается, что он
принадлежит правой части равенства;
для формулы 1 это будет означать, что .
Из включений
и
следует, что .

Итак,
пусть.
Это значит, что либо ,
либо ,
либо одновременно
и .
Во всех трех случаях .
Включение
доказано. Пусть теперь .
Это значит, что либо ,
либо ,
либо одновременно
и .
Во всех трех случаях .
Включение
доказано. Следовательно, ,
что и требовалось доказать.

Другой способ
доказательства — изобразить левую и
правую часть равенства для одних и тех
же множеств на диаграммах Эйлера-Венна
и убедиться, что они изображают одно и
тоже множество. Так, для формулы 1 диаграммы приведены
слева.

Задание.
Самостоятельно доказать включения
соответствующих множеств и изобразить
диаграммы для формул 2-4.

Опр.1.2.3.
Пересечением
множеств А
и В
называется множество С,
состоящее из элементов, принадлежащих
одновременно и множеству А,
и множеству В.
Если множества А
и В не
имеют общих элементов, их пересечение
равно пустому множеству; в этом случае
множества А
и В
называются непересекающимися.

Пересечение
множеств обозначается символами «»
и «»
(знак умножения):
или С=АВ.
Для примера, приведенного после опр.1.2.1,
.
Геометрически пересечение множеств
представлено на рис. 3.

Свойства операции пересечения множеств.

Теор.
1.2.2. Справедливы
следующие равенства:

1. (коммутативность);

2. (АВ)
   
   
   С=А
   (ВС)
   (ассоциативность);

3. Если ,
   то АВ=
   В;

4. А
   Ø= Ø.

Задание.
Самостоятельно доказать включения
соответствующих множеств и изобразить
диаграммы для формул 5-8.

Опр. 1.2.4
пересечения множеств для большего числа
множеств: Пересечением множеств А₁,
А₂,
А₃,
…, А_n
(обозначение )
называется множество, состоящее из
элементов, входящих в каждое из множеств
А₁,
А₂,
А₃,
…, А_n.

Теор. 1.2.3.
Для операций объединения и пересечения
множеств справедливы законы
дистрибутивности:

1. ;

2. .

Док-во:
Докажем формулу 9. Пусть .
Тогда либо
(следовательно,
и ,
т.е. );
либо
(следовательно, одновременно,
()
и
(),
т.е. );
либо одновременно
и
(в этом случае можно применить любое из
приведённых выше рассуждений). Таким
образом, доказано, что .

Пусть .
Рассмотрим два случая. 1. Пусть .Тогда
.
2. Пусть ,
но ,
т.е. одновременно и ,
и .
Это возможно, только если одновременно
и ,
и ;
т.е. ,
откуда следует, что .
Включение
доказано.

Задание.
Самостоятельно доказать формулу 10.

Опр. 1.2.5.
Разностью
множеств А
и В
называется множество АВ,
содержащее те элементы множества А,
которые не принадлежат множеству В.

В
опр. 1.2.5
не предполагается, что
(рис. 4). Если же ,
то разность АВ
называется дополнением
множества В
до множества А
(рис. 5). Для
дополнения множества А
до универсального множества U
применяется
обозначение
(рис. 6).

Теор.
1.2.4. Операции
разности и дополнения антидистрибутивны
относительно операций объединения и
пересечения:

11.
;

1. .

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

Док-во.
Докажем формулу 11. Пусть
.
Это означает, чтои,
т.е.,.
Следовательно,и,
т.е..
Включениедоказано.

Пусть
.
Это означает, что одновременно и(т.е.и),
и(т.е.и).
Так каки,
то.
Но,
следовательно,.
Включениедоказано. Из справедливости доказанных
включений следует справедливость
формулы 11.

Задание.
Самостоятельно доказать формулу 12 и
обобщение формул 11, 12 на большее число
множеств:

13.
; 14..

Соседние файлы в папке lec1

• #
• #
• #
• #

Введение в теорию множеств

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

Когда-то давным давно во всех академических дисциплинах было заложено фундаментальное убеждение — существует единственная бесконечность.

Но 1874 году довольно малоизвестный математик провёл серию революционных наблюдений, подвергавших сомнению это всеми принятое и глубоко укоренившееся убеждение. Георг Кантор в своей (теперь уже ставшей легендарной) публикации On a Property of the Collection of All Real Algebraic Numbers доказал, что множество вещественных чисел «более многочисленно», чем множество алгебраических чисел. Так он впервые показал, что существуют бесконечные множества разных размеров (не волнуйтесь — для прояснения этого мы вскоре подробно изучим его статью).

«Множество — это большое количество, которое позволяет воспринимать себя как одно» — Георг Кантор

С 1874 по 1897 год Кантор неистово публиковал статью за статьёй, разворачивая свою теорию абстрактных множеств в расцветающую дисциплину. Однако она была встречена упорным сопротивлением и критикой; многие педанты считали, что его теории перешли в область философии и нарушили принцип религии.

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

Теория множеств — это математическая теория о точно определённых наборах (множествах) отдельных объектов, называемых членами или элементами множества.

Сколько чисел есть между 0 и 1?

Первая публикация Кантора, состоящая из четырёх с половиной страниц, является великолепным примером краткости. Она разделена на два отдельных доказательства, совместно приводящих к выводу о существовании по крайней мере двух уникальных видов множеств.

В первой части теории исследуется множество вещественных алгебраических чисел и доказывается, что это бесконечное счётное множество. Здесь не стоит путать — «счётное» не обязательно значит, что счёт ведётся строго в целых числах; в контексте теории множеств «счётное» означает, что множество, пусть даже состоящее из бесконечного числа элементов, можно описать повторяющимся рядом, например упорядоченной многочленной функцией. Кантор назвал это свойство бесконечного набора чисел соответствия «один к одному» с рядом, наличием взаимно однозначного соответствия.

Если говорить вкратце, то набор, или множество всех вещественных алгебраических чисел можно вывести с помощью какого-то теоретического ряда многочленов с различными степенями и коэффициентами; следовательно, множество всех вещественных алгебраических чисел является бесконечным счётным множеством.

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

Затем Кантор указывает, что в любом замкнутом интервале [a,b] существует хотя бы одно транцендентное число, которое никогда нельзя будет подсчитать в бесконечном счётном множестве. Поскольку одно такое число существует, то предполагается, что в семействе вещественных чисел существует бесконечное количество транцендентных чисел.

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

Далее: запись и операции

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

Стоит также поделиться интересным наблюдением: большинство людей, использующих теорию множеств на практике, ценят скорее не эту конкретную теорему, а заданный ею обобщённый язык. Благодаря своей абстрактной природе теория множеств скрытно влияет на множество областей математики. В математическом анализе, который требует дифференциального и интегрального исчисления, необходимо понимание пределов и непрерывности функций, окончательно закреплённых в теории множеств. В алгебре логики логические операции «и», «или» и «не» соответствуют операциям пересечения, объединения и разности в теории множеств. И последнее, но не менее важное — теория множеств закладывает основы топологии — исследования геометрических свойств и пространственных отношений.

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

Часть вторая. Краткий обзор операций, обозначений и диаграмм Венна.

Как сказано в предыдущей части, одно из фундаментальных преимуществ теории множеств произрастает не из какой-то конкретной теории, а из созданного ею языка. Именно поэтому основная часть этого раздела будет посвящена обозначениям, операциям и визуальному представлению теории множеств. Давайте начнём с объяснения базовых символов обозначения множества — соответствующих ему элементов. В таблице ниже показан пример одного множества A с тремя элементами:

A — это множество с элементами «1», «2» и «3»

«1» — элемент множества A

В первой строке показано множество A с тремя отдельными элементами (A = {1,2,3}); во второй строке показан правильный способ обозначения отдельного конкретного элемента 1, принадлежащего множеству A. Пока всё довольно просто, но теория множеств становится существенно интереснее, когда мы добавляем второе множество — начинается путешествие по стандартным операциям.

Для показанной выше таблицы давайте введём два дополнительных множества B и C, содержащие следующие элементы: B = {3,A,B,C,D,E}, C = {1,2}. Хоть мы и создали три множества (A,B и C), в показанных ниже примерах операции выполняются одновременно только с двумя множествами, поэтому внимательно следите за тем, какие множества указаны в самом левом столбце. В показанной ниже таблице представлено пять самых распространённых операндов множеств:

Операции: пересечение (intersection) — множество элементов, принадлежащих множеству A и множеству B;

объединение (union) — множество элементов, принадлежащих множеству A или множеству B;

подмножество (subset) — C является подмножеством A, множество C включено во множество A;

собственное (истинное) подмножество — C является подмножеством A, но C не равно A;

относительное дополнение (relative complement) — множество элементов, принадлежащих к A и не к B.

Вот и они, самые распространённые операции в теории множеств; они довольно популярны и в областях за пределами чистой математики. На самом деле, высока вероятность того, что вы уже видели подобные типы операций в прошлом, хоть и не совсем с такой терминологией, и даже пользовались ими. Хорошая иллюстрация: попросите любого студента описать диаграмму Венна из двух пересекающихся групп, и он интуитивно придёт к правильному результату.

Ещё раз взгляните на последнюю строку, относительное дополнение — какое необычное сочетание слов, правда? Относительное к чему? Если относительное дополнение A — B определяется как A и не B, то как нам обозначить всё, что не является B?

Универсальное множество — пустое множество

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

Для любого подмножества A множества U дополнение множества A (обозначаемое A′ или U − A) определяется как множество всех элементов в генеральной совокупности U, которое не находится в A. Если вернуться к поставленному выше вопросу, то дополнением множества B является всё в пределах универсального множества, что не принадлежит B, в том числе и A.

Прежде чем мы двинемся дальше, надо упомянуть ещё одно принципиальное множество, которое достаточно важно для базового понимания: нулевое или пустое множество. Учтите, что существует единственное пустое множество, поэтому никогда не говорят «пустые множества». Хотя мы не будем рассматривать в этой статье эквивалентность, основная теория гласит, что два множества эквивалентны, если они имеют одинаковые элементы; следовательно, может быть только одно множество без элементов. Поэтому существует единственное пустое множество.

Диаграммы Венна и остальное

Диаграммы Венна, официально изобретённые в 1880 году Джоном Венном, являются именно тем, что вы и представляете, хотя их научное определение звучит примерно так:

Схематичное изображение всех возможных отношений нескольких множеств

Ниже показано изображение шести самых распространённых диаграмм Венна, и почти во всех показаны недавно изученные нами операнды:

Объединение (union), пересечение (intersection), относительное дополнение (relative complement), симметрическая разность (symmetric difference), собственное множество (proper subset), абсолютное дополнение (universal дополнение).

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

Закончим мы этот раздел введением понятия мощности (кардинального числа). Мощность множества, обозначаемая символом абсолютного значения — это просто количество уникальных элементов, содержащихся в определённом множестве. Для показанного выше примера мощность трёх множеств равна: |A| = 3, |B| =6, |C| = 2.

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

Часть 3. Мощность и показательные множества

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

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

Примеры мощности множеств

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

Помните подмножества из предыдущей части статьи? Оказывается, что мощность некоторого множества A и количество возможных подмножеств множества A имеют удивительную связь. Ниже показано, что количество подмножеств, которые можно составить из некоторого подмножества, увеличивается с порядком мощности на предсказуемую величину:

Количество возможных подмножеств в C= 2^|C|

Давайте подробно рассмотрим показанный ниже пример. Однако для начала поразмыслим над формулой. Представим мощность как общее количество «позиций», которое представляет множество. При создании некоторого подмножества для каждой возможной позиции принимается булево решение (да/нет). Это означает, что каждый уникальный элемент, добавляемый к множеству (то есть увеличивающий мощность на единицу) увеличивает количество возможных подмножеств на множитель два. Если вы программист или учёный, то можете уяснить эту логику немного глубже, если поймёте, что все подмножества множества можно вычислить с помощью таблицы двоичных чисел.

Показательное множество (булеан)

Прежде чем мы вычислим все подмножества для примера множества C, я хотел бы ввести последнее понятие — булеан.

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

Для удобства форматирования я убрал запятые между множествами***

Чем может быть полезен булеан? На самом деле, вы скорее всего много раз интуитивно использовали булеаны, даже об этом не догадываясь. Каждый раз, когда вы выбираете подмножество элементов из более крупного множества, вы выбираете элемент булеана. Например ребёнок внимательно изучающий кондитерский магазин с купюрой в 5 долларов — какой элемент булеана множества всех доступных сладостей он выберет? Или если взять более технический пример: вам, как разработчику ПО может потребоваться запросить всех возможных пользователей базы данных, также обладающих свойством X и Y — ещё один случай, в котором одно подмножество выбирается из всех возможных подмножеств.

Эквивалентность и биективная функция

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

Очевидно, что два множества с одинаковой мощностью имеют некое общее свойство, но на этом сходства заканчиваются — что если в одном из множеств есть многократно повторяющийся элемент? Что если два множества имеют одинаковую мощность и количество элементов? Нельзя отрицать, что они в какой-то степени «эквивалентны», но даже в этом случае всё равно есть возможность различий, потому что каждое множество может иметь разные элементы, повторяющиеся одинаковое количество раз. Смысл здесь в том, что концепция эквивалентности в теории множеств немного чужда другим областям математики. Установление эквивалентности в этом мире требует знакомства с этой концепцией и нового языка. В последней части этой статьи мы введём понятие эквивалентности, а также таких базисных свойств, как инъективные, биективные и сюръективные функции.

Часть 4. Функции.

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

Функция в мире теории множеств — это просто соответствие некоторых (или всех) элементов из Множества A некоторым (или всем) элементам Множества B. В показанном выше примере набор всех возможных элементов A называется областью определения; элементы A, используемые в качестве входных значений, в частности называются аргументами. Справа набор всех возможных выходных значений (называющихся в других областях математики «областью значений»), называется кообластью; набор настоящих выходных элементов B, соответствующих A, называется образом.

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

Инъекции, сюръекции и биекции

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

• Функция является инъективной (или «один к одному»), если каждый элемент в кообласти отображается не более чем на один элемент в области определения.
• Функция является сюръективной, если каждый элемент в кообласти отображается не менее чем на один элемент в области определения. (то есть образ и кообласть функции эквивалентны.)
• Функция является биективной, если каждый элемент кообласти отображается ровно на один элемент области определения.

Вишенкой на торте этих сложных определений стали возможные дополнительные значения слов «инъективный», «сюръективный» и «биективный». Когда они используются для описания функции (соответствия), верным будет представленное выше значение; однако также верно будет идентифицировать функции (соответствия) исключительно по этим характеристикам. То есть функция с инъективным поведением называется инъекцией, функция с сюръективным поведением — сюръекцией, а функция с биективным поведением — биекцией.

Прочитайте заново представленный выше список пунктов. Биекция — это просто функция, удовлетворяющая обоим предыдущим требованиям; то есть, функция инъективна и сюръективна. Инъективная функция не должна быть сюръективной, а сюръективная — инъективной. Ниже показан визуальный пример, в котором эти три классификации привели к созданию функций множеств, определяемых четырьмя возможными комбинациями инъективных и сюръективных свойств:

Биекция (инъекция + сюръекция), инъекция (инъекция + не-сюръекция), сюръекция (не-инъекция + сюръеция), без классификации (не-инъекция + не-сюръекция)

Вот и всё! Теперь мы обладаем элементарным пониманием самых часто встречаемых соотношений, встречающихся в мире множеств. Однако это ни в коем случае не конец нашего пути: напротив, это самое начало.

Фундаментальные основы теории множеств — ключ к пониманию более высокоуровневых областей математики. Чтобы продолжить наше движение вверх, к этим различным областям, далее нужно будет, пользуясь своими знаниями о теории множеств, уяснить одну из самых революционных теорий в истории математики: систему аксиом Цермело-Френкеля.