Доказательство
Докажем это равенство индукцией по 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. Понятие отношения и его теоретико-множественная модель. Определение свойств бинарных отношений: симметричность, рефлексивность, транзитивность. Примеры отношений. Определение отношения порядка. Примеры отношений порядка: больше или равно на числах, быть подмножеством на множествах, лексикографический порядок на словах.
Рефлексивное отношение
В математике бинарное отношение 
на множестве 
называется рефлексивным, если всякий элемент этого множества находится в отношении с самим собой.
Формально, отношение рефлексивно, если 
.
Свойство рефлексивности при заданных отношениях матрицей характеризуется тем, что все диагональные элементы матрицы равняются 1; при заданных отношениях графом каждый элемент имеет петлю — дугу (х, х).
Если это условие не выполнено ни для какого элемента множества , то отношение называется антирефлексивным.
Если антирефлексивное отношение задано матрицей, то все диагональные элементы являются нулевыми. При задании такого отношения графом каждая вершина не имеет петли — нет дуг вида (х, х).
Формально антирефлексивность отношения определяется как: 
.
Если условие рефлексивности выполнено не для всех элементов множества , говорят, что отношение нерефлексивно.
Примеры рефлексивных отношений
· отношения эквивалентности:
· отношение равенства 
· отношение сравнимости по модулю
· отношение параллельности прямых и плоскостей
· отношение подобия геометрических фигур;
· отношения нестрогого порядка:
· отношение нестрогого неравенства 
· отношение нестрогого подмножества 
· отношение делимости 
В математике бинарное отношение на множестве X называется симметричным, если для каждой пары элементов множества 
выполнение отношения 
влечёт выполнение отношения 
.
Формально, отношение симметрично, если 
.
Антисимметричность отношения не является антонимом симметричного отношения. Оба свойства для некоторых отношений выполняются одновременно, а для некоторых не выполняется ни одно.
Примеры
Любое отношение эквивалентности, по определению, является симметричным (а также рефлексивным и транзитивным). Также симметрично отношение связи вершин графа (неориентированного).
Не являются симметричными (за исключением случая тождественной ложности отношения) отношения порядка (как полного, так и частичного), а также отношение следования вершин ориентированного графа. Однако, отношение сравнимости для частичного порядка является, по построению, симметричным (хотя, в отличие от самого́ порядка, не транзитивным).
Матрица симметричного отношения симметрична относительно главной диагонали (совпадает с транспонированной). Если в графе симметричного отношения существует связь между двумя вершинами, то существует и обратная связь.
Транзитивность
В математике бинарное отношение на множестве называется транзитивным, если для любых трёх элементов множества 
выполнение отношений 
и 
влечёт выполнение отношения 
.
Формально, отношение транзитивно, если 
.
Примеры
· Равенство: 
и 
, значит 
(на самом деле, отношение равенства вместе с отношением эквивалентности и параллельности прямых обладает более сильным свойством также ещё и «равенства третьему» по причине своей симметричности)
· Отношение порядка: 
и 
, значит 
или нестрогого порядка: 
и 
, значит 
· Параллельность прямых: 
и 
, значит 
(см. примечание к «равенству чисел»)
· Импликация: 
и 
, значит 
· Эквивалентность: 
и 
, значит 
(см. примечание к «равенству чисел»)
· Включение подмножества: если b является подмножеством a, и в свою очередь c является подмножеством b, тогда c является подмножеством a
· Делимость: если a делится на b, и b делится на c, тогда a делится на c.
· Отношение следования вершин ориентированного графа: если вершина 
достижима из вершины 
, а вершина , в свою очередь, — из 
, то достижима из .
Примеры отсутствия транзитивности (встречаются, когда логические высказывания связаны не арифметическими отношениями или их эквивалентами в языке, а другими смысловыми отношениями):
· Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы сильнее Бумаги; однако Камень не сильнее Бумаги (
). Здесь "сильнее" не имеет буквального значения, поскольку "сила" Бумаги в том, что она просто обертывает Камень.
· В круговом турнире часто бывает ситуация, когда команда A победила команду B, команда B — команду C, а C — A. Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
· Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной 
, и две вершины 
и 
, входящие в состав различных альтернативных ветвей ветвления, то вершина связана с , связана с , однако вершины и не связаны (они либо параллельны, либо альтернативны).
· Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина , а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину , а другая — 
, то вершины и находятся в отношении параллельности, также как и вершины и , однако вершины и не параллельны (они находятся в отношении альтернативы).
· Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной , а другая включает последовательно выполняемые вершины и , то вершины и находятся в отношении альтернативы, что справедливо и для вершин и , однако вершины и не состоят в отношении альт
11. Отношение эквивалентности. Определение фактор множества по отношению эквивалентности. Примеры.
Отношение эквивалентности
У этого термина существуют и другие значения, см. Эквивалентность.
Отношение эквивалентности (
) на множестве — это бинарное отношение, для которого выполнены следующие условия:
1. Рефлексивность: 
для любого в ,
2. Симметричность: если 
, то 
,
3. Транзитивность: если и 
, то 
.
Запись вида «» читается как « эквивалентно ».
Связанные определения
· Классом эквивалентности 
элемента называется подмножество элементов, эквивалентных . Из вышеприведённого определения немедленно следует, что, если 
, то 
.
Множество всех классов эквивалентности обозначается 
.
· Для класса эквивалентности элемента используются следующие обозначения: 
, 
, 
.
· Множество классов эквивалентности по отношению является разбиением множества.
