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

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

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

Формально дано множество $S$ и отношение эквивалентности $~$ на $S$ , то класс эквивалентности из элемента $а$ в $S$ , обозначаемый , ^[+1]^[2] является множество ^[3] ${\ Displaystyle [а]}$

{\ displaystyle \ {x \ in S \ mid x \ sim a \}}

элементов, которые эквивалентны $a$ . Это может быть доказано, из определяющих свойств отношений эквивалентности, что классы эквивалентности образуют разбиение на $S$ . Этот раздел-множество классов эквивалентности, иногда называется множество фактор или фактор - пространство в $S$ по $~$ , и обозначается через $S / ~$ .

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

Примеры [ править ]

Если $X$ - это множество всех автомобилей, а $~$ - отношение эквивалентности "имеет тот же цвет, что и", то один конкретный класс эквивалентности будет состоять из всех зеленых автомобилей, и $X / ~$ может быть естественным образом отождествлен с набором всех цветов автомобилей. .
Пусть $X$ множество всех прямоугольников на плоскости и $\$ отношение эквивалентности «имеет такую же площадь , как», то для каждого положительного действительного числа А , будет класс эквивалентности всех прямоугольников , которые имеют площадь A . ^[4]
Рассмотрим по модулю отношения эквивалентности 2 на множестве целых чисел , $ℤ$ , таких , что $х ~ у$ , если и только если их разность $х - у$ является четным числом . Это отношение порождает ровно два класса эквивалентности: один класс состоит из всех четных чисел, а другой класс состоит из всех нечетных чисел. Используя квадратные скобки вокруг одного члена класса для обозначения класса эквивалентности в этом отношении, $[7]$ , $[9]$ и $[1]$ представляют один и тот же элемент из $ℤ / ~$ . ^[5]
Пусть $X$ - множество упорядоченных пар целых чисел $(a, b)$ с ненулевым $b$ , и определим отношение эквивалентности $~$ на $X$ такое, что $(a, b) ~ (c, d)$ тогда и только тогда, когда $ad = bc$ , то класс эквивалентности пары $(a, b)$ можно отождествить с рациональным числом $a / b$ , и это отношение эквивалентности и его классы эквивалентности могут использоваться для формального определения множества рациональных чисел. ^[6] Та же конструкция может быть обобщена на поле частных любой области целостности .
Если $X$ состоит из всех прямых, скажем, на евклидовой плоскости , а L ~ M означает, что L и M - параллельные прямые , тогда набор прямых, параллельных друг другу, образует класс эквивалентности, пока прямая считается параллельным самому себе . В этой ситуации каждый класс эквивалентности определяет бесконечно удаленную точку .

Обозначения и формальное определение [ править ]

Отношение эквивалентности на множестве $X$ представляет собой бинарное отношение $~$ на $X$ , удовлетворяющих три свойства: ^[7]^[8]

$а ~ а$ для всех $а$ в $X$ ( рефлексивность ),
$a ~ b$ влечет $b ~ a$ для всех $a$ и $b$ в $X$ ( симметрия ),
если $a ~ b$ и $b ~ c,$ то $a ~ c$ для всех $a$ , $b$ и $c$ в $X$ ( транзитивность ).

Класс эквивалентности элемента $a$ обозначается $[a]$ или $[a] ~$ , ^[1] и определяется как набор элементов, которые связаны с $a$ посредством $~$ . ^[3] Слово «класс» в термине «класс эквивалентности» не относится к классам, как определено в теории множеств , однако классы эквивалентности часто оказываются собственными классами . ${\ displaystyle \ {x \ in X \ mid a \ sim x \}}$

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

Когда элемент выбирается (часто неявно) в каждом классе эквивалентности, это определяет инъективную карту, называемую разделом . Если этот раздел обозначен $s$ , то $[s (c)] = c$ для каждого класса эквивалентности $c$ . Элемент $сек (с)$ называется представителем из $с$ . Любой элемент класса может быть выбран в качестве представителя класса, выбрав соответствующий раздел.

Иногда есть раздел, который более «естественен», чем другие. В этом случае представители называются каноническими представителями . Например, в модульной арифметике рассмотрим отношение эквивалентности целых чисел, определяемое следующим образом: $a ~ b,$ если $a - b$ кратно заданному положительному целому числу $n$ (называемому модулем ). Каждый класс содержит уникальное неотрицательное целое число, меньшее $n$ , и эти целые числа являются каноническими представителями. Класс и его представитель более или менее определены, как свидетельствует тот факт , что обозначение $мод$ $п$ может обозначать либо класс, либо его канонический представитель (который является остальной частью разделения изпо $п$ ).

Свойства [ править ]

Каждый элемент $x$ из $X$ является членом класса эквивалентности $[x]$ . Любые два класса эквивалентности $[x]$ и $[y]$ либо равны, либо не пересекаются . Таким образом, множество всех классов эквивалентности $X$ образует разбиение на $X$ : каждый элемент $X$ принадлежит одному и только один класс эквивалентности. ^[10] И наоборот, каждое разбиение $X$ происходит из отношения эквивалентности таким образом, согласно которому $x ~ y$ тогда и только тогда, когда $x$ и $y$ принадлежат одному и тому же набору раздела. ^[11]

Из свойств отношения эквивалентности следует, что

x ~ y

тогда и только тогда, когда

[x] = [y]

.

Другими словами, если $~$ - отношение эквивалентности на множестве $X$ , а $x$ и $y$ - два элемента $X$ , то эти утверждения эквивалентны:

${\ Displaystyle х \ сим у}$
${\ Displaystyle [х] = [у]}$
${\ displaystyle [x] \ cap [y] \ neq \ emptyset.}$

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

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

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

Инварианты [ править ]

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Примечания [ править ]

^ a b «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 30 августа 2020 .
^ «7.3: Классы эквивалентности» . Математика LibreTexts . 2017-09-20 . Проверено 30 августа 2020 .
^ а б Вайсштейн, Эрик В. "Класс эквивалентности" . mathworld.wolfram.com . Проверено 30 августа 2020 .
^ Avelsgaard 1989 , стр. 127
Перейти ↑ Devlin 2004 , p. 123
Перейти ↑ Maddox 2002 , pp. 77–78
Перейти ↑ Devlin 2004 , p. 122
^ Вайсштейн, Эрик В. «Отношение эквивалентности» . mathworld.wolfram.com . Проверено 30 августа 2020 .
Перейти ↑ Wolf 1998 , p. 178
Перейти ↑ Maddox 2002 , p. 74, Thm. 2.5.15
^ Avelsgaard 1989 , стр. 132, Thm. 3,16
Перейти ↑ Devlin 2004 , p. 123

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[:0-1] «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 30 августа 2020 .

[2] «7.3: Классы эквивалентности» . Математика LibreTexts . 2017-09-20 . Проверено 30 августа 2020 .

[:1-3] а б Вайсштейн, Эрик В. "Класс эквивалентности" . mathworld.wolfram.com . Проверено 30 августа 2020 .

[4] Avelsgaard 1989 , стр. 127

[5] Перейти ↑ Devlin 2004 , p. 123

[6] Перейти ↑ Maddox 2002 , pp. 77–78

[7] Перейти ↑ Devlin 2004 , p. 122

[8] Вайсштейн, Эрик В. «Отношение эквивалентности» . mathworld.wolfram.com . Проверено 30 августа 2020 .

[9] Перейти ↑ Wolf 1998 , p. 178

[10] Перейти ↑ Maddox 2002 , p. 74, Thm. 2.5.15

[11] Avelsgaard 1989 , стр. 132, Thm. 3,16

[12] Перейти ↑ Devlin 2004 , p. 123

[+1]