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

Докажем это равенство индукцией по n:

База индукции:

Шаг индукции: Пусть утверждение для   верно:

Тогда надо доказать утверждение для  :

Начнём доказательство:

Извлечём из первой суммы слагаемое при 

Извлечём из второй суммы слагаемое при 

Теперь сложим преобразованные суммы:

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

Тема 2. Алгебра множеств

6. Понятия множества, подмножества, равенства множеств. Способы задания множеств. Операции над множествами. Соотношения между операциями. Способы доказательства соотношений между операциями.

Под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M).

Множество может быть замкнутым и незамкнутым, полным и пустым, упорядоченным и неупорядоченным, счётным и несчётным, конечным и бесконечным. Более того, как в наивной, так и в формальной теориях множеств любой объект обычно считается множеством.

Множество   является подмножеством множества  , если любой элемент, принадлежащий  , также принадлежит  .

Два множества   и   могут вступать друг с другом в различные отношения.

•  включено в  , если каждый элемент множества   принадлежит также и множеству  :

•  включает  , если   включено в  :

•  равно  , если   и   включены друг в друга:

•  строго включено в  , если   включено в  , но не равно ему:

•  строго включает  , если   строго включено в  :

•  и   не пересекаются, если у них нет общих элементов:

 и   не пересекаются 

•  и   находятся в общем положении, если существует элемент, принадлежащий исключительно множеству  , элемент, принадлежащий исключительно множеству  , а также элемент, принадлежащий обоим множествам:

 и   находятся в общем положении   

Сравнение множеств

Множество   содержится во множестве   (множество   включает множество  ), если каждый элемент   есть элемент  :

В этом случае   называется подмножеством  ,   — надмножеством  . Если   и  , то   называется собственным подмножеством  . Заметим, что  . По определению  .

Два множества называются равными, если они являются подмножествами друг друга:

Иногда для того, чтобы подчеркнуть, что множества могут быть равны, используется запись:

Операции над множествами Бинарные операции

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

• пересечение:

• объединение:

Если множества   и   не пересекаются,то  . Их объединение обозначают также:  .

• разность (дополнение):

• симметрическая разность:

• Декартово или прямое произведение:

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

Унарные операции

• Абсолютное дополнение:

Операция дополнения подразумевает некоторый универсум (универсальное множество  , которое содержит  ):

Относительным же дополнением называется А\В (см.выше):

• Мощность множества:

Результатом является кардинальное число (для конечных множеств — натуральное).

• Множество всех подмножеств (булеан):

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

7. Булева алгебра всех подмножеств некоторого множества. Аксиомы булевой алгебры. Примеры алгебраического доказательства некоторых соотношений между операциями теории множеств из аксиом.

Аксиома коммутативности: x + y = y + x.

Аксиома ассоциативности: (x + y) + z = x + (y + z).

Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

ассоциативность

коммутативность

законы поглощения

дистрибутивность

дополнительность

8. Теоретико-множественные средства моделирования. Понятие произведения множеств A x B. Теорема о числе элементов в A x B для конечных множеств A и B с доказательством методом полной математической индукции.

Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово произведение множеств.

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

Декартовым (прямым) произведением множеств   называется множество упорядоченных n-ок (наборов, кортежей) вида

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

Замечание. Если все множества   одинаковы, то используют обозначение

.

9. Понятие множества всех подмножеств P(M) множества M. Число элементов в P(M) для конечного множества M (с доказательством).

10. Понятие отношения и его теоретико-множественная модель. Определение свойств бинарных отношений: симметричность, рефлексивность, транзитивность. Примеры отношений. Определение отношения порядка. Примеры отношений порядка: больше или равно на числах, быть подмножеством на множествах, лексикографический порядок на словах.