В предыдущей статье мы рассмотрели, что вообще такое есть математические отношения и какими свойствами они могут обладать. В этой статье мы рассмотрим наиболее важные комбинации упомянутых свойств, которые делают некоторые отношения особенными. Естественно, для понимания данной статьи необходимо прочитать предыдущую.
СОДЕРЖАНИЕ:
- Отношения Эквивалентности:
- - Что такое отношение эквивалентности?
- - Классы эквивалентности
- - Применение отношений эквивалентности:
- - - Векторы
- - - Арифметика остатков
- Отношения Порядка:
- - Что такое отношение порядка?
- - Отношения квазипорядка
- - Отношения частичного порядка
- - Отношения строгого порядка
- - Линейность отношений порядка
- - Применение отношений порядка:
- - - Упорядочивание множеств
- - - Вполне-упорядоченные множества
- Графы
- Особые отношения:
- - Универсальное отношение
- - Нуль-отношение
- - Функциональные отношения
- Заключение и упражнения
ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ
ЧТО ТАКОЕ ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ?
ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ - это всякое РЕФЛЕКСИВНОЕ, СИММЕТРИЧНОЕ и ТРАНЗИТИВНОЕ отношение.
Из прошлой статьи и упражнений к ней прикреплённых мы можем вспомнить, что следующие отношения обладают всеми тремя перечисленными свойствами: равенство «=», логическая эквивалентность «⇔», параллельность прямых «||», параллельность плоскостей «||», подобие фигур «∝». Что же объединяет все эти отношения? И почему их выделяют в отдельный вид отношений?
КЛАССЫ ЭКВИВАЛЕНТНОСТИ
Итак, для начала, мы рассмотрим следующее понятие:
РАЗБИЕНИЕМ МНОЖЕСТВА A называют множества A1, A2, A3, … , An такие, что A1 ⋃ A2 ⋃ A4 ⋃ … ⋃ An = A и для любых k и m, где 1 ≤ k, m ≤ n, верно Ak ⋂ Am = ∅.
Из то есть, при разбиении множества мы получаем несколько его подмножеств таких, что у них попарно нет общих элементов, а совокупность всех элементов этих подмножеств - исходное множество. Например, если мы рассмотрим множество целых чисел от 0 до 9 включительно M, то мы, например, можем разбить его на два подмножества только с чётными и только с нечётным числами. Так будет выглядеть оригинальное множество:
А так будут выглядеть подмножества M чётных чисел E и нечётных чисел O:
Что мы можем заметить? То, что O ⋂ E = ∅, ведь нет одновременно чётного и нечётного числа, и что O ⋃ E = M. То есть, если мы разделим M на подмножества E и O, то это будет разделение. Но если мы поделим множество M на множества E = {0, 2, 4, 6, 8} и O' = {1, 5, 7, 9}, то получим такую картину:
Число 3 было как бы «выброшено» и отсутствует в обоих подмножествах. При этом, теперь мы имеем O' ⋂ E = ∅ и O' ⋃ E = M \ {3}, то есть совокупность всех элементов из O' и E не даёт нам множества M, а значит такие подмножества Ek не составляют разделения M. Если же мы поделим множество M на множества E' = {0, 2, 3, 4, 6, 8} и O = {1, 3, 5, 7, 9}, то получим уже следующую картину:
В этот раз подмножество E' как бы берёт «лишнее» 3, которое теперь присутствует в обоих подмножествах. Значит O ⋂ E' = {3} и O ⋃ E' = M. То есть, и данные подмножества не составляют «разбиение» множества M.
В конечном итоге, можно заметить, что если некоторые подмножества составляют разбиение некого исходного множества, то они же представляют некоторые обособленные «кластеры» элементов, причём каждый элемент исходного множества принадлежит только одному «кластеру». Именно это - формирование «кластеров» из исходного множества - и является главной чертой разбиения.
А теперь рассмотрим некоторые отношения эквивалентности в виде графов:
Мы можем увидеть, что все объекты при этих отношениях группируются в те самые «кластеры», причём в каждом «кластере» все элементы попарно связаны отношением. И вот мы подошли к главной особенности отношений эквивалентности - они способны формировать разбиения множеств. Сами «кластеры» формируемые отношениями эквивалентности называются классами эквивалентности. Но сначала дадим формальное определение самого класса эквивалентности:
Пусть R - отношение эквивалентности на A. КЛАССОМ ЭКВИВАЛЕНТНОСТИ, ВКЛЮЧАЮЩИМ a ∈ A называется множество [a] = {x ∈ A | xRa}.
Например, на множестве M целых чисел от 0 до 9 включительно отношение «имеет ту же чётность» формирует классы эквивалентности [1] = {1, 3, 5, 7, 9} и [2] = {0, 2, 4, 6, 8}, причём [1] ⋂ [2] = ∅ и [1] ⋃ [2] = M, то есть [1] и [2] составляют разбиение множества M. Однако это же отношение, например, формирует классы [5] = {1, 3, 5, 7, 9} и [8] = {0, 2, 4, 6, 8}. Нетрудно заметить, что [1] = [5] и [2] = [8]. Вообще говоря, [1] = [3] = [5] = [7] = [9] = {1, 3, 5, 7, 9} и [0] = [2] = [4] = [6] = [8] = {0, 2, 4, 6, 8}. Как связано это всё? Можем увидеть, что если x ∈ [y], то [x] = [y]. Но это утверждение равносильно «если xRy, то [x] = y». И уже данное утверждение будет основой для нашего доказательства, что классы эквивалентности формируют разбиение множества.
Вот так, к слову, будут выглядеть класс эквивалентности на примере отношения подобия на множестве фигур из рисунка выше:
Также следует сказать, что отношения эквивалентности часто обозначают символом «~» (тильда) и называют «эквивалентностью». То есть, если R - отношение эквивалентности, то можно вместо xRy записать x~y и cказать «x эквивалентно y». Однако, если в контексте этот символ уже используется иначе, то перегружать его не стоит.
Итак, приступим. Нам нужно доказать утверждение «[x] = [y] ⇔ x~y» или же «Классы эквивалентности, включающие некоторые два элемента множества, равны тогда и только тогда, когда верно отношение между данными элементами». Поскольку ~ симметрично, для нас не имеет значение при рассмотрении формулировки теоремы: x~y или y~x.
- Докажем «[x] = [y] → x~y». Поскольку R рефлексивно, имеем x~x. Значит x ∈ [x]. Если [x] = [y], то имеем также x ∈ [y]. Но если x ∈ [y], то верно x~y. Утверждение доказано.
- Докажем «x~y → [x] = [y]». Вспомним, что «[x] = [y] ⇔ [x] ⊆ [y] ^ [y] ⊆ [x]» и докажем всю «правую» часть данного утверждения:Докажем, что «x~y → [x] ⊆ [y]». Пусть имеется некий элемент с такой, что c ∈ [x]. Тогда верно cRx и xRy. По свойству транзитивности теперь c~y и c ∈ [y], а значит «с ∈ [x] → c ∈ [y]» и [x] ⊆ [y].
- Докажем, что «x~y → [y] ⊆ [x]». Поскольку ~ симметрично, x~y ⇔ y~x. теперь пусть c ∈ [y] и, аналогично прошлому пункту, [y] ⊆ [x].
- Зная, что «(x~y → [x] ⊆ [y]) ^ (x~y → [y] ⊆ [x])», имеем теперь «x~y → [x] = [y]». Теперь, зная, что «([x] = [y] → x~y) ^ (x~y → [x] = [y])» имеем, что доказано утверждение теоремы: «[x] = [y] ⇔ x~y».
Как всё это относится к разбиениям? Заметим, что невозможно, чтобы некий элемент не находился ни в одном классе эквивалентности, ведь отношение R рефлексивно, а значит x~x и x ∈ [x]. Это означает, что объединение всех классов эквивалентности, пусть они даже состоят из одного элемента каждый, всегда будет давать изначальное множество. Но также невозможно, чтобы некий элемент был в двух различных классах эквивалентности, ведь по доказанной выше теореме, если некие два класса эквивалентности имеют общий элемент, то это два равных (то есть один) класса эквивалентности. Но эти два факта о классах эквивалентности говорят нам, что они формируют разбиение множества.
Если R - определённое на A отношение эквивалентности, то КЛАССЫ ЭКВИВАЛЕНТНОСТИ по данному отношению ВСЕГДА формируют РАЗБИЕНИЕ множества A.
ПРИМЕНЕНИЕ ОТНОШЕНИЙ ЭКВИВАЛЕНТНОСТИ.
На самом деле, чтобы примерно понять, что объединяет все отношения эквивалентности, нам достаточно взглянуть на названия основных таких отношений: равенство «=», равноостаточность «≡ (mod m)», подобие «∝», отношение «того же цвета» из предыдущей статьи. Все эти отношения выделяет то, что они группируют элементы по «похожести» между собой.
ВЕКТОРЫ
Самый первый пример применения отношений эквивалентности, который приходит мне в голову, это определение вектора из учебника Постникова по Аналитической Геометрии. Там оно дано так:
Класс эквиполентных направленных отрезков называется ВЕКТОРОМ. В частности, НУЛЕВЫМ ВЕКТОРОМ называется класс, содержащий все вырожденные отрезки.
Но мы его заменим более человеческим определением:
Класс направленных отрезков, имеющих одно направление и длину, называется ВЕКТОРОМ. В частности, НУЛЕВЫМ ВЕКТОРОМ называется класс, содержащий все отрезки нулевой длины.
Здесь мы видим отношение R, определённое, как «xRy тогда и только тогда, когда x и y имеют одно направление и длину». Но что же может тогда различаться у этих отрезков? Может различаться их точка начала! То есть, все эти направленные отрезки
Являются одним вектором, ведь для попарно для каждого из данных отрезков верно xRy.
АРИФМЕТИКА ОСТАТКОВ
Не менее важным является отношение «равноостаточности» или, как иногда говорят, «конгруэнтности по модулю» между числами. Поскольку равноостаточность - отношение эквивалентности, данное отношение должно формировать классы эквивалентности. Но какие?
Заметим, что, например, 1 ≡ 3 ≡ 5 ≡ 7(mod 2) и 0 ≡ 2 ≡ 4 ≡ 6 (mod 2). Значит у нас имеются классы эквивалентности [0] и [1]. Не будем тянуть резину - отношения равноостаточности по модулю m формируют классы эквивалентности [k], где k - некий остаток при делении числа на m. Из таких классов эквивалентности возникает Арифметика Остатков, в которой изучается поведение остатков при перемножении или сложении элементов между ними. Так, например, при отношении равноостаточности по модулю 2, какой бы элемент [0] и какой либо элемент [1] мы не взяли, мы получим некий элемент из [1], что в привычной форме является классическим «суммой чётного и нечётного числа является нечётное число». Такие утверждения записываются, как «[0] + [1] = [1]».
Вообще говоря,
Для классов эквивалентности отношения «равноостаточно по модулю m» [a] и [b] верно [a] + [b] = [a+b] и [a] * [b] = [a*b].
Доказать это утверждение не трудно:
- Докажем, что [a] + [b] = [a+b]. Если r ∈ [a], то r = mk + a, где k - некое целое. Аналогично, если t ∈ [b], то t = ml + b. Значит r + t = mk + a + ml + b = m(k+l) + (a+b) и (r + t) ∈ [a+b].
- Докажем что [a] * [b] = [a*b]. Если r ∈ [a] и t ∈ [b], то r = mk + a и t = ml + b. Значит r * t = (mk + a) * (ml + b) = m*(mkl + k + l) + (a*b) и r * t ∈ [a*b].
Совокупность классов эквивалентностей по отношению «равноостаточно по модулю m» обозначают Z_m (то есть с индексом m). Нередко для таких систем составляют таблицы сложения и умножения, где в первой строке и столбце указаны все классы эквивалентности, а в пересечении строки [a] со столбцом [b] пишется [a+b] или [a*b], в зависимости от таблицы. Вот, например, такие для Z_7:
Конечно же, приведённые два примера - совершенно не всё, что могут предложить отношения эквивалентности! Например, целые и рациональные числа зачастую определяются с использованием классов эквивалентности, а понятие изоморфизма, краеугольное для Общей Алгебры, отражается отношением эквивалентности.
ОТНОШЕНИЯ ПОРЯДКА
ЧТО ТАКОЕ ОТНОШЕНИЕ ПОРЯДКА?
На самом деле, у отношений порядка нет такого «единства», как у отношений эквивалентности и различают аж четыре основных подвида таких отношений. Но для них есть одна общая характеристика - они позволяют установить некоторый порядок следования элементов множества, то есть, упорядочить его.
ОТНОШЕНИЯ КВАЗИПОРЯДКА
Самым «слабым» отношения порядка является отношение квазипорядка.
ОТНОШЕНИЕМ КВАЗИПОРЯДКА называется любое РЕФЛЕКСИВНОЕ ТРАНЗИТИВНОЕ бинарное отношение.
На самом деле, отношения квазипорядка не выделяются чем-то особенным вне специфического контекста. Однако, важно отметить, что отношения эквивалентности - частный симметричным случай отношений квазипорядка.
ОТНОШЕНИЯ ЧАСТИЧНОГО ПОРЯДКА
ОТНОШЕНИЕМ ЧАСТИЧНОГО ПОРЯДКА называется любое РЕФЛЕКСИВНОЕ, АНТИСИММЕТРИЧНОЕ, ТРАНЗИТИВНОЕ отношение.
Самым основным и известным примером отношения частичного порядка является отношение «больше или равно», которое, как можно заметить, действительно позволяет упорядочить, например, множество целых чисел: мы можем сказать, что -4 ≥ -3, поэтому -4 должно идти «до» -3, а само -3 должно идти «до» -2, ведь -2 ≥ -3. Также отношением частичного порядка можно назвать отношение «⊆». Что мы можем упорядочить с помощью «⊆»? Ну, например основные числовые множества: N ⊆ Z ⊆ Q ⊆ R ⊆ C.
Однако у отношений частичного порядка имеется и отличительная черта, которая является не менее полезной - их антисимметричность. То есть, если aRb и bRa, то a = b. Зная, что x ≥ 2 и 2 ≥ x, мы можем с уверенностью сказать x = 2. Или же - факт, крайне часто использующийся в Теории Множеств - если A ⊆ B и B ⊆ A, то A = B.
ОТНОШЕНИЯ СТРОГОГО ПОРЯДКА
ОТНОШЕНИЕМ СТРОГОГО ПОРЯДКА называется любое АНТИРЕФЛЕКСИВНОЕ АСИММЕТРИЧНОЕ ТРАНЗИТИВНОЕ отношение.
Зачастую, отношениями строгого порядка являются «строгие» варианты отношений частичного порядка: «больше» для «больше или равно», «собственное подмножество» для «подмножество» и так далее. Как и отношения частичного порядка, отношения строгого порядка способны упорядочивать множества: -4 > -3, -2 > -3.
Однако, как и у отношений частичного порядка, у отношений строгого порядка имеется своя отличительная черта. Мы не разобрали данное свойство отдельно в прошлой статье, однако оно важно для отношений строго порядка:
Отношение R на A обладает свойством ТРИХОТОМИИ тогда и только тогда, когда для любых x, y ∈ A верно только одно из трёх: xRy, x = y или yRx.
И отношения строгого порядка обладают этим свойством! Трихотомия отношений строго порядка довольно полезна: зная, что неверно x > 2 и x = 2, мы можем с уверенностью сказать x < 2.
ЛИНЕЙНОСТЬ ОТНОШЕНИЙ ПОРЯДКА
До сих пор в статье мы предполагали, что все отношения порядка обладают свойством связности, однако данное свойство не обязательно для них. Например, мы можем рассмотреть отношение строгого порядка без свойства связности. Оно может выглядеть вот так на множестве разных цветов:
Такая «древовидная» структура - один из возможных вариантов строгого порядка без свойства полноты. Мы явно можем сказать, что Красный > Белый и Красный > Зелёный, но при этом мы не можем сказать, что Красный > Синий или Синий > Красный. Цвета Красный и Синий или Красный и Фиолетовый, как бы, несравнимы в таком отношении.
Аналогично есть и другая структура для отношений порядка без свойства полноты:
Можем видеть здесь «кластеры», при которых вновь Красный «несравним» с Синим или Фиолетовым.
Реальные примеры отношений порядка без свойства полноты могут предоставить отношения «⊂» и «|». Так, например, на множестве {1, 2, 4, 3, 6} мы получаем такую структуру отношения «|»:
А если рассмотреть то же отношение, но на множестве {2, 4, 8, 3, 6}, то получим:
Или, например, любое генеалогическое древо, заданное на множестве родственников отношением «родитель», также будет представлять собой «древовидную» структуру.
Как мог заметить читатель, «несравнимость» элементов противоречит введённому свойству трихотомии, что верно:
Свойством ТРИХОТОМИИ обладает любое ПОЛНОЕ отношение СТРОГОГО ПОРЯДКА.
Свойство полноты для отношений порядка особенно важно, потому даже ввели термин:
ОТНОШЕНИЕ ПОРЯДКА называется ЛИНЕЙНЫМ тогда и только тогда, когда оно ПОЛНОЕ.
ПРИМЕНЕНИЕ ОТНОШЕНИЙ ПОРЯДКА
УПОРЯДОЧИВАНИЕ МНОЖЕСТВ
Почему же подобрали именно слово «линейное» для обозначения полных отношений порядка? Это потому, что свойство линейности позволяет буквально выстроить все элементы множества в «линию».
Например, не имея линейное отношение строгого порядка на множестве цветов, как в «древовидном» примере выше, мы не можем расположить в линию по «убыванию» цвета: Красный должен стоять раньше, чем Синий? Или же должен быть порядок «Фиолетовый, Красный, Синий»? Аналогичная ситуация с «кластерами».
Однако, если отношение порядка является полным, мы можем чётко определить порядок следования элементов в линии. Пусть, например, будет такое отношение на множестве цветов:
Мы можем чётко сказать: справа от Фиолетового должны быть Синий, Красный, Белый и Зелёный, а слева - ничего; справа от Красного - Белый и Зелёный, слева - Синий и Фиолетовый. И, в конечном итоге, можем составить такую расстановку в порядке по убыванию среди цветов:
Притом, как можно было заметить, можно было упорядочить некоторые подмножества цветов в «древовидной» и «кластерной» структурах. Например, в «древовидной» структуре можно упорядочить «Фиолетовый, Синий, Белый, Зелёный» или «Красный, Белый, Зелёный», в «кластерной» - «Фиолетовый, Синий» или «Красный, Белый, Зелёный».
ВПОЛНЕ-УПОРЯДОЧЕННЫЕ МНОЖЕСТВА
Одним из важнейших понятий, связанных с понятием отношений порядка, является понятие вполне-упорядоченного множества:
Множество A с отношением линейного частичного порядка «≥» является ВПОЛНЕ-УПОРЯДОЧЕННЫМ, если в любом его подмножестве M есть такой x ∈ M, что для любого y ∈ M верно y ≥ x. Иначе говоря, в M ВСЕГДА есть НАИМЕНЬШИЙ элемент.
Например, вполне упорядоченным является множество натуральных чисел N с отношением «больше или равно», причём данное свойство используется для доказательства важных фактов. Например, для алгоритма деления - утверждения о том, что любое целое число n можно уникально представить в виде n = qm + r, где m - ещё одно целое число.
ГРАФЫ
Читатель мог заметить, что отношения почему-то как ничто другое хорошо иллюстрируется графами. Почему же?
Рассмотрим граф, состоящий из множества вершин V = {a, b, c, d} и связей E = {(a, b), (b, d), (c, d), (c, a), (a, a)}. Графически отобразим этот граф для удобства.
Что же мы можем заметить? В данном случае E - множество упорядоченных пар элементов множества V. Что же это нам напоминает? Конечно же это нам напоминает структуру бинарного отношения на V! Да и E вовсе таковым и является. Например, мы можем спокойно записать aEb или aEa. Любой граф, по сути, представляет собой множество вершин V с определённым на нём бинарным отношением E, потому исследование в сфере математических отношений является исследованием, своеобразно, и в сфере графов.
ОСОБЫЕ ОТНОШЕНИЯ
Есть и несколько других отношений, достаточно занимательных для упоминания, но которые не следует подробно обсуждать в рамках статьи.
УНИВЕРСАЛЬНОЕ ОТНОШЕНИЕ
УНИВЕРСАЛЬНЫМ ОТНОШЕНИЕМ на A называется множество A².
Действительно, поскольку A² ⊆ A², универсальное отношение является бинарным отношением на A. Универсальное отношение R на A характеризуется тем, что для любых x, y ∈ A верно xRy.
Забавно отметить, что универсальное отношение на A - это единственное полное отношение эквивалентности, причём классом эквивалентности для такого отношения является само множество A.
НУЛЬ-ОТНОШЕНИЕ
НУЛЬ-ОТНОШЕНИЕМ является множество ∅.
Легко заметить, что, поскольку ∅ ⊆ A для любого A, нуль-отношение определено на любом множестве. Нуль-отношение характерно тем, что для любых x, y ∈ A неверно xRy, причём такое отношение на множестве всегда единственное. Нуль-отношение является антирефлексивным, симметричным и транзитивным отношением, причём со свойством трихотомии.
ФУНКЦИОНАЛЬНЫЕ ОТНОШЕНИЯ
Бинарное отношение R на A называют ФУНКЦИОНАЛЬНЫМ тогда и только тогда, когда xRy ^ xRz → y = z для любых x, y, z ∈ A.
Мы уже подробно обсуждали функции во второй и третьих статьях цикла по Наивной Теории Множеств. И действительно, функции от одной переменной являются частным случаем бинарных отношений. Вообще говоря, функции n-1 переменных являются частным случаем n-арных отношений:
На множестве A n-арное отношение R является ФУНКЦИОНАЛЬНЫМ, тогда и только тогда, когда R(a1, a2, … , an-1, y) ^ R(a1, a2, … , an-1, z) → y = z для любых a1, a2, … , an-1, x, y ∈ A.
Функциональные отношения, конечно, также классифицируют на инъективные, сюръективные, биективные и прочие виды, которые характерны для классификации функций.
ЗАКЛЮЧЕНИЕ
В данной статье мы рассмотрели основные виды отношений, которые выделяются в математике. Мы, однако, не рассмотрели то, как влияют действия над множествами (объединение и пересечение) на свойства отношений. Не знаю, возможно в будущем будет написана третья часть цикла, посвящённая данной теме. А пока что, думаю, это конец данного небольшого цикла.
УПРАЖНЕНИЯ:
- Докажите, что данные отношения являются отнощениями эквивалентности, рассмотрите классы эквивалентности, которые формируют эти отношения, и предположите, какие общие свойства своих элементов отображают классы эквивалентности:
- - Логическая тождественность «⇔»
- - Параллельность прямых «||»
- - Отношение «может увидеть» из прошлого упражнения исходя из следующих рисунков:
- Исследуйте отношение «похож» или «сходен» на свойства отношений и покажите, что оно не является отношением эквивалентности. Такими же свойствами будут обладать и другие отношения, такие как «дружит с» или «знаком с», в чём вы можете убедиться. Подобные отношения называют ОТНОШЕНИЯМИ ТОЛЕРАНТНОСТИ, причём отношения эквивалентности считаются их частным случаем. Зная это, укажите, какими свойствами должно обладать отношение толерантности, а какими - не должно.
- Посчитайте, сколько всего отношений эквивалентности существует на множестве с мощностью 1, 2, 3.
- Изобразите таблицу сложения и умножения для Z_n с n = 3, n = 5, n = 8. Подумайте, как должны выглядеть такие таблицы для Z_1.
- Классифицируйте отношение «поедает» в контексте экосистемы, например, леса.
- Сколько существует отношений линейного строгого порядка на множестве мощность 1? 2? 3? 4? n?
- Верно ли, что для каждого множества существует одинаковое количество отношений линейного порядка частичных и строгих? (Подсказка: рассмотрите соответствия между множествами линейных отношений частичных и строгих на произвольном непустом множестве)
Благодарю за внимание!