Лекции по "Алгебре"

Г = {(Гагарин, 1934);(Дунаевский, 1900);(Носов,1908)}

(Рахманинов, 1973) – естественно не вошел в множество

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

Г’ = {(Гагарин, 1968);(Дунаевский,1955);(Носов,1986),(Рахманинов,1943)}

Определение: Множество DR, такое что,

                            DR, = {a  A :  b  B (a,b)  R}

называется областью определения соответствия R.

Определение: Множество DR, такое что,

                            BR, = { b  B: (a,b)  R}

называется областью значений соответствия R, или образом.

Таким образом, соответствие можно задать ООС, ОЗС и законом, определяющим соответствие.

Определение: Если каждому элементу множества Х ставится в соответствие один или более элемент множества У, то говорят что задано отображение Х на У.

В ранее приведенном примере соответствие человек - год рождения – не является отображением (т.к. не каждому элементу множества Х ставится в соответствие элемент из множества У) , а соответствие (человек, год смерти) – является отображением.

Определение: Функцией называется однозначное отображение Х на У. Т.е. такое отображение f, что если

(х1,y1)   f  и (х2,y2)   f  из х1 = х2 следует y1 = y2

При этом множества Х и У могут совпадать.

Определение: Если область определения отображения и область значения отображения совпадают, то отображение называется отношением.

Отметим некоторые возможные свойства отношений:

1.        Рефлексивность. хГх – истинно

2.        Антирефлексивность. хГх – ложно

3.        Симметричность. хГу   уГх

4.        Антисимметричность. хГу и уГх  у=х

5.        Несимметричность. хГу истинно, то  уГх  - ложно

6.        Транзитивность. хГу и уГz  хГz

Пример: Алфавит русского языка, как и любого другого языка – это упорядоченное множество букв. Назовем отношение между элементами этого множества отношением предшествования и обозначим его значком <.

Мы знаем, что а<б, б<в. И т.д.

Укажем свойства этого отношения:

1.        f<f – ложно, т.к. ни одна из букв не предшествует сама себе. Т.е. отношение предшествования антирефлексивно.

2.        Если f<s – истинно, то s<f – ложно. Т.е. отношение предшествования несимметрично.

3.        Если f<s и s<t, то f<t Отношение транзитивно

Т.о. отношение предшествования, которое мы ввели на множестве букв русского языка антирефлексивно, несимметрично и транзитивно.

Пример: Можно ввести на множестве из предыдущего примера отношение "непосредственно предшествует", основываясь на уже существующем и исследованном нами отношении "предшествует".

Будем говорить, что х непосредственно предшествует у, если x<y и  z: x<z и z<y.

Упражнение: Определите свойства этого отношения самостоятельно.

Тема 2.7 Типы отношений.

Теперь опишем несколько часто употребляемых типов отношений.

Отношение эквивалентности:

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

Примером отношения эквивалентности могут быть:

              Отношение "быть синонимом" на множестве слов русского языка;

              Отношение "иметь одинаковый остаток при делении на 3" на множестве целых чисел;

              Отношение "быть параллельной" на множестве прямых одной плоскости.

              Отношение "быть братом" на множестве людей.

Определение: Отношение эквивалентности – это бинарное отношение на множестве Х, удовлетворяющее следующим условиям:

1.        ХХ – рефлексивность

2.        ХУ  УХ – симметричность

3.        ХУ и УZ  ХZ  транзитивность

Т.е. отношение эквивалентности удовлетворяет следующим условиям: каждый элемент эквивалентен сам себе, не важен порядок, в котором рассматриваются эквивалентные элементы, и если два элементы эквивалентны третьему, то они эквивалентны между собой.

Упражнение: Покажите, что все примеры отношения эквивалентности обладают перечисленными свойствами.

Отношение строгого порядка:

Часто приходится сталкиваться с отношениями, определяющими некоторый порядок расположения элементов множества.

Примеры отношения строгого порядка:

отношения "быть больше", "быть меньше"   на множестве действительных чисел;

отношение строгого включения на множестве подмножеств данного множества.

Отношение "быть предком" на множестве людей.

Определение: Отношение строгого порядка – это бинарное отношение на множестве Х, удовлетворяющее следующим условиям:

1.        Х<Х – антирефлексивность

2.        Х<У и У<Х – несимметричность

3.        Х<У и У<Z  Х<Z - транзитивность

Отношение нестрогого порядка:

Примеры отношения строгого порядка:

отношение  на множестве действительных чисел;

отношение  на множестве подмножеств данного множества.

Определение: Отношение нестрогого порядка – это бинарное отношение на множестве Х, удовлетворяющее следующим условиям:

1.        ХХ – рефлексивность

2.        ХУ и УХХ=У – антисимметричность

3.        ХУ и УZ  ХZ – транзитивность

4.         

Тема 2.8 Верхняя и нижняя границы множества. Разбиение множества на классы эквивалентности

Эти понятия введены на любом подмножестве действительных чисел.

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

х              х ,  - называется верхней границей множества Х

Определение: Точной верхней гранью множества называется наименьшая из верхних граней множества и обозначается sup(X).

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

х              х ,  - называется верхней границей множества Х.

Определение: Точной нижней гранью, называется наибольшая из нижних граней множества и обозначается inf(X).

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

Пример: Система курсов данного факультета, система групп данного курса.

Пример: Если N – множество натуральных чисел, А – множество четных чисел, В – множество нечетных чисел, то {А,В} – будет разбиением множества N. Это же множество может быть разбито по остатку от деления на 3.

Чтобы дать формальное определение разбиения множества рассмотрим некоторое множества М и систему множеств ММ = {1…n}

Определение: Система ММ называется разбиением множества М, если она удовлетворяет следующим условиям:

1.        любое множество из ММ является подмножеством М

2.        Любые два множества из ММ являются непересекающимися

3.        Объединение всех множеств из ММ дает М.

Это понятие тесно связанно с отношением эквивалентности. Если рассматривать М как множество, на котором введено отношение эквивалентности, то подмножество элементов, эквивалентных некоторому элементу из М называется классом эквивалентности. Если рассматривать на множестве студентов отношение «быть в одной группе», то группа, в которой учится студент Иванов, будет классом эквивалентности, эквивалентным студенту Иванову.

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