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

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

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

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

В математике , когда элементы некоторого множества $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

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

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