14

1. Множества. Отношение принадлежности. Способы задания множеств. Отношения включения и равенств множеств. Подмножество, надмножество, собственное подмножество. Универсум. Пустое множество. Мощность множества. Булеан множества. Семейство множеств.

«Произвольная совокуп. определенных предметов нашей интуиции или интеллекта, кот. можно отличить один от другого и кот. представ. как единое целое, называется множеством. Предметы, кот. входят в состав множества, называются его эл-тами».

• Через обозначается отношение принадлежности, т.е. означает, что элемент принадлежит множеству .

• Если не является элементом множества A, то это записывается .

• Два множества A и B считаются равными, если они состоят из одних и тех же элементов. Пишется , если A и B равны, и в противном случае.

• Через Í обозначается отношение включения множеств, т.е. означает, что каждый элемент множества A является элементом множества B. В этом случае A называется подмножеством B, а B — надмножеством A. Если и , то A называется собственным подмножеством B, и в этом случае пишем .

• Мощностью (кардинальным числом) множества называется количество элементов в нем.

• Множество, не содерж. эл-тов (мощностью 0), наз. пустым и обознач. Æ.

• Общее множество для нескольких других наз. универсумом (универсальным множеством), обознач. .

• Фиксируем множество . Мы рассматриваем подмножества (содержащиеся в ). Семейство всех подмножеств обозначаем через . Семейство — множество, все эл-ты кот. сами являются множествами (множество из множеств).

Теорема. Если мощность конеч. множества А равна , то число всех подмножеств А равно , т. е. .

Множество всех подмножеств множества М называется булеаном и обозначается . Для конечных множеств выполняется .

Способы задания множеств:

• Перечисление элементов (только конеч. множества);

• Порождающая процедура (индуктивная, рекурсивная, комбинация из них);

• Описание хар-ристических св-в или хар-ристическим предикатом.

2. Простое и необычное множество. Парадоксы и Антиномии. Парадокс Рассела и его роль в математике. Способы избежать Парадокса Рассела. Логические антиномии.

Антиномия — противоречие между 2-мя высказываниями, признаваемых одинаково верными.

Парадокс Рассела. Рассмотрим все множества, не содержащие самих себя. Рассмотрим множество всех таких множеств. Тогда если оно не содержит себя, то оно содержит себя.

Задание множеств хар-ристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: . Если такое множество существует, то можно ответить на следующий вопрос: принадлежит ли оно само себе. С одной стороны, если , то . С другой стороны, если , то .

Это противоречие можно разрешить различ. способами, в целом сводящимся к тому, что не явл. множ.

Для 3-x множеств А, В, С справедливы следующие соотнош.: ; ; ; .

Связь между включением и равенством множеств устанавливается следующим соотнош.: множества равны когда они являются подмножествами друг друга. .

3. Операции над множествами и законы алгебры множеств. Диаграммы Эйлера. Формула включений и исключений. Покрытия и разбиения. Классы разбиения.

• Объединением (дизъюнкцией) 2-х множеств наз. множ. .

• Пересечением (конъюнкцией) 2-х множеств наз. множ. .

• Разностью 2-х множеств наз. множ.

• Дополнением множества A наз. разность и обознач. через .

• Симметрической разностью 2-х множеств наз. множ., элементы которого принадлежат только 1 из множеств: .

Диаграмма Эйлера–Вэйна — геометрич. изображ. множеств на плоскости в виде областей.

• Покрытие множества A — такая совокуп. множеств , которая представляет собой объединение подмножеств .

• Разбиение множества A — такая совокуп. , что совокуп. подмножеств покрытия A , при . Подмножества — классы разбиения.

Законы алгебры множеств:

1. Ассоц.: ; .

2. Коммут.: ; .

3. Иденп.: ; .

4. Дист. относ. слева и справа: ; .

5. Дист. относ. слева и справа: ; .

6. Св-ва дополнения: ; .

7. З-ны де Моргана: ; .

8. Св-ва универсума: ; .

9. З-ны пустого множества: ; .

10. Инволютивность: .

Формула включений и исключений:

.

4. Упорядоченная пара, кортеж, декартово произведение множеств. Прямое произведение n множеств, степень множества. Двуместное и n-местное соответствие. Способы задания соответствий. Пустое и полное соответствие.

Упорядоч. пара — запись вида (a, b), где , .

Кортеж — запись , где , …, .

Декартово (прямое) произведение 2 множеств — множ. всех упорядоч. пар эл-тов этих множеств:

.

#: , , .

Декартово произведение n множеств — множество кортежей, образованное элементами этих множеств. — множ. .

Если , то .

Соответствие — бинарное отнош. между множествами — произвольное подмнож. R из декартова произведения этих множеств. n множеств — n-местное соответствие.

Если , и , то пишут также или . Если , то соответствие называется пустым, а если , то соответствие называется полным.

Способы задания соответствий:

• множеством картежей;

• матрицей;

• сечением (фактор–множеством);

• диаграммой.

• Задание соответствия множеством картежей.

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

#: Пусть .

. Мощность: .

• Матричное задание соответствий.

#: , .

	y1	y2
x1	1	1
x2	0	0
x3	1	0

• Задание соответствия сечением.

Множ. всех сечений эл-тов множ. наз. фактор-множ.

#: Пусть .

.

• Диаграммное задание соответствий.

Обычно для соотв-вий диаграммным представлением явл. двудольный граф (доли — множества вершин, помеч. символами эл-тов множеств), или графич. представление соотв., а для отношений — псевдограф.

5. Область определения (прообраз Dom) и область значений (образ Im) соответствия. Образ (im) и прообраз (coim) элемента. Всюду определенное, сюръективное, функциональное и инъективное соответствие. Отображения множества А в (на) множество В, биективное и взаимнооднозначное соответствие. N-арная функция.

.

Область определения (прообраз, Dom R) — множ. эл-тов , для каждого из кот. найдется хотя бы 1 эл-т такой, что .

Область значений (образ, Im R) соответствия R наз. множество элементов , для каждого из которых найдется хотя бы один элемент такой, что .

Образ относительно R ( ) — множ. эл-тов таких, что .

Прообраз относительно ( ) — множ. эл-тов таких, что .

; .

• Полностью определенное — соотв., у кот. каждый эл-т множ. А включен в соотв. ( ). В противном случае — частичное (частич. опред.).

• Сюръективное — соотв., у кот. каждый эл-т множ B включен в соотв. ( ).

• Функциональное — соотв., у кот. если элемент имеет прообраз при соотв. R, то он единственный ( ).

• Инъективное — соотв., в кот. если элемент , имеет прообраз при соотв. R, то он единственный ( ).

• Отображение (функция) из A в B ( ) — функциональное и полностью определенное соотв. Частичное отображение (частичная функция), если соотв. функц. и частич. Число n (кол-во эл-тов в отображ.) — арность отображ. соответствия.

• Отображение A на B ( ) — всюду опред., сюръектив. и функц. соотв.

• Биектив. — сюръектив. и инъектив. соотв.

• Взаимно однознач. — всюду опред., сюръектив. функц. и инъектив. соотв.