Упражнения

1. В примере 2 проиллюстрировано свойство дистрибутив­ности слева операции пересечения относительно операции объединения . Подтвердить справедливость свойства дист­рибутивности справа пересечения относительно объедине­ния , а также слева и справа относительно , т.е.:

а) (А В) С = (А С) (В С) - справа относитель­но ;

б) А (В С) = (А В) (А В) - слева относительно ;

в) (А В) С = (А С) (B С) - справа и относитель­но .

2. Построить диаграммы Венна, иллюстрирующие мно­жества а) - л) из упражнения 7 в пункте 1.2.

3. Построить диаграммы Венна, иллюстрирующие мно­жества а) - з) из упражнения 8 в пункте 1.2. Отметить точками внутри соответствующих областей диаграмм элементы ис­ходных множеств U, А, В, С.

4. Пусть А,В,С U. Проиллюстрировать на примере кон­кретных множеств и с помощью диаграмм Венна справед­ливость следующих соотношений:

а) А (В С) = (А В) С; д) А (A В) = А;

б) A (B С) = (А В) С; е) A (A B) = A

в) = ; ж) (A B) ₍ A ₎ = A

г) = ; з) A ₍ B₎ = A B.

1.4. Доказательства

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

Ниже в примерах 1-5 проиллюстрированы наиболее час­то используемые в теории множеств приемы доказательств:

• доказательство равенства - соотношений типа X = Y;

• доказательство единственности существования;

• доказательство от противного.

В примерах 1, 2 доказательства соотношений типа X = Y, где X и Y - множества, основаны на использовании определений I и II равенства двух множеств.

В соответствии с определением I для равенства двух мно­жеств требуется совпадение их элементов. Поэтому сначала доказывается, что для произвольного элемента а из того, что а X, следует, что а Y, затем доказывается, что если а Х, то а Y. Таким образом, элементы множествам X и Y совпадают и, следовательно, по определению I, X=Y.

В соответствии с определением II, Х = Y, если Х Y и Y X. Поэтому для доказательства равенства двух множеств тре­буется показать справедливость включений X Y и Y X.

В примере 3 для доказательства единственности суще­ствования теоретико-множественного объекта X использо­ван основной математический подход, в соответствии с ко­торым сначала предполагается, что существуют два таких объекта X' и X", а затем доказывается, что они совпадают: Х'=Х", т.е. Х'=Х"=Х.

На последовательности примеров 1 - 4 показано, как мож­но выводить сравнительно сложные утверждения путем пос­ледовательности доказательств простых утверждений.

Пример 5 иллюстрирует косвенный метод доказательства - доказательство от противного. Для доказательства ис­тинности некоторого утверждения Q при исходных услови­ях Р предполагается, что Q при этих условиях ложно; далее показывается, что в таком случае имеют место противоре­чия. Следовательно, принятое предположение ложно, т.е. утверждение Q - истинно *.

Пример 1. Доказать справедливость соотношения

А (В С) = (А В) (A С)

Строгое обоснование этого и др. подходов к доказательству см., например, в [3. ч. 3, га. 4, § 3].

(свойство дистрибутивности слева объединения относи­тельно пересечения ).

Такое доказательство может быть выполнено с помо­щью диаграмм Венна (см. пример 2, пункт 1.3). Здесь для этих целей используем один из приемов доказательства равенства двух множеств.

В соответствии с определением I равенства множеств мно­жества равны, т.е. Х = Y, если их элементы совпадают. Это означает, что Х = Y, если из того, что а X, следует а Y, и из того, что а X, следует а Y.

Покажем сначала, что если произвольный элемент а при­надлежит левой части соотношения, т.е. а А (В Q), то он принадлежит и правой части данного соотношения, т.е. а (А B) (A Q). Пусть

1. a A (B C)

Из определения операции объединения следует, что элемент а принадлежит объединению множеств А и (В С), если он принадлежит хотя бы одному из них (или, что очевидно, тому и другому). Таким образом, а А или а (В Q), при этом возможны следующие случаи:

1.1. a принадлежит множеству А и а не принадлежит пе­ресечению множеств В С:

а А и а (В С).

Последнее условие выполняется, если а не принадлежит В, или С, или им обоим, т.е.

1.1.1. а А, а В, а С;

1.1.2. а А, а B, a C;

1.1.3. а А, a В, а С;

1.2. а А и а (B С),т.е. а А ,а В, а С;

1.3. а А и а (B С),т.е. а А ,а В, а С.

Рассмотрим каждый из этих случаев.

1.1. Так как а А, то а принадлежит объединению множества А с любым множеством, в том числе а (А В) и а (А С); следовательно, а принадлежит и их пересечению:

а (А B) (A C).

1.2. Так как а В, а С, то а (A B) и а (A C), следовательно,

а (A B) (A C)

1.3. Так как а А, то этого достаточно, чтобы а (A B) и а (A C) следовательно

а (A В) (A C).

Таким образом, в любом из рассмотренных случаев из того, что а A (B C), следует, что а (A B) (A C).

Покажем теперь справедливость второго условия опреде­ления I равенства множеств: если произвольный элемент а не принадлежит левой части соотношения а A (B C), то он не принадлежит и правой части данного соотношения а (A B) (A C). Пусть теперь:

2. а A (B C).

Элемент а не принадлежит объединению двух множеств, если он не принадлежит ни одному их них. Тогда а А и а (B C), т.е. возможны следующие случаи (см. п. 1.1):

2.1. a A, a B, a C;

2.2. a A, a B, a C;

2.3. a A, a B, a C.

Рассмотрим каждый из этих случаев:

2.1. Так как а А, а В, то а (A В), следовательно, а (A B) (A C).

2.2. Так как а А, а C, то а (A C), следовательно, а (A B) (A C).

2.3. Так как а А, а В, то этого достаточно, чтобы а (A В) и, следовательно,

а (A B) (A C).

Как видим, в любом из этих случаев из того, что а A (B C), следует, что а (A B) (A C).

Таким образом, множества A (B C) и (A B) (A C) совпадают и по определению I равенства множеств

A (B C) = (A B) (A C),

что и требовалось доказать.

Примечание 1. В примере 1 проверка условий 1.1.3 и 2.3 вооб­ще говоря избыточна.

Примечание 2. Далее будем использовать символ , который в выражениях типа P Q будет означать: "если справедливо Р, то спра­ведливо и Q " или "из того, что Р, следует Q" и т.п., а символ в выра­жениях типа P Q будет означать: "тогда и только тогда, когда", "если и только если" и т.п.

Пример 2. Доказать справедливость соотношения

(А В) С = (A С) (B С)

(свойства дистрибутивности справа пересечения относи­тельно объединения ).

Множества X = Y, если X Y и Y X. Поэтому пока­жем сначала, что (А В) С (A C) (B C), т.е. любой произвольный элемент a из множества, заданного левой ча­стью соотношения, принадлежит и множеству, заданному правой частью соотношения.

Пусть а (A B) С. Тогда

а (A B) и а С

(а A или a B) и (a С)

(а A и a C) или (a B и a С)

а (A C) или а (B C)

а (A C) (B C).

Таким образом, (A В) С (A C) (B C).

Покажем теперь, что (A C) (B C) (A В) С, т.е. любой элемент а из множества, заданного правой частью ис­ходного соотношения, принадлежит и множеству, заданно­му левой частью исходного соотношения.

Пусть а (A C) (B C). Тогда

а (А С) или а (В С)

(а А и а С) или (а B и а С)

(а А или а B) и а С

а (А B) и а С

а (А B) С.

Следовательно, (A C) (B C) (A В) С.

Таким образом, (A В) С (A C) (B C), что и требовалось доказать.

Примечание 3. В примере 2, в силу точного совпадения второй час­ти доказательства с первой, можно записать:

а (А B) С а (А B) и а С и т.д.

Пример 3*. Доказать, что относительно данного универ­сального множества U дополнение любого множества , если А U, единственно.

 Для доказательства единственности дополнения множества А U предположим, что существуют два множе­ства В и С в U, каждое из которых удовлетворяет требовани­ям дополнения множества A, т.е. их пересечение с А пусто, а объединение с А дает U:

а) B A = ; б) C A = ;

в) B A = U; г) C A = U.

Очевидно, что В = В U. С учетом условия г) В = В (С A).

Тогда по доказанному выше (см. пример 2, пункт 1.3)

B = (B C) (B A), но с учетом условия а) В = (B C)  = В п С, т.е. В = В п С. Поэтому

а B а B и а С B (B C) B B и B C.

Очевидно, что B B, отсюда следует, что B С.

В то же время (с учетом условий в), б), а также в соответ­ствии с доказанным выше примером 2 пункта 1.3):

С = С U = С (В А) = (С B) (С A) = (С B)  = С B.

Поэтому

а C а C и а B C (C B) C C и C B.

Отсюда следует, что C B.

Таким образом B C и C B, откуда В = С. Следователь­но, B = С = и - единственно, что и требовалось дока­зать.

Пример 4*. Пусть даны множества А, В, С такие, что A B C=U и A,B,C попарно не пересекаются. Доказать, что

, , .

 Докажем, что А = В С.

По условию, А, В, С попарно не пересекаются, т.е.

а) A B = ; б) A C = ; в) B C = ,

кроме того,

г) A В С= U, т.е. A (В С)= U.

Согласно доказанному в примере 2, пункта 1.3, A (В С)= (A B) (A C), где в соответствии с условиями а), б): (A B) (A C)=  =. Таким образом, A (В С)=.

Итак, пересечение А и (В С) пусто, а их объединение по условию г) составляет универсальное множество U:

A (В С)=; A (В С)=U.

Следовательно, В С удовлетворяет условиям для , кото­рое единственно (в соответствии с доказанным в примере 3). Поэтому , что и требовалось доказать.

Аналогично доказывается и

Пример 5*. Доказать, что для произвольных множеств А и В имеет место соотношение А В .

 Отметим вначале, что если а ,то а и проведем доказательство от противного, т.е. допустим, что А В . Тогда

1. A B _если a A_{, то} a B.

С другой стороны,

2. существует элемент а такой, что а и a а и a A.

Но тогда с учетом (1) - (2):

a A и а a B и а a ₍B _{) =}  (проти­воречие).

Следовательно, предположение ложно и поэтому ,т.е. А В .

Аналогично можно показать, что А В, зна­чит, А В , что и требовалось доказать.