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

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

Виды доказательств в теории множеств:

1) Геометрический – использование диаграмм Эйлера-Венна.

2) Аналитические методы:

Равенства с множествами имеют вид:

A (A, B, C, …)=B (A, B, C, …) (1)

либо вид

A (A, B, C, …)=Æ (2)

1. Универсальным методом доказательства равенств вида (1) является использование условия равенства 2-х множеств:

A=B Û (AÍB)&(BÍA) (3)

2. Универсальным методом доказательства равенства вида (2) является приведение к противоречию предположения, что A≠Æ, т.е. предположения о существовании такого а, что а ÎA (доказа-тельство от противного).

3. Доказательство единственности существования множества X.

Используется основной математический подход, в соответствии с которым сначала предполагается, что существует 2 таких множества X ′ и X ², а затем доказывается, что они совпадают:

X ′= X ², т.е. X ′= X ²= X.

Пример 1. Доказать справедливость соотношения – A È(B Ç C)= =(A È B)Ç(A È C).

Доказательство:

1-ый метод – геометрический с помощью диаграмм Эйлера-Венна.

Диаграммы Эйлера-Венна (картинки аудентичны, т.е. при наложении совпадают, если выдержаны масштабы и расположение изображений множеств A, B, C) (см. рис. 1.8).

2-ой метод. Покажем, что выполняется одновременно 2 условия:

а) a Î A È(B Ç C)® a Î(A È B)Ç(A È C);

б) a Î A È(B Ç C) a Î(A È B)Ç(A È C).

Доказательство:

(®) 1. ù a Î A È(B Ç C).

1.1 a Î A Ú a Î B Ç C.

1.2 a Î A Ú(a Î B & a Î C).

1.3 a Î A Ú a Î B ® a Î(A È B).

1.4 a Î A Ú a Î C ® a Î(A È C).

1.5 a Î(A È B)& a Î(A È C)® a Î(A È B)Ç(A È C).

() 2. ù a Î(A È B)Ç(A È C).

2.1 a Î(A È B)& a Î(A È C).

2.2 a Î(A È B)® a Î A Ú a Î B.

2.3 a Î(A È C)® a Î A Ú a Î C.

2.4 a Î A & a Î A Ú a Î B & a Î C.

2.5 a Î A Ú a Î B & a Î C.

2.6 a Î A Ú a Î(B Ç C).

2.7 a Î A È(B Ç C).

Одновременным выполнением 2-х условий доказывается справедливость соотношения.

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

Для доказательства единственности дополнения множества A Í U предположим, что существуют два множества B и C в U, каждое из которых удовлетворяет требованиям дополнения множества A:

a) B Ç A =Æ; б) С Ç A =Æ;

в) B È A = U; г) С È A = U.

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

Тогда по доказанному выше:

B =(B Ç C)È(B Ç A), но с учетом условия а) B =(B Ç C)ÈÆ= B Ç C, т.е. B = B Ç C. Поэтому a Î B Þ a Î B и a Î С Þ B Í(B Ç C) Þ B Í B и B Í С.

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

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

C = C Ç U = C Ç(B È A)=(C Ç B)È(C Ç A)=(C Ç B)ÈÆ= C Ç B.

Поэтому

а Î С Þ а Î С и a Î B Þ C Í(C Ç B) Þ C Í C и C Í B.

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

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

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

= B È C, = A È C, = A È C.

Докажем, что = B È C.

По условию, A, B, C попарно не пересекаются, т.е.

а) A Ç B =Æ; б) A Ç C =Æ; в) B Ç C =Æ,

кроме того,

г) A È B È C = U, т.е. A È(B È C)= U.

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

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

A Ç(B È C)=Æ; A È(B È C)= U.

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

Аналогично доказывается = A È C и = A È C.

Пример 4. Доказать, что для произвольных множеств A и B имеет место соотношение A Í B Û Í .

Отметим вначале, что если а Ï , то а Î A, и проведем доказательство от противного, т.е. допустим, что A Í B и . Тогда

1. A Í B Þ если а Î A, то а Î B.

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

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

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

а Î A и a Î Þ a Î B и a Î Þ a Î(B Ç )=Æ (противоречие).

Следовательно, предположение ложно и поэтому Í , т.е. A Í B Þ .

Аналогично можно показать, что Í Þ A Í B и, значит, A Í B Û Û Í , что и требовалось доказать.

Вопросы для самопроверки и упражнения:

1. Пусть даны множества A, B, C, причем С Í B. Доказать, что

а) A Ç C Í A Ç B; б) A È C Í A È B; в) A \ B Í A \ C;

г) C \ A Í B \ A; д) \ A Í \ A.

2. Доказать эквивалентность приведенных ниже утверждений, т.е. что из каждого следует другое:

A È B = U; Í B; Ç =Æ.