Является ли отношение отношением эквивалентности. Бинарные отношения — MT1102: Линейная алгебра (введение в математику) — Бизнес-информатика

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

Отношения эквивалентности и порядка

Напомним, что бинарным отношением на множестве называется подмножество ; вместо часто пишут .

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

Имеет место следующее очевидное, но часто используемое утверждение:

Теорема 11 . (а) Если множество разбито в объединение непересекающихся подмножеств, то отношение " лежать в одном подмножестве" является отношением эквивалентности.

(б) Всякое отношение эквивалентности получается описанным способом из некоторого разбиения.

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

Докажем, что для двух различных , такие множества либо не пересекаются, либо совпадают. Пусть они пересекаются, то есть имеют общий элемент . Тогда и , откуда ( симметричность ) и ( транзитивность ), а также ( симметричность ). Поэтому для любого из следует ( транзитивность ) и наоборот.

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

78. Покажите, что требования симметричности и транзитивности можно заменить одним: (при сохранении требования рефлексивности).

79. Сколько различных отношений эквивалентности существует на множестве ?

80. На множестве задано два отношения эквивалентности, обозначаемые и , имеющие и классов эквивалентности соответственно. Будет ли их пересечение отношением эквивалентности? Сколько у него может быть классов? Что можно сказать про объединение отношений ?

81. (Теорема Рамсея) Множество всех - элементных подмножеств бесконечного множества разбито на классов (, - натуральные числа). Докажите, что найдется бесконечное множество , все - элементные подмножества которого принадлежат одному классу.

(При это очевидно: если бесконечное множество разбито на конечное число классов , то один из классов бесконечен. При и утверждение можно сформулировать так: из бесконечного множества людей можно выбрать либо бесконечно много попарно знакомых, либо бесконечно много попарно незнакомых. Конечный вариант этого утверждения - о том, что среди любых шести людей есть либо три попарно знакомых, либо три попарно незнакомых, - известная задача для школьников.)

Множество классов эквивалентности называют фактор - множеством множества по отношению эквивалентности . (Если отношение согласовано с дополнительными структурами на , получаются фактор - группы, фактор - кольца и т.д)

Отношения эквивалентности нам не раз еще встретятся, но сейчас наша основная тема - отношения порядка.

Бинарное отношение на множестве называется отношением частичного порядка , если выполнены такие свойства:

(Следуя традиции, мы используем символ (а не букву) как знак отношения порядка.) Множество с заданным на нем отношением частичного порядка называют частично упорядоченным .

Говорят, что два элемента частично упорядоченного множества сравнимы , если или . Заметим, что определение частичного порядка не требует, чтобы любые два элемента множества были сравнимы. Добавив это требование, мы получим определение линейного порядка (линейно упорядоченного множества ).

Приведем несколько примеров частичных порядков:

  • Числовые множества с обычным отношением порядка (здесь порядок будет линейным).
  • На множестве всех пар действительных чисел можно ввести частичный порядок , считая, что , если и . Этот порядок уже не будет линейным: пары и не сравнимы.
  • На множестве функций с действительными аргументами и значениями можно ввести частичный порядок , считая, что , если при всех . Этот порядок не будет линейным.
  • На множестве целых положительных чисел можно определить порядок, считая, что , если делит . Этот порядок тоже не будет линейным.
  • Отношение " любой простой делитель числа является также и делителем числа " не будет отношением порядка на множестве целых положительных чисел (оно рефлексивно и транзитивно, но не антисимметрично).
  • Пусть - произвольное множество. Тогда на множестве всех подмножеств множества отношение включения будет частичным порядком.
  • На буквах русского алфавита традиция определяет некоторый порядок (). Этот порядок линеен - про любые две буквы можно сказать, какая из них раньше (при необходимости заглянув в словарь).
  • На словах русского алфавита определен лексикографический порядок (как в словаре). Формально определить его можно так: если слово является началом слова , то (например, ). Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке, и будет меньше. Этот порядок также линеен (иначе что бы делали составители словарей?).
  • Отношение равенства () также является отношением частичного порядка , для которого никакие два различных элемента не сравнимы.
  • Приведем теперь бытовой пример. Пусть есть множество картонных коробок. Введем на нем порядок, считая, что , если коробка целиком помещается внутрь коробки (или если и - одна и та же коробка). В зависимости от набора коробок этот порядок может быть или не быть линейным.

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. Отношение с на множестве М называется отношением нестрогого порядка если оно может быть представлено в виде:

где строгий порядок на М, а Е -диагональное отношение.

ОТНОШЕНИЯ

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

x А, у А отношение Г = {(x,y)| P(x,y)}, P(x,y) какое-то утверждение (предикат).

Если (x,y) Г, то говорят, что х находятся в отношении Г к у .

Например, иметь одинаковый остаток от деления (для чисел), быть на одинаковом расстоянии от прямой (для точек), родственные отношения или соседские отношения (для множества людей).

Более строгое определение:

Бинарным отношением называется два множества:

1) несущее множество А,

2) множество пар Г={(x,y)| x A, y A}, являющегося подмножеством квадрата несущего множества.

n-местное отношение, или n-арное (тернарное, кватернарное, …) отношение – это несущее множество А и множества кортежной размерностью n ,являющегося подмножеством множества А n .

Пример тернарного отношения: входить в «тройку игроков».

Если под отношением понимать просто множество кортежей (без несущего множества), то можно использовать все законы теории множеств. Универсальным множеством будет квадрат несущего множества, то есть множество всех возможных кортежей (когда каждый элемент находится в отношении к любому другому элементу).

Отношение можно определить также как двухместный предикат предметных переменных х, у , принимающего значение «истина», если (х, у) Г и значение «ложь», если не принадлежит.

Обозначения: (х, у) Г, у = Г(x), у = Гx или просто xГу , например, отношение равенства(х = у) , отношение порядка(х < у) .

Если (х, у) Г , то xГу принимает значение «истина», иначе – «ложь».

Если отношения заданы на дискретном множестве, их можно записывать в виде матрицы

A i , j =

Отношение – частный случай соответствия, для него можно ввести обратные отношения, композицию отношений:

Г -1 ={(y,x)| (x,y) Г}, Г ◦ Δ = {(x,z) | y ((x,y) Г &(y,z Δ))}.

Вводят понятие «единичного элемента» Δ 0 = {(x,x)} – «быть в отношении к самому себе». В матричном представлении это будет - главная диагональ).

Свойства бинарных отношений

1 Рефлексивность – «находиться в отношении к самому себе»

хГх – истина (например, отношения х=x, х≤x, х≥x ).

2 Антирефлексивность - «не быть в отношении к самому себе»

хГx - ложь (например, отношения х≠x, хх ).

Если множество не «рефлексивно», то это еще не значит что оно «антирефлексивно».

3 Симметричность «независимость от того, какой элемент первый, какой второй»

хГу – истина → уГх – истина (например, отношения х=у, х≠у ).

4 Антисимметричность «не превосходить»

(хГу – истина) & (yГх – истина) → (х=у) (например, отношения х≤у, х≥у ).

5 Асимметричность (несимметричность) «превосходить»

хГу – истина → уГх –ложь (например, отношения х<у, х>у ).

6. Транзитивность «передаточность»

(хГу – истина) & (yГz – истина) → (хГz – истина) (например, отношения х=у, х<у, х>у, х≤у, х≥у , отношение х≠у транзитивностью не обладает).

СПЕЦИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ

Рассмотрим «отношение эквивалентности», «отношение нестрогого порядка», «отношение строгого порядка» и «отношение доминирования».

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

Отношением эквивалентности называется рефлексивное (х~x) , симметричное ((х~y)=(y~x)) , транзитивное ((х~у)&(y~z)→(х~z)) отношение.

Примеры: равенство, тождественность, эквивалентность множеств, эквивалентность логических высказываний, подобие геометрических фигур, параллельность прямых, а вот перпендикулярность прямых - не является отношением эквивалентности.

Подмножество элементов, эквивалентных одному элементу, называется классом эквивалентности или смежным классом.

Любой элемент из класса называется представителем класса.

Свойства.

Все элементы в классе эквивалентны между собой.

Элементы из разных классов не эквивалентны.

Один элемент может входить только в свой класс.

Все множество можно представить как объединение классов.

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

Индекс разбиения – число классов эквивалентности.

Фактор-множество относительно отношения эквивалентности - это множество всех классов или представителей класса.

Мощность фактора-множества равна индексу разбиения.

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

Отношением порядка называют два вида бинарных отношений.

Отношениемнестрогого порядка называется рефлексивное (х≥x) , антисимметричное ((x≤y)&(y≤x)→ (x=y)) , транзитивное ((х≥у)&(y≥z)→(х≥z)) отношение .

Говорят, что на множестве установлен нестрогий порядок. В понятия ≤ , ≥ вкладывают более широкий смысл: не хуже – не лучше, не раньше – не позже и так далее. В теории множеств пример нестрого порядка - нестрогое включение (быть подмножеством другого множества0.

Отношениемстрогого порядка называется антирефлексивное ((х, антисимметричное ((x, транзитивное

((х>у)&(y отношение .

Говорят, что на множестве установлен строгий порядок. В понятия < , > вкладывают более широкий смысл: хуже – лучше, раньше – позже и так далее. В теории множеств пример строго порядка - строгое включение (быть подмножеством другого множества и при этом не быть равным ему).

Упорядоченные множества

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

Множество действительных или целых чисел: классические примеры упорядоченного множества.

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

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

Классы эквивалентных элементов и их свойства

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%a%% — некоторый элемент из %%M%%. Рассмотрим множество всех элементов из %%M%%, находящихся в отношении %%R%% к элементу %%a%%.

Классом эквивалентности %%M_a%%

называется множество всех элементов %%M%%, находящихся в отношении %%R%% к элементу %%a%%, то есть множество

$$ M_a = \{x \in M: x~R~a\}. $$

Пример

Пусть %%M%% — множество всех жителей России и %%R%% — отношение эквивалентности «проживать в одном городе». Найти классы эквивалентных элементов %%M_a%% для %%a \in M%%.

Класс элементов, эквивалентных элементу %%a%%, имеет вид: $$ M_a = \{x \in M: x \text{ проживает в одном городе с человеком } a\} $$

В зависимости от элемента %%a%% получаем несколько классов эквивалентности. Например, класс эквивалентности жителей Москвы или Санкт-Петербурга.

Свойства классов эквивалентности

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%M_a, M_b, \dotsc, M_z, \dotsc%% — все классы эквивалентности для отношения %%R%%. Тогда эти классы имеют следующие свойства.

Свойство 1

Для любого элемента %%a \in M%% выполняется условие $$ a \in M_a $$

Действительно, по определению, класс %%M_a = \{x \in M: x~R~a\}%%. Тогда для элемента %%a%% должно выполняться условие %%a \in M_a \leftrightarrow a~R~a%%, которое выполняется в связи с тем, что отношение %%R%% рефлексивно по определению отношения эквивалентности. Следовательно, %%a \in M_a%%.

Как следствие этого свойства можно сказать, что всякий класс %%M_a%% является непустым множеством.

Свойство 2

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Классы %%M_a%% и %%M_b%% равны тогда и только тогда, когда элемент %%a%% находится в отношении %%R%% к элементу %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$

Свойство 3

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Тогда классы %%M_a%% и %%M_b%% не имеют общих элементов. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$

Свойство 4

Объединение всех классов эквивалентности множества %%M%% равно множеству %%M%%. $$ \bigcup_{a\in M}{M_a} = M. $$

Разбиение множества

Совокупностью подмножеств %%M_i%%, где %%i \in I%% (множеству индексов), множества %%M%% называется разбиением множества %%M%% если выполняются следующие условия:

  1. Каждое из подмножеств %%M_i%% непусто.
  2. Объединение всех подмножеств %%M_i%% равно множеству %%M%%.
  3. Два различных подмножества %%M_i%% и %%M_j%%, где %%i \neq j%%, не имеют общих элементов.

Теорема. Пусть %%R%% — отношение эквивалентности на множестве %%M%%. Тогда совокупность классов эквивалентности множества %%M%% образует его разбиение.

Действительно, если в качестве подмножеств %%M_i%% взять классы эквивалентности %%M_a%%, то все три условия выполняются:

  1. Каждый класс эквивалентности является непустым множеством, согласно свойству 1 .
  2. Объединение всех классов эквивалентности есть множество %%M%%, согласно свойству 4 .
  3. Два различных класса эквивалентности не имеют общих элементов, согласно свойству 3 .

Все условия определения разбиения выполнены. Следовательно классы эквивалентности есть разбиение множества %%M%%.

Примеры

Пусть дано множество %%M = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \}%%, тогда разбиением этого множества могут быть следующие совокупности множеств:

  1. %%A_1 = \{1, 2, 3\}, A_2 = \{4, 5, 6, 7\}, A_3 = \{8, 9, 0 \}%%.
  2. %%B_1 = \{0, 7, 2\}, B_2 = \{1, 3, 5 \}, B_3 = \{4, 6, 8, 9\}%%.

Но следующие совокупности не являются разбиением:

  1. %%C_1 = \{1, 2, 3\}, C_2 = \{4, 5, 6, 7\}, C_3 = \{8, 9, 0, 3\}%%.
  2. %%D_1 = \{0, 7, 2\}, D_2 = \{1, 3, 5 \}, D_3 = \{4, 6, 8, 9\}, D_4 = \varnothing%%.
  3. %%E_1 = \{0, 1, 2\}, E_2 = \{3, 4, 5\}, E_3 = \{6, 7, 8\}%%.

Совокупность множеств %%C_i%% не является разбиением, т.к. оно не удовлетворяет условию 3 разбиения множеств: множества %%C_1%% и %%C_3%% имеют общий элемент %%3%%.

Совокупность множеств %%D_i%% не является разбиением, т.к. оно не удовлетворяет условию 1 разбиения множеств: множество %%D_4%% пусто.

Совокупность множеств %%E_i%% не является разбиением, т.к. оно не удовлетворяет условию 2 разбиения множеств: объединение множеств %%E_1, E_2%% и %%E_3%% не образует множество %%M%%.

Отношение эквивалентности – это отношение, обладающее свойствами рефлексивности, симметричности и транзитивности. Обозначается знаком ~, записьа ~ в означает, что а эквивалентно в .

В соответствии с определением для отношения эквивалентности выполняются свойства:

Примеры отношений эквивалентности – равенство, подобие треугольников .

Используя отношение эквивалентности можно проводить разбиение множества на классы эквивалентности.

Класс эквивалентности , порожденный элементом – множество всех элементов из , вступающих с в отношение эквивалентности. Класс эквивалентности определяется так:

, для
подбираются элементы
, находящиеся в соответствии с элементомх .

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

Фактор-множества множества по отношению эквивалентности φ – множество всех различных классов эквивалентности, обозначаемое А / φ .

Индекс разбиения , порожденный отношением φ – это мощность фактор-множества А / φ .

Пример 2 .11.

а) Отношение равенства
на любом множестве является отношением эквивалентности.

Равенство – это минимальное отношение эквивалентности в том смысле, что при удаление любой пары из
(то есть любой единицы на диагонали матрицы
) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентностью.

б) Утверждения вида
или
, состоящие из формул, соединенных знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций. Это отношение обычно называется отношением равносильности и определяется следующим образом: формулы равносильны, если они задают одну и ту же функцию. Равносильность, хотя и обозначается знаком =, отличается от отношения равенства
, так как оно может выполняться для различных формул. Отношение
для формул – это совпадение формул по написанию. Оно называетсяграфическим равенством .

в) Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются конгруэнтными (равными ) , если они при наложении совпадают, то есть могут быть переведены друг в друга путем некоторого перемещения . Конгруэнтность является отношением эквивалентности на множестве треугольников.

г) Отношение «иметь один и тот же остаток от деления на 9» является эквивалентностью на
. Это отношение выполняетсядля пар (12, 21), (17, 36) и не выполняется для пар (11, 13), (19, 29).

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

    она образует разбиение , то есть классы попарно не пересекаются ;

    любые два элемента из одного класса эквивалентны ;

    любые два элемента из разных классов неэквивалентны .

Все эти свойства вытекают из рефлексивности, симметричности и транзитивности . Действительно, если бы классы, например и, пересекались, то они имели бы общий элемент, эквивалентныйи, но тогда из-за транзитивности было бы
, что противоречит построению. Аналогично доказываются другие два свойства.

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

Пример. 2.12.

а) Все классы эквивалентности по отношению равенства
состоят из одного элемента.

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

в) Разбиение
по отношению «иметь общий остаток от деления на 7» имеет конечный индекс 7 и состоит из 7 счетных классов: 0, 7, 14, …; 2, 9, 16, …; …; 6, 13, 20, …



Похожие статьи