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

Эта статья об эквивалентности в математике. Чтобы узнать об эквивалентности в музыке, см. класс эквивалентности (музыка) .

«Карта коэффициентов» перенаправляется сюда. Для карты отношений в топологии см. карту отношений (топология) .

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

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

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

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

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

Отношение эквивалентности на множестве $X$ это бинарное отношение $\,\sim \,$ на $X$ удовлетворяющий трем свойствам:

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

Класс эквивалентности элемента $a$ определяется как

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

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

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

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

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

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

Свойства

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

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

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

Примеры

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

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

Основная статья: Кластерный граф

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

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

Инварианты

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Авелсгаард, Кэрол (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

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

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