lekcii_dm

или два утверждения: “элемент А” и “элемент В”, а А В означает, что эти же два утверждения связываются исключающим или, то есть х А В х либо только А, либо только В.

Множество А В можно было бы назвать “суммой по модулю два” множеств А и В, то есть берётся объединение этих двух множеств, но элементы, которые при этом встречаются дважды, выбрасываются.

Определение.

Пусть S и А – множества, при этом A S. Запас подмножеств S \ А называется дополнением множества А и обозначается СА или A ( A ).

1.03.Принцип двойственности в теории множеств.

1.Дополнение суммы равно пересечению дополнений:

2.Дополнение пересечений равно сумме дополнений:

Докажем, например, соотношение 1.

Пусть x S \ A . Это означает, что x A , то есть х A для

х S \ A для x (S \ A ).

Обратно, пусть х (S \ A ), то есть х S \ A , х A для

x A x S \ A .

Таким образом, равенство 1 доказано.

1.04. Отображения множеств.

Определение.

11

Пусть M и N – два произвольных множества. Если каждому элементу х M поставлен в соответствие один и только один элемент y N, то говорят, что на M определена функция ƒ, принимающая значения из N, то есть ƒ: M N.

Рис. ƒ: M N.

Замечания.

Для множеств произвольной природы часто вместо термина “функция” используется термин “отображение”.

При специализации природы множеств M и N возникают специальные типы функций, которые носят особые названия: “вектор-функция”, “мера”, “функционал”, “оператор” и т.д.

Определение.

Пусть а M, ƒ: M N. Тогда элемент b = ƒ(а) N называется образом элемента а при отображении ƒ.

Определение.

Совокупность всех тех элементов а из M, образом которых при отображении ƒ является данный элемент b N, называется прообразом (полным прообразом) элемента b и обозначается ƒ–1(b).

Определение.

Пусть А, M, N – множества; ƒ: M N; А M. Тогда совокупность {ƒ(a) | a A} всех элементов вида ƒ(а), где а А, называется образом А и обозначается ƒ(А).

12

Определение.

Пусть

M, N, B – множества, B N,

ƒ: M N.

Тогда совокупность {ƒ–1(b) | b B} всех тех элементов из М, образы которых принадлежат В называется (полным) прообразом ƒ–1(В) множества В при отображении ƒ.

Замечание.

Может оказаться, что ни один элемент b B не имеет непустого прообраза, тогда и прообраз ƒ–1(В) будет пустым множеством .

Определение.

Отображение ƒ: М N есть отображение “на” множество N или сюръекция, если ƒ(М) = N.

Определение.

Отображение ƒ: М N есть отображение множества М “в” множество N, если ƒ(М) N.

Определение.

Пусть ƒ: М N – отображение множества М “в” множество N, то есть

ƒ(М) N.

Если при х1 х2, где х1 М, х2 М, образы y1 = ƒ(х1) и y2 = ƒ(х2) различны, то есть y1 y2, то ƒ называется инъекцией.

Определение.

Отображение ƒ: М N, которое одновременно является и сюръекцией и инъекцией, называется биекцией или взаимно однозначным соответствием между M и N.

13

Теорема.

Прообраз суммы двух множеств равен сумме их прообразов, то есть f 1(A B) ƒ–1(А) ƒ–1(В).

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

Пусть х ƒ–1(A B ). Это означает, что ƒ(х) A B , то есть ƒ(х) А или ƒ(х) В х принадлежит по крайней мере одному из множеств ƒ–1(А)

или ƒ–1(В), то есть х ƒ–1(А) ƒ–1(В).

Обратно, пусть х ƒ–1(А) ƒ–1(В), тогда х принадлежит по крайней мере одному из множеств ƒ–1(А) или ƒ–1(В), то есть ƒ(х) принадлежит хотя бы

Теорема.

Прообраз пересечения двух множеств равен пересечению их прообразов, то есть ƒ–1(A B) ƒ–1(А) ƒ–1(В).

ƒ(A B) ƒ(А) ƒ(В).

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

14

Пусть y ƒ(А В). Это означает, что y = ƒ(х), где х принадлежит по

х А В y = ƒ(х) ƒ(А В), что и требовалось доказать.

Замечания.

1.Последние три теоремы остаются в силе для сумм и пересечений любого (конечного или бесконечного) числа множеств.

2.Образ пересечения двух множеств, вообще говоря, не совпадает с пересечением их образов.

Например, пусть задано отображение, проектирующее плоскость на ось х. Тогда отрезки

0 x 1, y 0;

0 x 1, y 1.

не пересекаются, а в то же время их образы совпадают.

1.05. Разбиение на классы. Отношения эквивалентности.

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

Например,

1.плоскость, рассматриваемую как множество точек, можно разбить на прямые, параллельные оси х;

2.трехмерное пространство можно представить как объединение концентрических сфер различных радиусов, начиная с r = 0;

3.жителей данного города можно разбить на группы по их году рождения

ит.п.

Определение.

15

Каждый раз, когда некоторое множество М представлено тем или иным способом как сумма попарно непересекающихся подмножеств, говорят о разбиении множества М на классы.

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

Ещё примеры:

множество всех треугольников можно разбить на а) классы равных между собой треугольников; б) классы равновеликих треугольников и т.д.

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

Признаки могут быть самыми разнообразными, но их выбор не произволен.

Определение.

Бинарное отношение над множеством М – это подмножество множества М М всех упорядоченных пар из М.

Определение.

Бинарным отношением между двумя множествами называется соответствие элементов одного из них элементам другого.

Замечание.

Вместо принадлежности пары (х, y) бинарному отношению , то есть вместо (х, y) часто используют инфиксную запись, то есть х y.

Определение.

Бинарное отношение над М называется рефлексивным, если для всех х М имеем: (х, х) или, другими словами,

х х для х М. (=,≤,≥, )

Определение.

16

Отношение над М называется антирефлексивным, если x x не выполняется ни для какого x X. (≠,<,>, )

Определение.

Бинарное отношение над М называется транзитивным, если из (х, y) и (y, z) (x, z) или, в инфексной записи:

если х y и y z, то х z. (=,≤,≥, ,<,>, ), не транз. (≠)

Определение.

Для каждого бинарного отношения над М определено обращение Т (обратное отношение), а именно:

(х, y) Т (y, x) .

Определение.

Бинарное отношение над М называется симметричным, если Т = , или, в инфиксной записи: если х y, то y x. (=,≠)

Определение.

Отношение над М называется антисимметричным, если для любых x,y X из x y и y x x=y. (≤,≥, )

Определение.

Отношение над М называется строго антисимметричным, если для любых x,y X из <x,y> <y,x> . (<,>, )

Определение.

Бинарное отношение называется отношением эквивалентности, если

оно:

1.рефлексивно;

2.транзитивно;

3.симметрично.

17

Теорема.

Для того, чтобы бинарное отношение позволяло разбить множество М на классы необходимо и достаточно, чтобы было эквивалентным.

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

Докажем необходимость утверждения.

Пусть имеется множество М и его разбиение на классы, то есть пусть а и b находятся в одном классе и связаны отношением . Легко видеть, что в классе Ка выполняется:

а а;

если а b и b c, то а с; если а b (а это так), то b a,

то есть отношение является эквивалентным.

Докажем достаточность.

Пусть 1. — отношение эквивалентности между элементами множества М;

18

Для х Ка по определению имеем

принадлежит и Ка. Таким образом, два класса Ка и Кb, имеющих хотя бы один общий элемент, совпадают между собой. Итак, получено разбиение множества М на классы по заданному отношению эквивалентности, что и требовалось доказать.

Замечание.

Понятие разбиения множества на классы тесно связано с понятием отображения, а именно:

Пусть ƒ – отображение множества А в множество В, то есть ƒ: A b B . Множество элементов А, образы которых в В совпадают, образуют класс элементов, то есть возникает некоторое разбиение множества А.

Пусть В – совокупность тех классов, на которые разбито множество А. Ставя в соответствие каждому элементу а А тот класс ( то есть элемент из В), к которому а принадлежит, то есть g: a Ка, получаем отображение А на множество В.

Примеры.

1.Пусть ƒ – проекция плоскости хy на ось х. Прообразы точек оси х – вертикальные прямые. Следовательно, этому отображению отвечает разбиение плоскости на параллельные прямые.

2.Разобьём все точки трехмерного пространства на классы, объединив в один класс точки, равноудаленные от начала координат. Каждый класс представляет собой сферу некоторого радиуса. Совокупность всех этих классов можно отождествить с множеством всех точек, лежащих на луче

[0, ), то есть разбиению трёхмерного пространства на концентрические

19

cos ) r(трёхмерный случай).

3. Объединим в один класс все действительные числа с одинаковой дробной частью. Этому разбиению отвечает отображение прямой линии на отрезок [0, 1): ƒ: d.k 0.k.

1.06. Упорядоченные множества. Изоморфизм теории множеств.

Определение.

Пусть М – произвольное множество, – бинарное отношение, определяемое некоторым множеством M M . Это отношение называется частичной упорядоченностью, если оно удовлетворяет условиям:

1.рефлексивности: а а;

2.транзитивности: из а b &b c a c ;

3.антисимметричности: из а b &b a a b. Частичную упорядоченность обозначают символом .

Определение.

Множество, в котором задана некоторая частичная упорядоченность, называется частично упорядоченным.

Примеры.

Всякое множество можно тривиальным образом рассматривать как частично упорядоченное, если положить a b a b , то есть за частичную упорядоченность всегда можно принять отношение тождества .

20