ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ - Александр Соловьев

1. РЕФЛЕКСИВНОСТЬ. Это когда отношение обращено на себя. Ранее уже рассматривалось отношение включения. Поскольку любое множество включено само в себя, то отношение включения обладает свойством рефлексивности. Если верить народной мудрости, то и отношение «спасения» на множестве утопающих – рефлексивно.

2. АНИТИРЕФЛЕКСИВНОСТЬ. Это когда отношение к самому об'екту (всегда) неприменимо. Например, «перпендикулярность» на множестве прямых. Прямая не может быть перпендикулярна самой себе.

3. СИММЕТРИЧНОСТЬ. Если Иванов «учится в одной группе» с Петровым, то и обратное справедливо. Если прямая А «перпендикулярна» прямой B, то и обратное справедливо.

4. АНТИСИММЕТРИЧНОСТЬ. Если тысячу рублей можно «разменять» сотнями, то обратное не под силу даже фокуснику. Мрачноватый, но очень точный пример: «носить траур по кому-то»…

5. ПОЛНОТА. Это самое сложное свойство, поскольку, в отличие от всех остальных, оно прежде всего «направлено» на само множество. Полнотой обладает отношение, которое для любой пары разных элементов данного множества выполнимо хотя бы «в одну сторону». Например, полнотой обладает отношение «больше» для множества действительных чисел, ибо для двух разных действительных чисел одно обязательно больше другого. Но если мы к действительным числам добавим комплексные, то свойство полноты исчезнет. Если хотя бы одно из сравниваемых чисел будет комплексным, сравнение на «больше»-"меньше" теряет смысл.

6. ТРАНЗИТИВНОСТЬ. Если Иванов «учится в одной группе» с Петровым, а Петров с Сидоровым, то Иванов «учится в одной группе» с Сидоровым. Отношение включения тоже транзитивно. Если группа «включена» в множество студентов университета, а это множество «включено» в множество студентов страны. То множество студентов группы «включено» в множество студентов страны. Можно продолжить эту цепочку включений, прихватив галактику. И вот тут опять подводный камень казуистики!

Если студенческую группу рассматривать как элемент университета – множества, состоящего из групп, а университет элемент высшей школы – множества, состоящего из университетов, то группа не является элементом высшей школы (там элементы университеты). То есть отношение «принадлежности» нетранзитивно. «Вассал моего вассала -…»

Вернемся к функциональному соответствию (то есть к функции). Если это соответствие к тому же еще и всюду-определено, то оно называется ОТОБРАЖЕНИЕМ.

Если отобразить множество студентов в группе, на множество фамилий в группе, То это скорее всего будет ОТОБРАЖЕНИЕ множества студентов НА множество фамилий. То есть сюр'ективное соответствие. Если же отобразить множество студентов группы на множество фамилий студентов университета, то говорят, что имеет место ОТОБРАЖЕНИЕ множества студентов В множество фамилий. То есть в области значений будут и «незадействованные фамилии».

Мы подошли к одному из самых фундаментальных, может потому и неблагозвучных, понятий и теории множеств, и математики вообще, мы подошли к ГОМОМОРФИЗМУ.

Пример. Отобразим множество точек участка земной поверхности на множество точек карты. Сейчас оставим в стороне то, что некое множество точек земной поверхности отобразится в одну точку на карте, в таких случаях неин'ективность – обычное дело. Для нас существенно то что, чем выше точки земной поверхности над уровнем моря, тем в более коричневые точки карты они отображаются.

Таким образом, мы рассматриваем не просто множества элементов. В первом случае здесь между элементами множества существует отношение «выше», а во втором – «коричневее». Где выше в первом – там коричневее во втором. «Выше» и «коричневее» – это отношения заданные на своих множествах.

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

Такое отображение называется ГОМОМОРФНЫМ. Или говорят, что между этими множествами существует ГОМОМОРФИЗМ.

Вернемся к тому, что слово не очень благозвучное, а по американским меркам и громоздкое. Поэтому последнее время все чаше используется более короткий (усеченный) термин – МОРФИЗМ.

Морфизмы играют в математике исключительную роль. Коль скоро математику не без оснований часто отождествляют с математическим моделированием, то приведем афоризм из одной умной философской книжки: ХОРОШАЯ МОДЕЛЬ ВСЕГДА ГОМОМОРФНА.

Афоризм в конце лекции провоцирует размышления. Чего бы и хотелось добиться…

Лекция 5. ОСОБЫЕ ОТНОШЕНИЯ

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

Прежде всего к таковым относятся отношения ЭКВИВАЛЕНТНОСТИ. Это отношения, которые одновременно обладают свойствами рефлексивности, симметричности и транзитивности. Отношение «равенства» чисел – самый простой пример эквивалентности. Или «учиться в одной студенческой группе».

Интересно, что каждый об'ект эквивалентен сам себе хотя бы потому, что для самого невероятного об'екта, который ни на что не похож, по отношении к самому себе выполняются рефлексивность, симметричность и транзитивность. Обычно же об'екты не столь уникальны и имеют место множества (любят говорить КЛАССЫ) эквивалентных между собой об'ектов.

Самое важное свойство отношения эквивалентности (то есть свойство отношения, которое само определено с помощью трех вышеупомянутых свойств) покажем на примере. Если взять первозданный хаос, то есть все множество студентов университета, которые болтаются по коридорам, сидят в буфете или в аудиториях, а еще лучше дома или вообще неизвестно где, то отношение «учиться в одной группе» РАЗБИВАЕТ это множество на подмножества-группы. Каждый студент принадлежит какой-то группе и не может принадлежать сразу двум. (В реальной жизни возможны исключения из этих очевидных свойств, но мы по умолчанию рассматриваем лишь нормальных студентов).

В качестве лабораторной работы по разбиению рекомендуется разбить тарелку. Желательно, из китайского фарфора. А потом созерцать осколки, каждый из которых будет для фарфоринок классом эквивалентности применительно к отношению «принадлежать одному и тому же осколку»… Это лучше, чем разбивать группы, тем более, что ортодоксальные алгебраисты под «группой» понимают не кучу студентов, а нечто фундаментальное математическое… Но это уже начало другой романтической истории про молоденького французского гения и (увы) дуэлянта – Эвариста Галуа.

Заметную роль в математике играют и отношения ПОРЯДКА, обладающие свойствами транзитивности и антисимметричности. Нарушение любого из них нарушает порядок не только с точки зрения математики, но и здравого смысла.

Примеры. «Быть больше» на множестве чисел, «быть после» в очереди, «быть старше по званию» в армии.

Дополнительно, если порядки обладают свойством полноты, то их называют СОВЕРШЕННЫМИ. Например, «больше», на множестве действительных чисел.

Если отношение еще и рефлексивно, то порядок называют НЕСТРОГИМ (ЧАСТИЧНЫМ). Например, «выть выше или равного роста». А предыдущие три примера – это отношения СТРОГОГО (ЛИНЕЙНОГО) порядка, поскольку в них имеет место антирефлексивность.

Отрадно то, что теоретико-множественные отношения порядка как правило совпадают с житейским представлением об упорядочении. Но не всегда. Знаменитое отношение «быть братом» с одной стороны очень похоже на отношение порядка. Иван брат Марьи, но Марья не брат Петра – вроде(!) антирефлексивность. Если Иван брат Петра, а Петр брат Марьи, то Иван брат Марьи. Вроде бы(!) транзитивность. Но, если Иван брат Петра, то и Петр брать Ивана – то есть с анитисимметричностью все-таки не получается. Хуже того, если Иван брат Петра, а Петр брать Ивана, то по свойству транзитивности придем к заключению, что Иван брат Ивана. А чтобы не возникал такой абсурдный результат, отношение «быть братом» признается нетранзитивным.

Более интересными являются другие отношения, очень похожие на отношения порядка. Например, «быть немного выше ростом». Это антисимметричное, но нетранзитивное отношение. Иван немного выше ростом Петра, Петро немного выше ростом Егора. Но Иван намного выше ростом Егора. Отношения, похожие на отношения порядка, но не обладающие свойством транзитивности, называют отношениями ТОЛЕРАНТНОСТИ. Хорошей иллюстрацией этого отношения служат многие известные картинки Эшера, где, например, ящерицы «плавно» превращаются в птиц и т.п.