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

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

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

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

Формально, если задано множество и отношение эквивалентности на классе эквивалентности элемента в обозначается или, что то же самое, подчеркивается его отношение эквивалентности. Определение отношений эквивалентности подразумевает, что классы эквивалентности образуют смысловое разделение , что каждый элемент множества принадлежит ровно одному классу эквивалентности. Множество классов эквивалентности иногда называют фактормножеством или факторпространством by и обозначают ${\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}$

Из свойств предыдущего раздела следует, что if — отношение эквивалентности на множестве и и — два элемента следующих утверждений эквивалентны: ${\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. Девлин 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), Доказательство, логика и гипотеза: набор инструментов математика , Фриман, ISBN 978-0-7167-3050-7

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

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

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

• СМИ, связанные с классами эквивалентности, на Викискладе?