Бинарные отношения, свойства отношений. Отношения эквивалентности, порядка и толерантности. Бинарные отношения — MT1102: Линейная алгебра (введение в математику) — Бизнес-информатика Является ли отношение отношением эквивалентности
КУРСОВАЯ РАБОТА
«Отношение
эквивалентности»
Введение
Глава 1. Понятие отношения. Определение, типы, примеры отношений
Глава 2. Разбиение на классы. Фактор-множество. Отношение эквивалентности. Операции над эквивалентностями.
Глава 3. Отношения в школьной математике
Заключение
Список
использованных источников
Введение
Настоящая курсовая работа посвящена изучению понятия отношения вообще и, в частности, отношения эквивалентности. Эти понятия являются основополагающими в курсе алгебры и в то же время они могут быть выведены из общепринятых житейских понятий равенства, сходства, порядка. Это дает возможность знакомить с ними старших школьников, не углубляясь в теорию, на конкретных примерах из школьного курса математики.
Первая глава курсовой работы будет посвящена понятию отношения вообще, способам задания отношений, алгебраической и геометрической интерпретации отношений. Будут введены некоторые теоретико-множественные операции над отношениями. Рассматриваются основные свойства отношений и значение этих свойств для геометрического и алгебраического способов задания отношений. Глава размещена на 7 листах.
Во второй главе настоящей курсовой работы раскрывается смысл отношения эквивалентности. Доказывается теорема о равносильности определений. Приводится ряд примеров. Вводится понятия разбиения на классы и фактор-множества. Определяются также некоторые другие важные отношения.
Третья глава посвящена рассмотрению некоторых
отношений, вводимых на множествах знакомых и понятных любому старшему школьнику
объектов. Наглядно иллюстрируются свойства отношений эквивалентности,
толерантности, порядка. Делается вывод о возможности введения этих понятий на
занятиях математических кружков. Глава содержит 5 листов.
Глава 1. Понятие отношения. Определение, типы, примеры отношений
Определение отношения. Способы задания
отношений
Если говорить языком, доступным пониманию школьника, задать отношение - значит указать, между какими объектами оно выполняется.
Например, отношение «быть братом» будет полностью определено, если мы составим список всех пар людей, один из которых - брат второго.
Отношение может быть определено не только для пар объектов (бинарное), но и для троек, четверок и т.д.
Примерами трехместных (тернарных) отношений являются алгебраические операции. Например, отношение «образовывать сумму» имеет смысл для троек чисел (x, y, z) и выполняется в том случае, когда x + y = z.
Перейдем к более строгому определению.
Пусть А и В - некоторые произвольные непустые множества.
Определение 1.1. Декартовым произведением множества А на множество В называется множество А х В, элементами которого являются всевозможные пары (а, b), где первый элемент берется из множества А, а второй-из множества В. Две такие пары считаются равными, если у них совпадают и первые, и вторые элементы: (а, b) = (с, d) а = с и b = d.
Пример 1.1. Если А= (0, 1, +} и В = (□, о, , +}, то
А В - {(0, □), (0, о), (0. ),
(0, +), (1, □), (1, o), (1, ), (1, +), (+, □),
(+, о), (+, ), (+, +)}. Несложными рассуждениями устанавливается
справедливость следующих соотношений:
=
=
=
4) A-подмножество B и С -подмножество D, то подмножество
Определение 1.3. Бинарным отношением между множествами A и В называется всякое подмножество декартова произведения А х В, т. е. любой элемент множества Р(А х В) всех подмножеств множества А х В.
Если |A| = т, |B|=n, то декартово произведение А х В будет состоять из тп различных пар. В этом случае | Р(А х В) | = 2 mn ,- это и есть общее число всевозможных бинарных отношений между множествами A и В.
Бинарные отношения будем обозначать строчными греческими буквами. Если (a, b) р, то говорят, что элемент а находится с элементом b в отношении ρ.
Среди всех отношений между
множествами A и В выделяются: пустое отношение Ø, не
содержащее ни одной пары; универсальное отношение, содержащее все возможные
пары, т. е. само декартово произведение A и В.
Для любого отношения ρ Р(А
х В) имеют место включения
ρ А х В
Есть два удобных способа представления отношений между элементами конечных множеств:
) с помощью двоичных булевых матриц;
) с помощью графов.
Пусть А ={a 1 , a 2 , …a m }, B={b 1 , b 2 , …b m }, ρ А х В
Построим матрицу М(ρ)
размерности т х n следующим образом. Строки этой
матрицы пометим элементами множества A,
расположенными в некотором фиксированном порядке, а столбцы аналогично пометим
элементами множества В. Затем положим в качестве элементов матрицы М(ρ):
Здесь 0, 1 - элементы двоичной булевой алгебры B 2 . Таким образом, элемент представляет собой логическое значение высказывания «пара принадлежит отношению ρ».
Очевидно, что различным отношениям между множествами A и В соответствуют различные двоичные булевы матрицы. Подчеркнем, что порядок элементов в A и В раз и навсегда фиксирован.
Пусть М-n-элементное множество и ρ - отношение на нем. Отношение на М может быть задано матрицей размерности n x n. Матрица, для которой а ij = 0 задает пустое отношение Ø, которое не выполняется ни для одной пары.
Матрица, для которой а ij = 1 задает полное отношение М х М, которое выполняется для всех пар.
Особую роль играет также матрица ||δ i j ||, где
Символ называют символом Кронекера. Этой матрице соответствует так называемое диагональное отношение Е или отношение равенства: (x, y), если x и y - один и тот же элемент множества.
Полезно также ввести антидиагональное отношение условием:
Для пустого, полного, диагонального и антидиагонального отношений имеет место любопытное свойство - их матрицы на зависят от выбора нумерации элементов множества М. Иначе говоря, если отношение ρ таково, что при любом выборе нумерации в М матрицы || a ij || совпадают, то ρ либо полное, либо пустое, либо диагональное, либо антидиагональное.
Можно представить отношение и иначе:
Пусть снова ρ М х М.
Определим (ориентированный) граф G(ρ) следующим образом:
Множество вершин этого графа будут составлять множество М при этом, из вершины a i проводится
ребро в вершину b j в том и
только в том случае, если
, причем если (а i , a i), то у точки a i нарисуем
петлю, выходящую и входящую в одну и ту же точку.
Пустому отношению соответствует граф
без стрелок и петель, диагональное отношение описывается графом, в котором
присутствуют только петли (рис1.1). Полное отношение задается полным графом
(все вершины соединены со всеми, рис 1.2).
рис. 1.1 
рис. 1.2
Граф есть геометрическое изображение отношения, как график - геометрическое изображение функции. Геометрический язык полезен, когда граф достаточно прост. Наоборот, изучать и описывать графы с большим числом вершин удобнее в терминах отношений.
II. Функции как отношения
Частным случаем отношений можно считать и функции. Пусть отношение на множестве М таково, что для всякого хМ существует ровно один элемент у М, для которого (х, у) . Тем самым каждому элементу хМ сопоставляется некоторый у М, определенный этим условием. Такое отношение и называется функцией или отображением. Множество пар, для которых (х, у) , называется графиком функции.
Пример: Если М - числовая прямая, а отношение - есть отношение равенства х = у, то график состоит из всех точек вида (х, х) и является биссектрисой координатного угла (графиком функции у = х). Если отношение выполнено для тех пар, для которых у =sin x, то график этой функции -обычная синусоида.
Итак, наше определение графика - обобщение обычного графика числовых функций.
III. Операции над отношениями.
Поскольку отношения между множествами A и В представляют собой ни что иное, как подмножества множества А х В, то для них определены все теоретико-множественные операции.
Определение 1.4. Пересечением
отношений ρ
и
δ
назовем
пересечение соответствующих подмножеств. Ясно что (x, y) тогда и только тогда, когда
одновременно (x, y)
.
Определение 1.5. Объединением отношений ρ и δ назовем объединение соответствующих подмножеств. Ясно что (x, y) тогда и только тогда, когда выполнено хотя бы одно из соотношений (x, y).
Важную роль играет операция,
обозначаемая ρδ
- произведение
отношений. Эта операция определяется так: соотношение (x, y) равносильно тому, что существует
такое z, для которого выполнено (x, z)
IV. Свойства отношений.
Определение 1.6. Отношение ρ называют рефлексивным, если оно всегда выполнено между объектом и им самим: (х, х).
Рефлексивные отношения всегда представимы в виде матриц, у которых на главной диагонали стоят единицы. В графе, изображающем рефлексивное отношение, каждая вершина имеет петлю.
Определение 1.7. Отношение ρ называют антирефлексивным, если из (х, у), всегда следует х ≠ у.
Отношения «быть братом», «быть старше» - антирефлексивны.
Матрица, представляющая антирефлексивное отношение, имеет на главной диагонали нули, а соответствующий граф непременно не имеет петель.
Определение 1.8. Отношение ρ называют симметричным, если из (х, у), всегда следует (у, х).
В матрице, представляющей симметричное отношение, элементы, расположенные симметрично относительно главной диагонали, равны между собой a ij = a ji .
В соответствующем графе, вместе с каждой стрелкой существует стрелка противоположного направления. Симметричное отношение можно изображать виде неориентированного графа.
Определение 1.9. Отношение ρ называют асимметричным, если из двух соотношений (х, у) или (у, х) по меньшей мере, одно не выполнено.
Для матричных элементов это приводит к равенству: a ij ∙a ji =0
В соответствующем графе, не может быть стрелок, соединяющих две вершины в противоположном направлении.
Теорема 1.1: Если отношение асимметрично, то оно антирефлексивно.
Определение 1.10. Отношение ρ называют антисимметричным, если соотношения (х, у) и (у, х) выполняются одновременно, только когда х=у.
Для матричных элементов это приводит к равенству: a ij ∙a ji =0, когда i≠j
Определение 1.11. Отношение ρ называют транзитивным, если из того, что выполняются соотношения (х, z) и (z, y) следует, что (х, у). По индукции отсюда следует такое свойство: если (х, z 1), (z 1 , z 2) …(z n -1 , y) то (х, y).
Это свойство хорошо интерпретируется на графе: если точки х и у соединены путем, проходимым по направлению стрелок, то существует стрелка, непосредственно ведущая из вершины х с вершину у.
отношение эквивалентность математика
Глава 2. Разбиение на классы. Отношение эквивалентности. Свойства эквивалентности. Фактор-множество
Разбиение на классы. Отношение эквивалентности
Определение 2.1. Назовем взаимозаменяемыми те и только те объекты некоторого данного множества М, которые обладают одним и тем же набором формальных признаков, существенных в данной ситуации.
Обозначим через М х
-множество всех объектов, взаимозаменяемых с объектом х. Очевидно, что х М х и объединение всех М х
(при всевозможных х из М) совпадает совсем множеством М:
Предположим, что
. Это значит, что существует
некоторый элемент z, такой, что он одновременно
принадлежит и и . Значит x
взаимозаменяем с z и z
взаимозаменяем с у. Следовательно, х взаимозаменяем с у, а значит и с любым
элементом из. Таким образом . Аналогично показывается и обратное
включение. Таким образом, встречающиеся в объединении (2.1) множества либо не пресекаются, либо целиком
совпадают.
Определение 2.2. Систему непустых
подмножеств {M 1 , M 2 ,….}
множества М мы будем называть разбиением этого множества, если
Сам множества при этом называются классами разбиения.
Определение 2.3. Отношение ρ на множестве М называется эквивалентностью (или отношением эквивалентности), если существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения.
Пусть {M 1 , M 2 ,….} разбиение множества М. Определим, исходя из этого разбиения, отношение ρ на М: (х, у),если х и у принадлежат к некоторому общему классу M i данного разбиения. Очевидно, что отношение ρ является эквивалентностью. Назовем ρ отношением эквивалентности, соответствующим данному разбиению.
Определение 2.4. Если в каждом подмножестве M i выбрать содержащийся в нем элемент х i , то этот элемент будем называть эталоном для всякого элемента у, входящего в тоже множество M i . По определению, положим выполненным отношение ρ* «быть эталоном» (х i , у)
Легко видеть, что эквивалентность ρ, соответствующая данному разбиению, может быть определена и так: (z, у) если z и у имеют общий эталон (х i , z) и (х i , у).
Пример 2.1: Рассмотрим в качестве М
множество целых неотрицательных чисел и возьмем его разбиение на множество М 0
четных чисел и множество М 1 - нечетных. Соответствующее отношение
эквивалентности на множестве целых чисел обозначается так:
и читается: n сравнимо с m по модулю 2. В качестве эталонов естественно выбрать 0 - для четных чисел и 1 - для нечетных. Аналогично, разбивая то же множество М на k подмножеств M 0 , M 1 ,… M k -1 , где M j состоит из всех чисел, дающих при делении на k в остатке j, мы придем к отношению эквивалентности:
которое выполняется, если n и m имеют одинаковые остатки при делении на k.
В качестве эталона в каждом M j естественно выбрать соответствующий остаток j.
II. Фактор-множество
Пусть - отношение эквивалентности. Тогда по теореме, существует разбиение {M 1 , M 2 ,….} множества М на классы эквивалентных друг другу элементов - так называемые классы эквивалентности.
Определение 2.5. Множество классов эквивалентности по отношению обозначают М/ и читают фактор-множество множества М по отношению.
Пусть φ: M → S - сюрьективное отображение множества М на некоторое множество S.
Для всякого φ: M → S - сюрьективного отображения существует такое отношение эквивалентности на множестве М, что М/ и S могут быть поставлены во взаимно однозначное соответствие.
III. Свойства эквивалентности
Определение 2.6. Отношение ρ на множестве М называется эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.
Теорема 2.1: Если отношение ρ на множестве М рефлексивно, симметрично и транзитивно, существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения.
Обратно: Если задано разбиение {M 1 , M 2 ,….} и бинарное отношение ρ задано как «принадлежать к общему классу разбиения», то ρ рефлексивно, симметрично и транзитивно.
Доказательство:
Рассмотрим рефлексивное, симметричное и транзитивное отношение ρ на М. Пусть для любого состоит из всех таких z, для которых (x, z) ρ
Лемма 2.1: Для любых x и y либо либо 
Из леммы и рефлексивности отношения ρ следует, что множества вида образуют разбиение множества М. (Это разбиение естественно назвать разбиением, соответствующим исходному отношению). Пусть теперь (x, y) ρ. Это значит, что y. Но и х в силу (x, х) ρ. Следовательно, оба элемента входят в . Итак, если (x, y) ρ, то х и у входят в общий класс разбиения. Наоборот, пусть uи v. Покажем, что (u, v) ρ, Действительно, имеем (x, u) ρ и (x, v) ρ. Отсюда по симметричности (u, x) ρ. По транзитивности из (u, x) ρ и (x, v) ρ следует (u, v) ρ. Первая часть теоремы доказана.
Пусть дано разбиение {M 1 , M 2 ,….} множества М. Т.к. объединение всех классов разбиения совпадает с М, то любой хвходит в некоторый класс . Отсюда следует, что (x, х) ρ, т.е. ρ - рефлексивно. Если x и y входят в некоторый класс , то y и x входят в тот же класс. Это означает, что из (x, y) ρ вытекает (y, x) ρ, т.е. отношение симметрично. Пусть теперь выполнено (x, y) ρ и (y, z) ρ. Это означает, что x и y входят в некоторый класс , а y и z входят в некоторый класс . Классы имеют общий элемент у, а, следовательно, совпадают. Значит x и z входят в класс , т.е. выполняется (x, z) ρ и отношение транзитивно. Теорема доказана.
IV. Операции над эквивалентностями.
Определим здесь некоторые теоретико-множественные операции над эквивалентностями и приведем без доказательств их важные свойства.
Вспомним, что отношение - это пара (), где М - множество элементов, вступающих в отношение, а - множество пар, для которых отношение выполнено.
Определение 2.7. Пересечением отношений (ρ 1 , М) и (ρ 2 , М) назовем отношение, определенное пересечением соответствующих подмножеств. (x, y) ρ 1 ρ 2 тогда и только тогда, когда одновременно (x, y) ρ 1 и (x, y) ρ 2 .
Теорема 2.2: Пересечение ρ 1 ρ 2 эквивалентностей ρ 1 ρ 2 само является отношением эквивалентности.
Определение 2.8. Объединением отношений (ρ 1 , М) и (ρ 2 , М) назовем отношение, определенное объединением соответствующих подмножеств. (x, y) ρ 1 ρ 2 тогда и только тогда, когда (x, y) ρ 1 или (x, y) ρ 2 .
Теорема 2.3: Для того, чтобы
объединение ρ 1 ρ 2
эквивалентностей ρ 1 ρ 2 само по себе
было отношением эквивалентности необходимо и достаточно, чтобы
ρ 1 ρ 2 =ρ 1 ρ 2
Определение 2.9. Прямой суммой отношений (ρ 1 , М 1) и (ρ 2 , М 2) называется отношение). Прямая сумма обозначается (ρ 1 , М 1) (ρ 2 , М 2).
Таким образом, если (ρ 1 , М 1) (ρ 2 , М 2)= (), то M=.
Теорема 2.4: Если , а отношения - эквивалентности, то прямая сумма отношений (ρ 1 , М 1) (ρ 2 , М 2)= (), также является эквивалентностью.
V. Типы отношений
Введем еще несколько важных типов отношений. Примеры будут приведены в третьей главе.
Определение 2.10. Отношение ρ на множестве М называется толерантностью, если оно рефлексивно и симметрично.
Определение 2.11. Отношение ρ на множестве М называется отношением строгого порядка если оно антирефлексивно и транзитивно.
Определение 2.12. Отношение строгого порядка ρ называется совершенным строгим порядком, если для всякой пары элементов x и y из М верно либо (х, у), либо (у, х)
Определение 2.13. Отношение ρ на множестве
М называется отношением нестрогого порядка если оно может быть представлено в
виде:
Глава 3. Отношения в школьной математике
Отношения между геометрическими объектами
Многие хорошо известные из школьной математики понятия, в сущности, являются названиями бинарных отношений, а основные связанные с ними теоремы выражают свойства этих отношений.
Пример 3.1. Пусть М- множество всех прямых на плоскости. Соотношение Х || Y означает, что прямые X и Y параллельны. Установим некоторые свойства этого отношения.
Отношение || антирефлексивно. Действительно, никакая прямая не параллельна сама себе.
Отношение || симметрично, это видно из того, что в определении параллельности обе прямые равноправны.
Отношение || почти транзитивно. а именно: если Х || Y и Y || Z, то либо X || Z, либо пряные Х и Z совпадают. Действительно, если бы это было не так, то прямые X и Z пересекались бы. Но, как известно из геометрии, если прямая Z пересекается с одной из параллельных X, то она пересекается и с другой из параллельных Y, т.е. было бы невозможно соотношение Y || Z.
Таким образом, отношение параллельности между
прямыми не обладает еще хорошими свойствами. Но сказанное выше позволяет легко
сообразить, какое отношение, родственное параллельности, будет отношением
эквивалентности. А именно, определим отношение
Которое выполняется, когда прямые параллельны, либо совпадают. По определению, Х ||| X для любой прямой Х. Симметричность отношения ||| также очевидна. Наконец, если Х||| Y и Y ||| Z, то Х ||| Z. В самом деле, если Х || Y и Y = Z, то Х || Z; если Х = Y и Y || Z, то Х || Z. Наконец, если Х || Y и Y || Z, то, по сказанному ранее, либо Х = Z, либо Х || Z. Во всех случаях имеем Х ||| Z.
Отношение ||| на множестве прямых
очень естественно выглядит в алгебраической форме. Если на плоскости ввести
декартовы координаты х и у, то всякая прямая, не перпендикулярная оси Ох (не
вертикальная) задается уравнением y=kx+b. Иначе
говоря, любая (за указанным исключением) прямая определяется парой чисел (k, b). Пусть
прямая Х задается уравнением y=kx+b, а прямая Y --
уравнением y=k’x+b’. Тогда
соотношение X|||Y выполняется
в том и только в том случае, когда k=k’ (k- тангенс
угла наклона прямой к оси Ох). Соотношение X||Y означает,
что k=k’ и
одновременно b≠b’, т.е.
прямые различны. Для вертикальных прямых можно положить k=∞ (), и условие k=k’будет
по-прежнему означать X|||Y. Однако,
это соглашение не очень красиво, так как при k=∞ у
нас не определен второй параметр, различающий параллельные прямые.
В аналитической геометрии дается
более универсальная (нормальная) форма задания прямой: x cos α + y sin α - p =0, которая
описывает прямую любого вида. Здесь р - длина перпендикуляра, опущенного из
начала координат на прямую, α - угол наклона этого перпендикуляра к
оси абсцисс.
Тем самым каждой прямой взаимно-однозначно сопоставлена пара чисел (α, р), где 0 ≤ α < 2π и 0 ≤ р < +∞. Соотношение X|||Y означает, что для соответствующих прямых α = α’ или α = α’ + π. Каждой прямой соответствует точка на плоскости параметров α и р, лежащая в области, изображенной на рисунке 3.2. Пары вертикальных прямых α=const и α+ π=const (0 ≤ α < π) суть классы эквивалентности отношения |||.
Пример 3.2. На множестве прямых на плоскости существует еще одно важное отношение: X ┴Y (X перпендикулярна Y). Отношение перпендикулярности обладает следующими важными свойствами:
1. Антирефлексивность. Невозможно X ┴ X.
2. Симметричность. Если X ┴ Y, то Y ┴ X.
3. Если X ┴ Y и Y ┴ Z то невозможно Х ┴ Z. Из X ┴ Y и Y ┴ Z следует, очевидно, X ||| Z. Обратно, если X ||| Z, то существует общий перпендикуляр Y к прямым Х и Z, т.е. такое Y, что X ┴ Y и Y ┴ Z.
Оба последних утверждения означают, что квадрат отношения перпендикулярности есть отношение ||| - «усиленной параллельности»:
┴
┴ = ┴ 2 =|||.
Пример 3.3. Введем на М еще одно отношение X Пер Y, означающее, что прямые имеют хотя бы одну общую точку, т.е. пересекаются или совпадают. Ясно, что отношение Пер рефлексивно, симметрично, но не транзитивно и является отношением толерантности.
Выберем на плоскости некоторую точку Р и рассмотрим множество К р всех прямых, проходящих через эту точку. Легко видеть, что К р есть класс толерантности. Действительно, любые прямые из К р имеют общую точку, а именно - саму точку Р. С другой стороны, любая прямая Х, не входящая в К р, не пересекается с некоторой прямой из К р, а именно с прямой, проходящей через точку Р параллельной Х.
Пример 3.4. Пусть теперь М -- множество всех треугольников на плоскости. Равенство и подобие треугольников - суть отношения эквивалентности.
Пример 3.5. Обозначим через М к множество окружностей на плоскости и определим отношение X |= Y условием, что окружность X находится внутри окружности Y. Это отношение антирефлексивно, транзитивно, т.е. является строгим порядком. Этот порядок не является совершенным, т.к. существуют окружности, не одна из которых не лежит внутри другой.
Пример 3.6. Множеству всех прямых присвоим обозначение М п. тогда можно рассмотреть отношения между прямыми и окружностями. Примером такого отношения является отношение X Кас Y - прямая X касается окружности Y.
II. Отношения между уравнениями.
Пусть теперь множество М состоит из уравнений
вида:
f(x)=g(x)
(α)
Множество всех корней уравнения α будем обозначать Rα.
Например, для уравнения
x 2 =x 3
(α 1)
Rα 1 ={0,1}.Для
уравнения
cos x=sin x (α 2)
Rα 2 ={…}.Для уравнения
X 2 =-1 (α 3)
Rα 3 =Ø. Для уравнения
(1+ x) 2 = x 2 +2x+1 (α 4)
Rα 4 =(-∞,
+∞).
Пример 3.7. Введем теперь отношения между уравнениями: назовем уравнения α и β равносильными α ≈ β, если Rα = Rβ.
Из того, что равенство множеств есть отношение эквивалентности, легко получается, что отношение ≈ есть отношение эквивалентности. В школьном курсе изучаются преобразования уравнений, которые переводят уравнение α в равносильное ему уравнение β.
Пример 3.8. Уравнение α не сильнее уравнения β: α => β, если Rα содержится в Rβ. В этом случае говорят что уравнение β не слабее α.
Отношение => рефлексивно и транзитивно, т.е. является квазипорядком. Из α => β и β => α вытекает равносильность α ≈ β. Обратно, из равносильности α ≈ β следует α => β и β => α. Таким образом, ≈ = =>=> -1 .
Пример 3.9. На множестве уравнений, имеющих хотя бы один корень, легко определить естественное отношение толерантности - наличие общих корней: Rα ∩ Rβ ≠ Ø.
Пример 3.10. Можно ввести еще отношение эффективной равносильности. Уравнения α и β будем называть эффективно равносильными, если каждое из них можно преобразовать в другое с помощью конечного числа равносильных преобразований (разрешенных приемов из фиксированного списка).
В силу транзитивности отношения , любое число применения таких приемов не нарушают равносильности. Поэтому эффективно равносильные уравнения являются равносильными, что можно назвать включением одного отношения в другое.
Рассмотренные примеры отношений ярко
иллюстрируют понятие отношения, в том числе и отношения эквивалентности, их
свойства легко проверяются инструментом школьной математики и вполне наглядны.
Поэтому, можно вводить понятие отношений старшим школьникам, занимающимся в
математических кружках.
Заключение
Бинарные отношения - очень удобный и простой аппарат для решения весьма разнообразных задач. Язык бинарных (и более общих) отношений очень удобен и естествен для математической лингвистики, математической биологии и целого ряда других прикладных (для математики) областей. Это очень легко объяснить, если сказать, что геометрический аспект теории бинарных отношений есть попросту теория графов. Но насколько геометрическая теории графов известна и хорошо освещена в литературе, настолько скудно изложены алгебраические аспекты теории отношений.
А между тем алгебра отношений может быть рассказана вполне общедоступно. Так, чтобы ее могли усвоить старшие школьники, занимающиеся в математических кружках.
В данной работе были рассмотрены понятия
отношения, эквивалентности, разобраны некоторые их свойства, приведены
геометрические интерпретации и наглядные примеры.
Список использованных источников
1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. - М.: Наука. Физматлит, 1997. -368с.
2. Шрейдер Ю.А. Равенство. Сходство. Порядок. - М.: Наука, 1971.-256с.
Кострикин А.И. Введение в алгебру. - М.: Наука, 1977.-334с.
Б.Л. ван-дер-Варден. Современная алгебра. в 2 т. Т.1.- М., ОГИЗ ГОСТЕХИЗДАТ, 1947 -339с.
Во многих вычислительных задачах берутся большие множества и разбиваются таким образом, чтобы все интересующие нас ситуации можно было исследовать на нескольких правильно выбранных примерах.
Определение 1: Пусть A ¹ Æ и {A i },i= совокупность подмножеств таких, что A= . Тогда совокупность этих подмножеств называется покрытием множества A.
Например, {A, B}- покрытие AÈB; {A, AÈB, B, C}-покрытие AÈBÈC.
Замечание: В общем случае покрытие может быть и бесконечным. однако с точки зрения изучения конкретных свойств такая ситуация не вызывает энтузиазма.
Определение 2: Разбиением непустого множества А называется такое его покрытие , что если i¹ j, то A i ÇA j =Æ.
Например, {A, A’} – разбиение U .
{AÇB, AÇB’, A’ÇB, A’ÇB’} – разбиение U ,
{A\B, AÇB, B\A} – разбиение AÈB.
Организовать разбиение непустого множества можно при помощи отношений, которые ведут себя подобно отношениям равенства на множестве чисел или множеств.
Определение 3: Бинарное отношение на множестве называется отношением эквивалентности , если оно рефлексивно, симметрично и транзитивно.
Примеры :
1. На множестве всех треугольников: {(x, y)| x и y имеют одинаковую площадь}
2. На множестве всех программ: {(a, b)| a, b вычисляют одну и ту же функцию на конкретной машине}
Определение 4: Пусть R – отношение эквивалентности на множестве А и xÎA. Классом эквивалентности порожденным элементом х называется множество {y| xR y}=[x] R .
Определение 5: Любой элемент класса эквивалентности называется представителем этого класса. Полной системой представителей называется множество представителей, по одному из каждого класса.
Пример 3 :
N – натуральные числа, s – фиксированный элемент. На Z определено отношение: r s = {(x, y)| x-y=ns, nÎZ }. Отношение сравнения по модулю s (запись: xºy(mod s)).
Нетрудно проверить, что отношение сравнения по модулю s, есть отношение эквивалентности на множестве Z.
Пусть, например, s=10. Тогда:
= {11,21,-9,10 976 631,.... }
= {66,226,-24,... }
На самом деле есть всего 10 классов эквивалентности по этому отношению, а числа 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 образуют полную систему представителей . Классы эквивалентности по этому отношению эквивалентности называют классами вычетов по модулю s.
Определение 6: Фактор-множеством множества А по отношению эквивалентности R называется множество всех классов эквивалентности по этому отношению и обозначается A/R.
Множество классов вычетов по модулю s обозначают Z s .
Имеет место
Теорема (о разбиении): Пусть R - отношение эквивалентности на непустом множестве А. Тогда фактор-множество A/R является разбиением множества А.
Доказательство:
"xÎA(xÎ[x] R). Надо доказать, что каждый элемент множества А принадлежит в точности одному классу. То есть, докажем, что если классы имеют хотя бы один общий элемент, то они совпадают. Пусть cÎ[a] и cÎ[b]. Пусть xÎ[a], но тогда x R a, a R c, c R b Þ x R b(транзитивность R). Значит, [a] Ì [b]. (где рефлексивность? а она есть!) Аналогично [b] Ì [a].
Что и требовалось доказать.
Имеет место и обратное утверждение. Пусть S- разбиение множества А и R s – бинарное отношение на A, такое что: R={(x,y)ïx и y принадлежат одному элементу разбиения }, тогда R , будем называть– отношением, определяемым разбиением S.
Теорема (обратная): Отношение R на А, определяемое разбиением S, является отношением эквивалентности на А, причем A/R s =S.(самостоятельно)
Упражнения:
1. Пусть А- конечное множество. Какие отношения эквивалентности дают наибольшее и наименьшее число классов эквивалентности.
2. Если {A 1 , A 2 , ..., A n }- разбиение А и А конечно, то .
Отношение порядка.
Из понятия равенства (например, чисел) возникает математическое понятие эквивалентности. А из понятия неравенства возникает другой тип отношений, которые называются отношениями порядка.
Определение 1: Частичным порядком на множестве А называется бинарное отношение, которое рефлексивно, антисимметрично и транзитивно.
Частичный порядок - это обобщение отношения £ на R. Можно ввести понятие строгого порядка , соответствующего отношению < на R. Отношение строгого порядка - только транзитивно(оно еще и антирефлексивно).
Если задан £, то можно определить <: a
Множество, на котором задано отношение порядка, будем обозначать
(X, £) (или (X, <), если порядок строгий).
Определение 2: Множество, на котором задано отношение порядка, называется частично упорядоченным.
Пример: A - множество. (P (A),Í ), легко проверить, что отношение Í является отношением порядка на P (A).
Определение 3: Отношение порядка R на А называется полным (линейным) порядком , если " x, yÎA (xR y Ú yR x). Множество (A, R) называется линейно упорядоченным.
Примеры :
1. отношение £ на R является отношением полного порядка. Таким образом (R, £) - линейно упорядочено.
2. а вот (P (A),Í ) не является линейно упорядоченным
3. x£y Û y x на множестве N не является полным порядком
Определение 4: пусть (A, £) – частично упорядоченное множество. Элемент аÎА называетсянаименьшим /наибольшим/ в А, если " xÎA (a£ x) /x £ a /. Элемент bÎА называется минимальным /максимальным/ если " xÎA (x£ a Þ x=a) /a £ x Þ a=x /.
Задача: Доказать, что для линейно упорядоченного множества понятия наибольшего (наименьшего) и максимального (минимального) элементов совпадают. Привести пример частично упорядоченного множества, где они не совпадают.
Композиция отношений
Пусть заданы множества A, B и C и отношения S между A и B (то есть SÌA´B) и R между B и C (RÌB´C). Определим новое отношение между A и C следующим образом:
Определение 1: Множество всех пар (x, y), таких, что существует zÎB такое, что (x, z)Î S и (z, y)Î R называется композицией отношений S и R . Обозначается: R o S . Таким образом, R o S Ì A ´ C .
R oS = {(x, y)| $zÎB((x,z)ÎSÙ(z,y)ÎR)} или x R o Sy Û $zÎB(xSzÙzRy).
Пример 1 : Пусть A={1, 2, 3}, B={1, 2, 3, 4, 5, 6}, C={3, 6, 9, 12}, s ={(1,2), (2,4), (3,6)}, r={(1,3), (2,6), (3,9), (4,12)}. Тогда r o s={(1,6), (2,12)}.
Проиллюстрируем ситуацию на картинке:
Пример 2 : Пусть s и r - отношения на N такие, что
S = {(x,x+1)ïxÎN } и r = {(x 2 ,x)ïxÎN }. Тогда D r = {x 2 ïxÎN }={1,4,9,16,25,...}, а D s = N.
D r o s ={xïxÎN Ù x+1=y 2 }={3,8,15,24,...}.
В случае, когда отношение задано на множестве, оно может быть скомбинировано с самим собой:
sos = s 2 = {(x,x+2)½xÎN } и ror = r 2 = {(x 4 ,x)½xÎN }.
Используя это обозначение, можно определить энную степень отношения:
, где nÎN
, n>1.
Например, для отношений из примера 2 имеем:
, 
Хотелось бы дополнить аналогию с умножением. Для этого введем следующее естественное определение:
Определение 2: Бинарные отношения называются равными , если они равны как подмножества, то есть R=S, если"x,y((x,y)ÎRÛ(x,y)ÎS).
Понятно, что отношения должны быть определены на одних и тех же множествах.
Теорема (свойства композиции отношений): Для любых бинарных отношений R, S, T имеют место равенства:
1. (RoS)oT = Ro(SoT)
2. (RoS) -1 = S -1 o R -1
Доказательство:
1) Для любых x и y имеем:
x(RoS)oTy º $z(xTzÙ(zRoSy)) º $z$t(xTzÙ(zStÙtRy)) º $z$t((xTzÙzSt)ÙtRy) º $t(($z(xTzÙzSt))ÙtRy) º $t((xSoTt)ÙtRy) º xRo(SoT)y.
2) x(RoS) -1 y º yRoSx º $z(ySzÙzRx) º $z(xR -1 zÙzS -1 y) º xS -1 oR -1 y.
Что и требовалось доказать.
Замечание: если R - отношение на множестве A, то ясно, что I A oR=RoI A =R. То есть I A ведет себя как единица при умножении чисел. Однако полной аналогии провести нельзя. Поскольку, например, коммутативность, в общем случае места не имеет, так как RoS может быть определено, а SoR нет. Также как и не всегда имеет смысл равенство R -1 oR=RoR -1 = I A .
Замыкание отношений
Понятие замыкания является фундаментальным математическим понятием и используется в большинстве разделов математики. Проиллюстрируем это понятие на общем примере: возьмем объект x 0 и процесс P, который, будучи примененный последовательно, порождает некоторое множество и, значит, определяет последовательность x 1 , x 2 , ..., x n , ... так, что x 1 ÎP(x 0), x 2 ÎP(x 1),..., x n ÎP(x n -1),... 
Определение 1: множество, содержащее все элементы всех последовательностей, которые могут быть получены при помощи процесса P и начинающиеся с x 0 , называется замыканием процесса P относительно x 0 .
Ясно, что результат будет заключаться в нахождении Р n (x 0) при некотором n. Это n мы заранее не знаем, оно зависит от самого процесса. Более того, если мы возьмем элемент y из этого замыкания и будем применять к нему процесс р, то не получим ничего нового. То есть множество таким путем расширено быть не может - оно замкнуто!
Пример : Возьмем квадрат S, обозначенный ABCD и рассмотрим процесс r, заключающийся в повороте квадрата по часовой стрелке на 90°:
| |
| |
| |
| |
| |
Пусть отношение A задано на некотором множестве. Тогда:
Определение 2: Транзитивным замыканием отношения A на данном множестве называется отношение A + :
Таким образом, из не транзитивного отношения A на некотором множестве можно построить транзитивное A + .
Примеры:
1. r - отношение на N
: r={(x, y)| y=x+1}, тогда r + ={(x, y)| x 2. s на Q
: s={(x, y)| x 3. t наQ
: t={(x, y)| x×y=1}, тогда r + ={(x, x)| x¹0} 4. Пусть L - множество станций лондонского метро; L={a, b, c} последовательные станции. N={(x, y)| y следует за x}.Значит (a, b), (b, c) ÎN; кроме того (a, a), (b, b), (c, c), (a, c) Î N 2 . Значит, N + =L´L Вообще говоря, транзитивное замыкание не является рефлексивным (пример 2). Пусть A - отношение на X. Положим A 0 =I X . Определение 3:
Рефлексивным замыканием А*
отношения A называют отношение Примеры:
1. r*={(x, y)| x£y} I. Разбиение на классы. Отношение эквивалентности Определение 2.1. Назовем взаимозаменяемыми те и только те объекты некоторого данного множества М, которые обладают одним и тем же набором формальных признаков, существенных в данной ситуации. Обозначим через М х -множество всех объектов, взаимозаменяемых с объектом х. Очевидно, что х М х и объединение всех М х (при всевозможных х из М) совпадает совсем множеством М: Предположим, что. Это значит, что существует некоторый элемент z, такой, что он одновременно принадлежит и и. Значит x взаимозаменяем с z и z взаимозаменяем с у. Следовательно, х взаимозаменяем с у, а значит и с любым элементом из. Таким образом. Аналогично показывается и обратное включение. Таким образом, встречающиеся в объединении (2.1) множества либо не пресекаются, либо целиком совпадают. Определение 2.2. Систему непустых подмножеств {M 1 , M 2 ,….} множества М мы будем называть разбиением этого множества, если Сам множества при этом называются классами разбиения. Определение 2.3. Отношение с на множестве М называется эквивалентностью (или отношением эквивалентности), если существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения. Пусть {M 1 , M 2 ,….} разбиение множества М. Определим, исходя из этого разбиения, отношение с на М: (х, у),если х и у принадлежат к некоторому общему классу M i данного разбиения. Очевидно, что отношение с является эквивалентностью. Назовем с отношением эквивалентности, соответствующим данному разбиению. Определение 2.4. Если в каждом подмножестве M i выбрать содержащийся в нем элемент х i , то этот элемент будем называть эталоном для всякого элемента у, входящего в тоже множество M i . По определению, положим выполненным отношение с* «быть эталоном» (х i , у) Легко видеть, что эквивалентность с, соответствующая данному разбиению, может быть определена и так: (z, у) если z и у имеют общий эталон (х i , z) и (х i , у). Пример 2.1: Рассмотрим в качестве М множество целых неотрицательных чисел и возьмем его разбиение на множество М 0 четных чисел и множество М 1 - нечетных. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так: и читается: n сравнимо с m по модулю 2. В качестве эталонов естественно выбрать 0 - для четных чисел и 1 - для нечетных. Аналогично, разбивая то же множество М на k подмножеств M 0 , M 1 ,… M k-1 , где M j состоит из всех чисел, дающих при делении на k в остатке j, мы придем к отношению эквивалентности: которое выполняется, если n и m имеют одинаковые остатки при делении на k. В качестве эталона в каждом M j естественно выбрать соответствующий остаток j. II. Фактор-множество Пусть - отношение эквивалентности. Тогда по теореме, существует разбиение {M 1 , M 2 ,….} множества М на классы эквивалентных друг другу элементов - так называемые классы эквивалентности. Определение 2.5. Множество классов эквивалентности по отношению обозначают М/ и читают фактор-множество множества М по отношению. Пусть ц: M > S - сюрьективное отображение множества М на некоторое множество S. Для всякого ц: M > S - сюрьективного отображения существует такое отношение эквивалентности на множестве М, что М/ и S могут быть поставлены во взаимно однозначное соответствие. III. Свойства эквивалентности Определение 2.6. Отношение с на множестве М называется эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно. Теорема 2.1: Если отношение с на множестве М рефлексивно, симметрично и транзитивно, существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения. Обратно: Если задано разбиение {M 1 , M 2 ,….} и бинарное отношение с задано как «принадлежать к общему классу разбиения», то с рефлексивно, симметрично и транзитивно. Доказательство: Рассмотрим рефлексивное, симметричное и транзитивное отношение с на М. Пусть для любого состоит из всех таких z, для которых (x, z) с Лемма 2.1: Для любых x и y либо либо Из леммы и рефлексивности отношения с следует, что множества вида образуют разбиение множества М. (Это разбиение естественно назвать разбиением, соответствующим исходному отношению). Пусть теперь (x, y) с. Это значит, что y. Но и х в силу (x, х) с. Следовательно, оба элемента входят в. Итак, если (x, y) с, то х и у входят в общий класс разбиения. Наоборот, пусть uи v. Покажем, что (u, v) с, Действительно, имеем (x, u) с и (x, v) с. Отсюда по симметричности (u, x) с. По транзитивности из (u, x) с и (x, v) с следует (u, v) с. Первая часть теоремы доказана. Пусть дано разбиение {M 1 , M 2 ,….} множества М. Т.к. объединение всех классов разбиения совпадает с М, то любой хвходит в некоторый класс. Отсюда следует, что (x, х) с, т.е. с - рефлексивно. Если x и y входят в некоторый класс, то y и x входят в тот же класс. Это означает, что из (x, y) с вытекает (y, x) с, т.е. отношение симметрично. Пусть теперь выполнено (x, y) с и (y, z) с. Это означает, что x и y входят в некоторый класс, а y и z входят в некоторый класс. Классы имеют общий элемент у, а, следовательно, совпадают. Значит x и z входят в класс, т.е. выполняется (x, z) с и отношение транзитивно. Теорема доказана. IV. Операции над эквивалентностями. Определим здесь некоторые теоретико-множественные операции над эквивалентностями и приведем без доказательств их важные свойства. Вспомним, что отношение - это пара (), где М - множество элементов, вступающих в отношение, а - множество пар, для которых отношение выполнено. Определение 2.7. Пересечением отношений (с 1 , М) и (с 2 , М) назовем отношение, определенное пересечением соответствующих подмножеств. (x, y) с 1 с 2 тогда и только тогда, когда одновременно (x, y) с 1 и (x, y) с 2 . Теорема 2.2: Пересечение с 1 с 2 эквивалентностей с 1 с 2 само является отношением эквивалентности. Определение 2.8. Объединением отношений (с 1 , М) и (с 2 , М) назовем отношение, определенное объединением соответствующих подмножеств. (x, y) с 1 с 2 тогда и только тогда, когда (x, y) с 1 или (x, y) с 2 . Теорема 2.3: Для того, чтобы объединение с 1 с 2 эквивалентностей с 1 с 2 само по себе было отношением эквивалентности необходимо и достаточно, чтобы с 1 с 2 =с 1 с 2 Определение 2.9. Прямой суммой отношений (с 1 , М 1) и (с 2 , М 2) называется отношение). Прямая сумма обозначается (с 1 , М 1) (с 2 , М 2). Таким образом, если (с 1 , М 1) (с 2 , М 2)= (), то M=. Теорема 2.4: Если, а отношения - эквивалентности, то прямая сумма отношений (с 1 , М 1) (с 2 , М 2)= (), также является эквивалентностью. V. Типы отношений Введем еще несколько важных типов отношений. Примеры будут приведены в третьей главе. Определение 2.10. Отношение с на множестве М называется толерантностью, если оно рефлексивно и симметрично. Определение 2.11. Отношение с на множестве М называется отношением строгого порядка если оно антирефлексивно и транзитивно. Определение 2.12. Отношение строгого порядка с называется совершенным строгим порядком, если для всякой пары элементов x и y из М верно либо (х, у), либо (у, х) Определение 2.13. Отношение с на множестве М называется отношением нестрогого порядка если оно может быть представлено в виде: где строгий порядок на М, а Е -диагональное отношение. Лекция 22. Отношения эквивалентности и порядка на множестве
1. Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы. 2. Отношение порядка. Строгое и нестрогое отношения порядка, отношение линейного порядка. Упорядоченность множеств. 3. Основные выводы Рассмотрим на множестве дробей X
= {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} отношение равенства. Это отношение: Рефлексивно, так как всякая дробь равна сама себе; Симметрично, так как из того, что дробь m
/n
равна дроби p
/q
, следует, что дробь p
/q
равна дроби m
/n
; Транзитивно, так как из того, что дробь m
/n
равна дроби p
/q
и дробь p
/q
равна дроби r
/s
, следует, что дробь m
/n
равна дроби r
/s
. Про отношение равенства дробей говорят, что оно является отношением эквивалентности
. Определение. Отношение R на множестве X называется отношением эквивалентности, если оно одновременно обладает свойствами рефлексивности, симметричности и транзитивности.
Примерами отношений эквивалентности могут служить отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными). Почему в математике выделили этот вид отношений? Рассмотрим отношение равенства дробей, заданное на множестве X
= {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} (Рис.106). Видим, что множество разбилось на три подмножества: {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х,
т.е. имеем разбиение множества X
на классы. Это не случайно. Вообще, если на множестве X задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества (классы эквивалентности).
Так, мы установили, что отношению равенства на множестве дробей {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей. Верно и обратное утверждение: если какое-либо отношение, заданное на множестве X, порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Рассмотрим, например, на множестве X =
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно порождает разбиение множества X
на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 1, 4, 7, 10), и в третий - все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множеством X.
Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве X,
является отношением эквивалентности. Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается и классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множество отрезков разбивается на классы равных отрезков (см. рис. 99). Отношению подобия соответствует разбиение множества треугольников на классы подобных треугольников. Итак, имея отношение эквивалентности на некотором множестве, мы можем разбить это множество на классы. Но можно поступить и наоборот: сначала разбить множество на классы, а затем определить отношение эквивалентности, считая, что два элемента эквивалентны тогда и только тогда, когда они принадлежат одному классу рассматриваемого разбиения. Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему? Во-первых
, эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {1/2, 2/4, 3/6} неразличимы с точки зрения отношения равенства, и дробь 3/6 может быть заменена другой, например 1/2. И эта замена не изменит результата вычислений. Во-вторых
, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. Определение класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность отдельных представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. Свойства, присущие некоторому классу, рассматриваются на одном его представителе. В-третьих
, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные между собой прямые. Вообще любое понятие, которым оперирует человек, представляет собой некоторый класс эквивалентности. «Стол», «дом», «книга» - все эти понятия являются обобщенными представлениями о множестве конкретных предметов, имеющих одинаковое назначение. Другим важным видом отношений являются отношения порядка.
Определение. Отношение R на множестве X называется отношением порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности
.
Примерами отношений порядка могут служить: отношение «меньше» на множестве натуральных чисел; отношение «короче» на множестве отрезков, поскольку они антисимметричны и транзитивны. Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка.
Например, отношение «меньше» на множестве натуральных чисел является отношением линейного порядка, так как обладает свойствами антисимметричности, транзитивности и связанности. Определение. Множество X называется упорядоченным, если на нем задано отношение порядка.
Так, множество N натуральных чисел можно упорядочить, если задать на нем отношение «меньше». Если отношение порядка, заданное на множестве X,
обладает свойством связанности, то говорят, что оно линейно упорядочивает
множество X.
Например, множество натуральных чисел можно упорядочить и с помощью отношения «меньше», и с помощью отношения «кратно» - оба они являются отношениями порядка. Но отношение «меньше», в отличие от отношения «кратно», обладает еще и свойством связанности. Значит, отношение «меньше» упорядочивает множество натуральных чисел линейно. Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка. Рассмотрим на множестве дробей X = { } отношение равенства. Это отношение: Рефлексивно, так как всякая дробь равна сама себе; Симметрично, так как из того, что дробь равна дроби , следует, что дробь равна дроби ; Транзитивно, так как из того, что дробь равна дроби и дробь равна дроби , следует, что дробь равна дроби . Про отношение равенства дробей говорят, что оно является отношением эквивалентности. Определение. Отношение R на множестве X называется отношением эквивалентности, если оно одновременно обладает свойствами рефлексивности, симметричности и транзитивности
. Примерами отношений эквивалентности могут служить отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными). Почему в математике выделили этот вид отношений? Рассмотрим отношения равенства дробей, заданного на множестве X = { }. (Рис.7). Видим, что множество разбилось на три подмножества: Вообще если на множестве X задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества (классы эквивалентности).
Так, мы установили, что отношению равенства на множестве дробей X = { } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей. Верно и обратное утверждение: если какое-либо отношение, заданное на множестве X, порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Рассмотрим, например, на множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно порождает разбиение множества X на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 1, 4, 7, 10), и в третий - все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множеством X. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве X, является отношением эквивалентности. Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается и классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множество отрезков разбивается на классы равных отрезков (см. рис. 4). Отношению подобия соответствует разбиение множества треугольников на классы подобных треугольников. Итак, имея отношение эквивалентности на некотором множестве, мы можем разбить это множество на классы. Но можно поступить и наоборот: сначала разбить множество на классы, а затем определить отношение эквивалентности, считая, что два элемента эквивалентны тогда и только тогда, когда они принадлежат одному классу рассматриваемого разбиения. Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему? Во-первых
, эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например И эта замена не изменит результата вычислений. Во-вторых
, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. Определение класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность отдельных представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. Свойства, присущие некоторому классу, рассматриваются на одном его представителе. В-третьих
, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные между собой прямые. Вообще любое понятие, которым оперирует человек, представляет собой некоторый класс эквивалентности. «Стол», «дом», «книга» - все эти понятия являются обобщенными представлениями о множестве конкретных предметов, имеющих одинаковое назначение. Другим важным видом отношений являются отношения порядка. Оно определяется следующим образом. Определение. Отношение R на множестве X называется отношением порядка, если оно одновременно обладает свойством антисимметричности и транзитивности.
Примерами отношений порядка могут служить: отношения «меньше» на множестве натуральных чисел; отношения «короче» на множестве отрезков, поскольку они антисимметричны и транзитивны. Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка. Например, отношение «меньше» на множестве натуральных чисел является отношением линейного порядка, так как обладает свойствами антисимметричности, транзитивности и связанности. Определение. Множество X называется упорядоченным, если на нем задано отношение порядка.
Так, множество N натуральных чисел можно упорядочить, если задать на нем отношение «меньше». Если отношение порядка, заданное на множестве X, обладает свойством связанности, то говорят, что оно линейно упорядочивает множество X. Например, множество натуральных чисел можно упорядочить и с помощью отношения «меньше», и с помощью отношения «кратно» - оба они являются отношениями порядка. Но отношение «меньше», в отличие от отношения «кратно», обладает еще и свойством связанности. Значит, отношение «меньше» упорядочивает множество натуральных чисел линейно. Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.
. То есть 
.
Эти подмножества не пересекаются, а их объединение совпадает с множеством X, т е имеем разбиение множества X на классы. Это не случайно.