Отношение эквивалентности

В 52 отношениях эквивалентности на 5-элементе , установленные изображены как 5 × 5 логических матриц (цветные поли, в то числе светло - серого цвета, подставку для них;. Белых полей для нулей) строк и столбцов индексов небелых клеток являются соответствующими элементами, в то время как разные цвета, кроме светло-серого, указывают классы эквивалентности (каждая светло-серая ячейка представляет собой свой собственный класс эквивалентности).

В математике , отношение эквивалентности является бинарным отношением , что является рефлексивным , симметричным и транзитивным . Отношение «равно» является каноническим примером отношения эквивалентности.

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

Обозначение [ править ]

В литературе используются различные обозначения для обозначения того, что два элемента a и b набора эквивалентны относительно отношения эквивалентности R ; наиболее распространенными являются « a ~ b » и « a ≡ b », которые используются, когда R неявно, и варианты « a ~ _R b », « a ≡ _R b » или « » для явного указания R. Неэквивалентность может быть написана « a ≁ b » или « ».${\ Displaystyle {а \ mathop {R} б}}$${\ Displaystyle а \ не \ эквив б}$

Определение [ править ]

Бинарное отношение ~ на множестве X называется отношением эквивалентности, если и только если оно рефлексивно, симметрично и транзитивно. То есть для всех a , b и c в X :

• а ~ а . ( Рефлексивность )
• a ~ b тогда и только тогда, когда b ~ a . ( Симметрия )
• если a ~ b и b ~ c , то a ~ c . ( Транзитивность )

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

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

Простой пример [ править ]

Пусть на множестве имеется отношение эквивалентности . Следующие множества являются классами эквивалентности этого отношения:${\ Displaystyle \ {а, б, в \}}$${\ Displaystyle \ {(а, а), (Ь, Ь), (с, с), (Ь, с), (с, Ь) \}}$

${\ displaystyle [a] = \ {a \}, ~~~~ [b] = [c] = \ {b, c \}}$.

Множество всех классов эквивалентности для этого отношения равно . Этот набор является разбиением множества .${\ Displaystyle \ {\ {а \}, \ {б, с \} \}}$${\ Displaystyle \ {а, б, в \}}$

Отношения эквивалентности [ править ]

Все следующие отношения являются отношениями эквивалентности:

• «Равно» на множестве чисел. Например, равно . ^[3]${\ displaystyle {\ tfrac {1} {2}}}$${\ displaystyle {\ tfrac {4} {8}}}$
• «Имеет тот же день рождения, что и» на съемках всех людей.
• « Подобно » на множестве всех треугольников .
• « Конгруэнтно » на множестве всех треугольников .
• «Конгруэнтно по модулю n » на целых числах . ^[3]
• «Имеет такое же изображение под функцией » на элементах домена функции .
• "Имеет одинаковое абсолютное значение" на множестве действительных чисел
• «Имеет одинаковый косинус» на множестве всех углов.

Отношения, не являющиеся эквивалентами [ править ]

• Отношение «≥» между действительными числами рефлексивно и транзитивно, но не симметрично. Например, 7 ≥ 5 не означает, что 5 ≥ 7. Однако это полный порядок .
• Отношение «имеет общий делитель больше 1 с» между натуральными числами больше 1, является рефлексивным и симметричным, но не транзитивным. Например, у натуральных чисел 2 и 6 общий делитель больше 1, а у 6 и 3 общий делитель больше 1, но у 2 и 3 общий делитель не больше 1.
• Пустое отношение R (определяется так , что АРБ никогда не верно) на непустого множества X является тривиальным образом симметрично и транзитивно, но не рефлексивно. (Если X также пусто , то R является рефлексивным.)
• Отношение «примерно равно» между действительными числами, даже если оно определено более точно, не является отношением эквивалентности, потому что, хотя оно рефлексивно и симметрично, оно не является транзитивным, поскольку несколько небольших изменений могут накапливаться, чтобы стать большим изменением. Однако, если приближение определяется асимптотически, например, говоря, что две функции f и g приблизительно равны около некоторой точки, если предел f - g равен 0 в этой точке, то это определяет отношение эквивалентности.

Связи с другими отношениями [ править ]

• Частичный порядок является отношение , которое является рефлексивным, антисимметричным и транзитивным.
• Равенство - это одновременно отношение эквивалентности и частичный порядок. Равенство также является единственным отношением на множестве, которое является рефлексивным, симметричным и антисимметричным. В алгебраических выражениях одинаковые переменные могут быть заменены друг на друга, что недоступно для переменных, связанных с эквивалентностью. Эти классы эквивалентности отношения эквивалентности могут заменить друг с другом, но не отдельных лиц в пределах класса.
• Строгий частичный порядок иррефлексивно, переходный и асимметричный .
• Частичное отношение эквивалентности транзитивно и симметрично. Такое отношение рефлексивно тогда и только тогда, когда оно серийно , то есть если ∀ a ∃ b a ~ b . ^[4] Следовательно, отношение эквивалентности может быть альтернативно определено как симметричное, транзитивное и последовательное отношение.
• Тройное отношение эквивалентности является тройной аналог обычных (бинарными) отношений эквивалентности.
• Рефлексивное и симметричное отношение - это отношение зависимости (если оно конечно), и отношение терпимости, если оно бесконечно.
• Предзаказ рефлексивно и транзитивно.
• Конгруэнтность отношение является отношением эквивалентности, область Х также базовый набор для алгебраической структуры , и которая уважает дополнительную структуру. Вообще говоря, отношения конгруэнтности играют роль ядер гомоморфизмов, и может быть образовано факторное отношение структуры по отношению конгруэнтности. Во многих важных случаях отношения конгруэнтности имеют альтернативное представление как подструктуры структуры, на которой они определены (например, отношения конгруэнтности на группах соответствуют нормальным подгруппам ).
• Любое отношение эквивалентности является отрицанием отношения обособленности , хотя обратное утверждение справедливо только в классической математике (в отличие от конструктивной математики ), поскольку оно эквивалентно закону исключенного третьего .

Правильность определения в отношении эквивалентности [ править ]

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

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

В более общем смысле функция может отображать эквивалентные аргументы (в отношении эквивалентности ~ _A ) в эквивалентные значения (в соответствии с отношением эквивалентности ~ _B ). Такая функция а известна как морфизм от ~ _А к ~ _B .

Класс эквивалентности, фактор-множество, разбиение [ править ]

Пусть . Некоторые определения:${\ displaystyle a, b \ in X}$

Класс эквивалентности [ править ]

Подмножество Y из X таким образом, что ~ Ь справедливо для всех а и б в Y , и никогда не для в Y и B вне Y , называется класс эквивалентности из X по ~. Обозначим через класс эквивалентности, к которому принадлежит a . Все эквивалентные друг другу элементы X также являются элементами одного и того же класса эквивалентности.${\ displaystyle [a]: = \ {x \ in X \ mid a \ sim x \}}$

Набор коэффициентов [ править ]

Множество всех классов эквивалентности X по ~, обозначаемый , является фактормножество из X на ~. Если X - топологическое пространство , существует естественный способ превратить X / ~ в топологическое пространство; подробности см. в частном пространстве .${\displaystyle X/{\mathord {\sim }}:=\{[x]\mid x\in X\}}$

Проекция [ править ]

Проекция из ~ является функция определяется которая отображает элементы X в соответствующие классы эквивалентности по ~.${\displaystyle \pi :X\to X/{\mathord {\sim }}}$${\displaystyle \pi (x)=[x]}$

Теорема о проекциях : ^[5] Пусть функция f : X → B такова, что a ~ b → f ( a ) = f ( b ). Тогда существует единственная функция g  : X / ~ → B такая, что f = g π. Если f - сюръекция и a ~ b ↔ f ( a ) = f ( b ), тоg - биекция .

Ядро эквивалентности [ править ]

Ядро эквивалентности некоторой функции F является отношением эквивалентности ~ определяется . Ядром эквивалентности инъекции является отношение тождества .${\displaystyle x\sim y\iff f(x)=f(y)}$

Раздел [ править ]

Перегородка из X представляет собой набор Р непустых подмножеств X , такие , что каждый элемент X является элементом одного элемента P . Каждый элемент P является ячейкой раздела. Кроме того, элементы P являются попарно не пересекаются , а их объединение является Х .

Подсчет разделов [ править ]

Пусть X - конечное множество из n элементов. Поскольку каждое отношение эквивалентности над X соответствует разбиению X , и наоборот, количество отношений эквивалентности на X равно количеству различных разбиений X , которое является n- м числом Белла B _n :

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}$       ( Формула Добинского ).

Основная теорема об отношениях эквивалентности [ править ]

Ключевой результат связывает отношения эквивалентности и разбиения: ^{[6] [7] [8]}

• Отношение эквивалентности ~ на множестве X разделов X .
• С другой стороны , соответствующий любое разбиение X , существует отношение эквивалентности \ на X .

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

Сравнение отношений эквивалентности [ править ]

Если ~ и ≈ - два отношения эквивалентности на одном и том же множестве S , а a ~ b влечет a ≈ b для всех a , b ∈ S , то ≈ называется более грубым отношением, чем ~, а ~ - более тонким отношением, чем ≈ . Эквивалентно,

• ~ лучше, чем ≈, если каждый класс эквивалентности ~ является подмножеством класса эквивалентности ≈, и, таким образом, каждый класс эквивалентности ≈ является объединением классов эквивалентности ~.
• ~ тоньше, чем ≈, если раздел, созданный ~, является уточнением раздела, созданного ≈.

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

Отношение «~ тоньше, чем ≈» на совокупности всех отношений эквивалентности на фиксированном множестве само по себе является отношением частичного порядка, которое делает совокупность геометрической решеткой . ^[9]

Создание отношений эквивалентности [ править ]

Для любого бинарного отношения на , отношение эквивалентности, порожденное, является пересечением отношений эквивалентности на, которые содержат . (Поскольку это отношение эквивалентности, пересечение нетривиально.)${\displaystyle A\subset X\times X}$${\displaystyle X}$${\displaystyle A}$${\displaystyle X}$${\displaystyle A}$${\displaystyle X\times X}$

• Любое множество X , есть отношение эквивалентности на множестве [ X → X ] все функции X → X . Две такие функции считаются эквивалентными, если их соответствующие наборы фиксированных точек имеют одинаковую мощность , соответствующую циклам длины один в перестановке . Эквивалентные таким образом функции образуют класс эквивалентности на [ X → X ], и эти классы эквивалентности разбивают [ X → X ].
• Отношение эквивалентности ~ на X является ядром эквивалентности его сюръективной проекции π: X → X / ~. ^[10] С другой стороны , любая сюръекция между множествами определяет разбиение на своей области, множество прообразов из одноэлементных в области значений . Таким образом, отношение эквивалентности над X , разбиение X и проекция, область определения которой X , являются тремя эквивалентными способами определения одного и того же.
• Пересечение любой совокупности отношений эквивалентности над X (бинарные отношения рассматриваются как подмножество из X × X ) также является отношение эквивалентности. Это дает удобный способ генерации отношение эквивалентности: при любом бинарное отношение R на X , отношение эквивалентности , порожденный R является наименьшим отношением эквивалентности , содержащий R . Конкретно, R порождает отношение эквивалентности a ~ b тогда и только тогда, когда существуют элементы x ₁ , x ₂ , ..., x_n в X такое, что a = x ₁ , b = x _n и ( x _i , x _{i +1} ) ∈ R или ( x _{i +1} , x _i ) ∈ R , i = 1, ..., n - 1.
  Обратите внимание, что созданное таким образом отношение эквивалентности может быть тривиальным. Например, отношение эквивалентности ~, порожденное любым полным порядком на X, имеет ровно один класс эквивалентности, сам X , потому что x ~ y для всех x и y . В качестве другого примера, любое подмножество относительно идентичности на X имеет эквивалентности классов , которые являются одноэлементными из X .
• Отношения эквивалентности могут создавать новые пространства, «склеивая вещи вместе». Пусть X - единичный декартов квадрат [0, 1] × [0, 1], и пусть ~ - отношение эквивалентности на X, определенное формулой ( a , 0) ~ ( a , 1) для всех a ∈ [0, 1] и (0, b ) ~ (1, b ) для всех b ∈ [0, 1]. Тогда фактор-пространство X / ~ можно естественным образом отождествить ( гомеоморфизм ) с тором: возьмите квадратный лист бумаги, согните и склейте верхний и нижний края, чтобы сформировать цилиндр, затем согните получившийся цилиндр так, чтобы склеить два его открытых конца, в результате получится тор.

Алгебраическая структура [ править ]

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

Теория групп [ править ]

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

Пусть '~' обозначает отношение эквивалентности над некоторым непустым множеством A , называемым универсумом или базовым множеством. Обозначим через G множество биективных функций над A , сохраняющих структуру разбиения A : ∀ x ∈ A ∀ g ∈ G ( g ( x ) ∈ [ x ]). Тогда верны следующие три связные теоремы: ^[11]

• ~ разбивает A на классы эквивалентности. (Это основная теорема об отношениях эквивалентности, упомянутая выше);
• Учитывая разбиение A , G является группой преобразований относительно композиции, орбиты которых являются клетки разбиения; ^[15]

• Учитывая группу преобразований G над А , существует отношение эквивалентности ~ над A , чьи классы эквивалентности орбиты G . ^{[16] [17]}

Таким образом, для данного отношения эквивалентности ~ над A существует группа преобразований G над A , орбиты которой являются классами эквивалентности A относительно ~.

Эта групповая характеристика отношений эквивалентности принципиально отличается от того, как решетки характеризуют отношения порядка. Доводы решетки теории операций встречаются и присоединиться элементы некоторого универсума А . Между тем, аргументы группы преобразований операций композиции и обратный являются элементами множества биекций , A → A .

Перемещение групп в общем, пусть H является подгруппой некоторой группы G . Пусть ~ - отношение эквивалентности на G такое, что a ~ b ↔ ( ab ⁻¹ ∈ H ). Классы эквивалентности ~ -также называются орбиты действия из H на G -Есть правые смежные классы из H в G . Меняя местами a и b, получаем левые смежные классы.

Связанное с этим мышление можно найти у Розена (2008: глава 10).

Категории и группоиды [ править ]

Пусть G будет множество , и пусть «~» обозначают отношение эквивалентности над G . Тогда мы можем сформировать группоид, представляющий это отношение эквивалентности, следующим образом. Объекты являются элементами группы G , и для любых двух элементов x и y группы G существует уникальный морфизм от x к y тогда и только тогда, когда x ~ y .

Преимущества рассмотрения отношения эквивалентности как частного случая группоида включают:

• В то время как понятие «отношения свободной эквивалентности» не существует, понятие свободного группоида на ориентированном графе существует. Таким образом, имеет смысл говорить о «представлении отношения эквивалентности», т. Е. О представлении соответствующего группоида;
• Связки групп, групповые действия , множества и отношения эквивалентности могут рассматриваться как частные случаи понятия группоида, точка зрения, которая предполагает ряд аналогий;
• Во многих контекстах важны "факторные отношения" и, следовательно, соответствующие отношения эквивалентности, часто называемые конгруэнциями . Это приводит к понятию внутреннего группоида в категории . ^[18]

Решетки [ править ]

Отношения эквивалентности на любом множестве X , когда они упорядочены по включению множества , образуют полную решетку , которая по соглашению называется Con X. Каноническое отображение кег : X ^ X → Con X , связывает моноид X ^ X всех функций на X и Con X . кег является сюръективным , но не инъективно . Менее формально отношение эквивалентности ker на X, переводит каждую функцию f : X → X в ее ядро ker f . Точно так же, кег (кег) является отношением эквивалентности на Х ^ Х .

Отношения эквивалентности и математическая логика [ править ]

Отношения эквивалентности - готовый источник примеров или контрпримеров. Например, отношение эквивалентности ровно с двумя бесконечными классами эквивалентности является простым примером теории, которая является ω- категоричной , но не категоричной для любого большего кардинального числа .

Из теории моделей следует, что свойства, определяющие отношение, могут быть доказаны независимыми друг от друга (и, следовательно, необходимыми частями определения) тогда и только тогда, когда для каждого свойства могут быть найдены примеры отношений, не удовлетворяющих данному свойству, но удовлетворяющих все остальные свойства. Следовательно, три определяющих свойства отношений эквивалентности могут быть доказаны взаимно независимыми на следующих трех примерах:

• Рефлексивное и транзитивное : Отношение ≤ на N . Или любой предзаказ ;
• Симметричный и транзитивный : отношение R на N , определяемое как aRb ↔ ab ≠ 0. Или любое отношение частичной эквивалентности ;
• Рефлексивное и симметричное : отношение R на Z , определяемое как aRb ↔ « a - b делится по крайней мере на одно из 2 или 3.» Или любое отношение зависимости .

Свойства, определяемые в логике первого порядка, которыми отношение эквивалентности может или не может обладать, включают:

• Число классов эквивалентности конечно или бесконечно;
• Количество классов эквивалентности равно (конечному) натуральному числу n ;
• Все классы эквивалентности имеют бесконечную мощность ;
• Количество элементов в каждом классе эквивалентности - натуральное число n .

Евклидовы отношения [ править ]

Евклида «S Элементы включает в себя следующее„Общее понятие 1“:

Вещи, которые равны одному и тому же, также равны друг другу.

В настоящее время свойство, описываемое Общим понятием 1, называется евклидовым (замена «равно» на «связаны с»). Под «отношением» подразумевается бинарное отношение , в котором aRb обычно отличается от bRa . Таким образом, евклидово отношение имеет две формы:

( aRc ∧ bRc ) → aRb (лево-евклидово соотношение)

( cRa ∧ cRb ) → aRb (право-евклидово соотношение)

Следующая теорема связывает евклидовы отношения и отношения эквивалентности:

Теорема

Если отношение (левое или правое) евклидово и рефлексивно , оно также симметрично и транзитивно.

Доказательство лево-евклидова отношения

( aRc ∧ bRc ) → aRb [ a / c ] = ( aRa ∧ bRa ) → aRb [ рефлексивный ; стереть T ∧] = bRa → aRb . Следовательно , R является симметричным .

( aRc ∧ bRc ) → aRb [ симметрия ] = ( aRc ∧ cRb ) → aRb . Следовательно , R является транзитивным .${\displaystyle _{\Box }}$

с аналогичным доказательством для право-евклидова отношения. Следовательно, отношение эквивалентности - это евклидово и рефлексивное отношение . В «Элементах» не упоминается ни симметрия, ни рефлексивность, и Евклид, вероятно, счел бы рефлексивность равенства слишком очевидной, чтобы ее можно было прямо упомянуть.

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

• Отношение обособленности
• Класс сопряженности
• Эквиполлентность (геометрия)
• Фактор по отношению эквивалентности
• Топологическая сопряженность
• Вплоть до

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

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

• Браун, Рональд, 2006. Топология и группоиды. Буксург ООО. ISBN 1-4196-2722-8 . 
• Кастеллани, Э., 2003, «Симметрия и эквивалентность» в Брэдинге, Кэтрин и Э. Кастеллани, ред., Симметрии в физике: философские размышления . Cambridge Univ. Пресс: 422–433.
• Роберт Дилворт и Кроули, Питер, 1973. Алгебраическая теория решеток . Прентис Холл. Гл. 12 обсуждает, как отношения эквивалентности возникают в теории решеток .
• Хиггинс, П.Дж., 1971. Категории и группоиды. Ван Ностранд. Доступно для скачивания с 2005 года в виде перепечатки TAC.
• Джон Рэндольф Лукас , 1973. Трактат о времени и пространстве . Лондон: Метуэн. Раздел 31.
• Розен, Джозеф (2008) Правила симметрии: как наука и природа основаны на симметрии . Springer-Verlag. В основном главы. 9,10.
• Раймонд Уайлдер (1965) Введение в основы математики, 2-е издание, глава 2-8: Аксиомы, определяющие эквивалентность, стр 48-50, John Wiley & Sons .

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

• "Отношение эквивалентности" , Энциклопедия математики , EMS Press , 2001 [1994]
• Богомольный, А. , " Отношение эквивалентности " разорвать узел . Доступ 1 сентября 2009 г.
• Отношение эквивалентности в PlanetMath
• Последовательность OEIS A231428 (двоичные матрицы, представляющие отношения эквивалентности)