Лекция: Теоретические обоснования

Вернемся к свойствам (1) – (19) операций над множествами. Все они представляют собой утверждения о равенстве двух множеств. Стандартный способ доказательства равенства двух множеств состоит в доказательстве двух включений: и .

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

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

.

1) Пусть — произвольный элемент из. Тогда по определению операции имеем и. Во втором случае из определения операции выводим, что или. Если, то с учетом того, что, получаем. Если, то с учетом того, что, получаем. Таким образом, или. Следовательно, по определению операции имеем. Тем самым установлено, что .

2) Пусть — произвольный элемент из. Тогда по определению операции имеем или. В первом случае из определения операции выводим, что и. Во втором случае — и. Таким образом, или, значит,. Кроме того, в обоих случаях. Следовательно, согласно определению операции, имеем. Тем самым установлено, что .

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

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

Теорема 1.1 (о свойствах классов эквивалентности).Пусть — отношение эквивалентности на множестве. Тогда

1. ;

2. ;

3. .

Доказательство. 1. — отношение эквивалентности, следовательно, является рефлексивным, т.е. выполняется. Но тогда и, значит, .

2. Пусть, т.е.. Тогда и, откуда и, и, следовательно, в силу симметричности и, и, наконец, поскольку транзитивно, получим .

Возьмем любой элемент множества, тогда. Так как и, то в силу транзитивности, т.е.. Таким образом, .

Аналогично получим. Следовательно, .

3. Докажите это утверждение самостоятельно. ■