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

Математическая концепция

Конгруэнтность — пример отношения эквивалентности. Два самых левых треугольника конгруэнтны, тогда как третий и четвертый треугольники не конгруэнтны ни одному другому треугольнику, показанному здесь. Таким образом, первые два треугольника находятся в одном классе эквивалентности, тогда как третий и четвертый треугольники находятся каждый в своем собственном классе эквивалентности.

В математике , когда элементы некоторого множества имеют понятие эквивалентности (формализованное как отношение эквивалентности ), то можно естественным образом разбить множество на классы эквивалентности . Эти классы эквивалентности построены так, что элементы и принадлежат к одному и тому же классу эквивалентности тогда и только тогда , когда они эквивалентны. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle a}$ ${\displaystyle b}$

Формально, если задано множество и отношение эквивалентности на классе эквивалентности элемента в обозначается или, что то же самое, чтобы подчеркнуть его отношение эквивалентности Определение отношений эквивалентности подразумевает, что классы эквивалентности образуют раздел смысла , что каждый элемент множества принадлежит ровно одному классу эквивалентности. Множество классов эквивалентности иногда называют фактор-множеством или фактор - пространством по и обозначается как ${\displaystyle S}$ ${\displaystyle \,\sim \,}$ ${\displaystyle S,}$ ${\displaystyle a}$ ${\displaystyle S}$ ${\displaystyle [a]}$ ${\displaystyle [a]_{\sim }}$ ${\displaystyle \sim .}$ ${\displaystyle S,}$ ${\displaystyle S}$ ${\displaystyle \,\sim \,,}$ ${\displaystyle S/{\sim }.}$

Когда множество имеет некоторую структуру (например, групповую операцию или топологию ) и отношение эквивалентности совместимо с этой структурой, фактор-множество часто наследует похожую структуру от своего родительского множества. Примерами служат фактор-пространства в линейной алгебре , фактор-пространства в топологии , фактор-группы , однородные пространства , фактор-кольца , фактор-моноиды и фактор-категории . ${\displaystyle S}$ ${\displaystyle \,\sim \,}$

Определение и обозначения

Отношение эквивалентности на множестве — это бинарное отношение , удовлетворяющее трем свойствам: ^[1] ${\displaystyle X}$ ${\displaystyle \,\sim \,}$ ${\displaystyle X}$

• ${\displaystyle a\sim a}$для всех ( рефлексивность ), ${\displaystyle a\in X}$
• ${\displaystyle a\sim b}$подразумевает для всех ( симметрия ), ${\displaystyle b\sim a}$ ${\displaystyle a,b\in X}$
• если и то для всех ( транзитивность ). ${\displaystyle a\sim b}$ ${\displaystyle b\sim c}$ ${\displaystyle a\sim c}$ ${\displaystyle a,b,c\in X}$

Класс эквивалентности элемента определяется как ^[2] ${\displaystyle a}$

${\displaystyle [a]=\{x\in X:a\sim x\}.}$

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

Множество всех классов эквивалентности относительно отношения эквивалентности обозначается как и называется по модулю (или ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle X/R,}$ ${\displaystyle X}$ ${\displaystyle R}$фактор-множество по).^[3]Сюръективноеотображениеизна,которое отображает каждый элемент в его класс эквивалентности, называется ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle x\mapsto [x]}$ ${\displaystyle X}$ ${\displaystyle X/R,}$каноническая сюръекция , иликаноническая проекция.

Каждый элемент класса эквивалентности характеризует класс и может быть использован для его представления . Когда такой элемент выбран, он называется представителем класса. Выбор представителя в каждом классе определяет инъекцию из в X . Поскольку его композиция с канонической сюръекцией является тождеством такой инъекции, она называется секцией , если использовать терминологию теории категорий . ${\displaystyle X/R}$ ${\displaystyle X/R,}$

Иногда есть раздел, который более «естественен», чем другие. В этом случае представители называются каноническими представителями . Например, в модульной арифметике для каждого целого числа m, большего 1 , сравнение по модулю m является отношением эквивалентности целых чисел, для которого два целых числа a и b эквивалентны — в этом случае говорят «сравнение» — если m делится , это обозначается Каждый класс содержит уникальное неотрицательное целое число, меньшее , и эти целые числа являются каноническими представителями. ${\displaystyle a-b;}$ ${\textstyle a\equiv b{\pmod {m}}.}$ ${\displaystyle m,}$

Использование представителей для представления классов позволяет избежать явного рассмотрения классов как множеств. В этом случае каноническая сюръекция, которая отображает элемент в его класс, заменяется функцией, которая отображает элемент в представителя его класса. В предыдущем примере эта функция обозначается и производит остаток от евклидова деления a на m . ${\displaystyle a{\bmod {m}},}$

Характеристики

Каждый элемент из является членом класса эквивалентности Каждые два класса эквивалентности и либо равны, либо не пересекаются . Следовательно, множество всех классов эквивалентности из образует разбиение из : каждый элемент из принадлежит одному и только одному классу эквивалентности. ^[4] Наоборот, каждое разбиение из происходит из отношения эквивалентности таким образом, согласно которому тогда и только тогда, когда и принадлежат одному и тому же множеству разбиения. ^[5] ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle [x].}$ ${\displaystyle [x]}$ ${\displaystyle [y]}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle x\sim y}$ ${\displaystyle x}$ ${\displaystyle y}$

Из свойств предыдущего раздела следует, что если — отношение эквивалентности на множестве и и — два элемента следующих утверждений эквивалентны: ${\displaystyle \,\sim \,}$ ${\displaystyle X,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X,}$

• ${\displaystyle x\sim y}$
• ${\displaystyle [x]=[y]}$
• ${\displaystyle [x]\cap [y]\neq \emptyset .}$

Примеры

• Пусть — множество всех прямоугольников на плоскости, а отношение эквивалентности «имеет ту же площадь, что и», тогда для каждого положительного действительного числа будет существовать класс эквивалентности всех прямоугольников, имеющих площадь ^[6] ${\displaystyle X}$ ${\displaystyle \,\sim \,}$ ${\displaystyle A,}$ ${\displaystyle A.}$
• Рассмотрим отношение эквивалентности по модулю 2 на множестве целых чисел , такое, что тогда и только тогда, когда их разность является четным числом . Это отношение порождает ровно два класса эквивалентности: один класс состоит из всех четных чисел, а другой класс состоит из всех нечетных чисел. Используя квадратные скобки вокруг одного члена класса, чтобы обозначить класс эквивалентности в этом отношении, и все представляют один и тот же элемент ^[2] ${\displaystyle \mathbb {Z} ,}$ ${\displaystyle x\sim y}$ ${\displaystyle x-y}$ ${\displaystyle [7],[9],}$ ${\displaystyle [1]}$ ${\displaystyle \mathbb {Z} /{\sim }.}$
• Пусть — множество упорядоченных пар целых чисел с ненулевым значением и зададим отношение эквивалентности на таком, что тогда и только тогда, когда класс эквивалентности пары можно отождествить с рациональным числом , и это отношение эквивалентности и его классы эквивалентности можно использовать для формального определения множества рациональных чисел. ^[7] Эту же конструкцию можно обобщить на поле дробей любой целочисленной области . ${\displaystyle X}$ ${\displaystyle (a,b)}$ ${\displaystyle b,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle X}$ ${\displaystyle (a,b)\sim (c,d)}$ ${\displaystyle ad=bc,}$ ${\displaystyle (a,b)}$ ${\displaystyle a/b,}$
• Если состоит из всех прямых, скажем, в евклидовой плоскости , и означает, что и являются параллельными прямыми , то множество прямых, которые параллельны друг другу, образуют класс эквивалентности, пока прямая считается параллельной самой себе . В этой ситуации каждый класс эквивалентности определяет точку на бесконечности . ${\displaystyle X}$ ${\displaystyle L\sim M}$ ${\displaystyle L}$ ${\displaystyle M}$

Графическое представление

График примера эквивалентности с 7 классами

Неориентированный граф может быть связан с любым симметричным отношением на множестве , где вершины являются элементами и двумя вершинами и соединены тогда и только тогда, когда Среди этих графов есть графы отношений эквивалентности. Эти графы, называемые кластерными графами , характеризуются как графы, в которых связанные компоненты являются кликами . ^[2] ${\displaystyle X,}$ ${\displaystyle X,}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s\sim t.}$

Инварианты

Если — отношение эквивалентности на и — свойство элементов такое, что всякий раз, когда истинно, если истинно, то свойство называется инвариантом или хорошо определенным относительно отношения ${\displaystyle \,\sim \,}$ ${\displaystyle X,}$ ${\displaystyle P(x)}$ ${\displaystyle X}$ ${\displaystyle x\sim y,}$ ${\displaystyle P(x)}$ ${\displaystyle P(y)}$ ${\displaystyle P}$ ${\displaystyle \,\sim \,,}$ ${\displaystyle \,\sim .}$

Частный случай часто возникает, когда есть функция из в другое множество ; если всякий раз, когда тогда говорят, что это класс инвариантен относительно или просто инвариантен относительно Это происходит, например, в теории характеров конечных групп. Некоторые авторы используют «совместимый с » или просто «уважает » вместо «инвариантен относительно ». ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f\left(x_{1}\right)=f\left(x_{2}\right)}$ ${\displaystyle x_{1}\sim x_{2},}$ ${\displaystyle f}$ ${\displaystyle \,\sim \,,}$ ${\displaystyle \,\sim .}$ ${\displaystyle \,\sim \,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle \,\sim \,}$

Любая функция является инвариантом класса относительно , ​​согласно которому тогда и только тогда, когда Класс эквивалентности представляет собой множество всех элементов, в которых выполняется отображение на , то есть класс является обратным образом Это отношение эквивалентности известно как ядро ${\displaystyle f:X\to Y}$ ${\displaystyle \,\sim \,,}$ ${\displaystyle x_{1}\sim x_{2}}$ ${\displaystyle f\left(x_{1}\right)=f\left(x_{2}\right).}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle f(x),}$ ${\displaystyle [x]}$ ${\displaystyle f(x).}$ ${\displaystyle f.}$

В более общем смысле функция может отображать эквивалентные аргументы (в соответствии с отношением эквивалентности на ) в эквивалентные значения (в соответствии с отношением эквивалентности на ). Такая функция является морфизмом множеств, снабженных отношением эквивалентности. ${\displaystyle \sim _{X}}$ ${\displaystyle X}$ ${\displaystyle \sim _{Y}}$ ${\displaystyle Y}$

Факторное пространство в топологии

В топологии факторпространство — это топологическое пространство, образованное на множестве классов эквивалентности отношения эквивалентности на топологическом пространстве с использованием топологии исходного пространства для создания топологии на множестве классов эквивалентности.

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

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

Нормальная подгруппа топологической группы, действующая на группу посредством действия трансляции, является факторпространством в смысле топологии, абстрактной алгебры и групповых действий одновременно.

Хотя этот термин может быть использован для любого набора классов эквивалентности отношения эквивалентности, возможно, с дополнительной структурой, цель использования этого термина, как правило, состоит в том, чтобы сравнить этот тип отношения эквивалентности на множестве либо с отношением эквивалентности, которое индуцирует некоторую структуру на множестве классов эквивалентности из структуры того же вида на или с орбитами группового действия. Как смысл структуры, сохраняемой отношением эквивалентности, так и изучение инвариантов при групповых действиях приводят к определению инвариантов отношений эквивалентности, данному выше. ${\displaystyle X,}$ ${\displaystyle X,}$

Смотрите также

• Эквивалентное разбиение — метод разработки тестовых наборов при тестировании программного обеспечения , основанный на разделении возможных входных данных программы на классы эквивалентности в соответствии с поведением программы на этих входных данных.
• Однородное пространство , факторпространство групп Ли
• Отношение частичной эквивалентности  – Математическая концепция для сравнения объектов.
• Фактор по отношению эквивалентности  – Обобщение классов эквивалентности на теорию схем
• Сетоид  – Математическая конструкция множества с отношением эквивалентности
• Трансверсальный (комбинаторика)  – множество, пересекающее каждое из семейства множеств.

Примечания

1. Девлин 2004, стр. 122.
2. Devlin 2004, стр. 123.
3. Вольф 1998, стр. 178
4. Мэддокс 2002, стр. 74, Теория 2.5.15
5. Авелсгаард 1989, стр. 132, Теория 3.16
6. Авелсгаард 1989, стр. 127
7. Мэддокс 2002, стр. 77–78.

Ссылки

• Авелсгаард, Кэрол (1989), Основы высшей математики , Скотт Форесман, ISBN 0-673-38152-8
• Девлин, Кит (2004), Множества, функции и логика: Введение в абстрактную математику (3-е изд.), Chapman & Hall/CRC Press, ISBN 978-1-58488-449-1
• Мэддокс, Рэндалл Б. (2002), Математическое мышление и письмо , Harcourt/Academic Press, ISBN 0-12-464976-9
• Вольф, Роберт С. (1998), Доказательство, логика и гипотеза: набор инструментов математика , Freeman, ISBN 978-0-7167-3050-7

Дальнейшее чтение

• Сандстром (2003), Математическое обоснование: написание и доказательство , Prentice-Hall
• Смит; Эгген; Сент-Андре (2006), Переход к высшей математике (6-е изд.), Томсон (Брукс/Коул)
• Шумахер, Кэрол (1996), Глава нулевая: основные понятия абстрактной математики , Addison-Wesley, ISBN 0-201-82653-4
• О'Лири (2003), Структура доказательства: с логикой и теорией множеств , Prentice-Hall
• Лэй (2001), Анализ с введением в доказательство , Prentice Hall
• Мораш, Рональд П. (1987), Мост к абстрактной математике , Random House, ISBN 0-394-35429-X
• Гилберт; Ванстоун (2005), Введение в математическое мышление , Пирсон Прентис-Холл
• Флетчер; Патти, Основы высшей математики , PWS-Kent
• Иглевич; Стойл, Введение в математическое мышление , Макмиллан
• D'Angelo; West (2000), Математическое мышление: Решение проблем и доказательства , Prentice Hall
• Купиллари , «Основы доказательств» , Уодсворт
• Бонд, Введение в абстрактную математику , Брукс/Коул
• Барнье; Фельдман (2000), Введение в высшую математику , Prentice Hall
• Эш, Учебник по абстрактной математике , MAA

Внешние ссылки

• Медиа, связанные с классами эквивалентности на Wikimedia Commons