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

редактировать
Рефлексивное, симметричное и транзитивное отношение
Бинарные отношения
Симметричное Антисимметричное Connex Well -основан Имеет объединения Соответствует
Отношению эквивалентности
Предварительный заказ (квазипорядок)
Частичный заказ
Общий предварительный заказ
Общий заказ
Предварительный заказ
Хорошо-квази- упорядочение
Упорядочение
Решетка
Соединение-полурешетка
Встреча-полурешетка
Знак «✓» указывает, что свойство столбца требуется в определении строки.. Например, определение отношения эквивалентности требует, чтобы оно было симметричным.. Все определения неявно требуют транзитивности и рефлексивности.
Отношения эквивалентности 52 на 5-элементном множестве, изображенном как 5 × 5 логических матриц (цветные поля, в том числе светло-серые, обозначают единицы; белые поля - нули.) Индексы строк и столбцов небелых ячеек являются связанными элементами, а разные цвета - другими чем свет серым цветом обозначены классы эквивалентности (каждая светло-серая ячейка является собственным классом эквивалентности).

В математике отношение эквивалентности - это бинарное отношение, которое является рефлексивным, симметричным и транзитивным. Отношение «равно» является каноническим примером отношения эквивалентности, где для любых объектов a, b и c:

  • a = a (рефлексивное свойство),
  • если a = b, то b = a (свойство симметрии) и
  • , если a = b и b = c, то a = c (свойство транзитивности).

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

Содержание

  • 1 Обозначение
  • 2 Определение
  • 3 Примеры
    • 3.1 Простой пример
    • 3.2 Отношения эквивалентности
    • 3.3 Отношения, которые не являются эквивалентностями
  • 4 Связи с другими отношениями
  • 5 Четко определенная в отношении эквивалентности
  • 6 Класс эквивалентности, факторное множество, раздел
    • 6.1 Класс эквивалентности
    • 6.2 Факторное множество
    • 6.3 Проекция
    • 6.4 Ядро эквивалентности
    • 6.5 Разделение
      • 6.5.1 Подсчет разделов
  • 7 Основная теорема об отношениях эквивалентности
  • 8 Сравнение отношений эквивалентности
  • 9 Создание отношений эквивалентности
  • 10 Алгебраическая структура
    • 10.1 Теория групп
    • 10.2 Категории и группоиды
    • 10.3 Решетки
  • 11 Отношения эквивалентности и математическая логика
  • 12 Евклидовы отношения
  • 13 См. Также
  • 14 Примечания
  • 15 Ссылки
  • 16 Внешние ссылки

Обозначения

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

Определение

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

X вместе с отношением ~ называется сетоидом. класс эквивалентности для a {\ displaystyle a}a под ~, обозначается [a ] {\ displaystyle [a]}[a] , определяется как [a] = {x ∈ X ∣ x ∼ a} {\ displaystyle [a] = \ {x \ in X \ mid x \ sim a \}}{\ displaystyle [a] = \ {x \ in X \ mid x \ sim a \}} .

Примеры

Простой пример

Пусть набор {a, b, c} {\ displaystyle \ {a, b, c \}}{\ displaystyle \ {a, b, c \}} имеют отношение эквивалентности {(a, a), (b, b), (c, c), (b, c), (c, b)} {\ displaystyle \ {( a, a), (b, b), (c, c), (b, c), (c, b) \}}{\ displaystyle \ {(a, a), (b, b), (c, c), (b, c), (c, b) \}} . Следующие множества представляют собой классы эквивалентности этого отношения:

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

Набор всех классов эквивалентности для этого отношения: {{a}, {b, c}} {\ displaystyle \ {\ {a \}, \ {b, c \} \}}{\ displaystyle \ {\ { a \}, \ {b, c \} \}} . Этот набор представляет собой раздел набора {a, b, c} {\ displaystyle \ {a, b, c \}}{\ displaystyle \ {a, b, c \}} .

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

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

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

Отношения, не являющиеся эквивалентностями

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

Связи с другие отношения

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

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

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

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

класс эквивалентности, фактормножество, разбиение

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

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

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

Факторное множество

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

Проекция

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

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

Ядро эквивалентности

Эквивалентность ядро функции f - это отношение эквивалентности ~, определяемое формулой x ∼ y ⟺ f (x) = f (y) {\ displaystyle x \ sim y \ iff f (x) = f (y)}x \ sim y \ iff f (x) = f (y) . Ядром эквивалентности инъекции является отношение идентичности.

Раздел

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

Подсчет разбиений

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

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

Основная теорема отношений эквивалентности

Ключевой результат связывает отношения эквивалентности и разбиения:

  • Отношение эквивалентности ~ на множестве X разбивает X.
  • И наоборот, соответствует любому разбиение X, существует отношение эквивалентности ~ на X.

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

Сравнение отношений эквивалентности

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

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

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

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

Генерация отношений эквивалентности

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

  • Для любого множества X существует отношение эквивалентности по множеству [ X → X] всех функций X → X. Две такие функции считаются эквивалентными, если их соответствующие наборы фиксированных точек имеют одинаковую мощность, соответствующую циклам длины один в перестановке. Эквивалентные таким образом функции образуют класс эквивалентности на [X → X], и эти классы эквивалентности разбивают [X → X].
  • Отношение эквивалентности ~ на X является ядром эквивалентности его сюръективная проекция π: X → X / ~. И наоборот, любая сюръекция между наборами определяет раздел в его домене, набор прообразов из одиночных объектов в кодомене. Таким образом, отношение эквивалентности над X, разбиение X и проекция, область определения которой X, являются тремя эквивалентными способами определения одного и того же.
  • Пересечение любого набора отношений эквивалентности над X (бинарные отношения рассматриваются как подмножество в X × X) также является отношением эквивалентности. Это дает удобный способ генерирования отношения эквивалентности: для любого бинарного отношения R на X отношение эквивалентности, порожденное R, является наименьшим отношением эквивалентности, содержащим R. Конкретно, R порождает отношение эквивалентности a ~ b тогда и только тогда, когда существуют элементы x 1, x 2,..., x n в X такие, что a = x 1, 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 / ~ можно естественным образом отождествить (гомеоморфизм ) с тором : возьмите квадратный лист бумаги, согните и склейте верхнюю и нижний край, чтобы сформировать цилиндр, затем согните получившийся цилиндр так, чтобы склеить его два открытых конца, в результате чего получится тор.

Алгебраическая структура

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

теории групп

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

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

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

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

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

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

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

Категории и группоиды

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

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

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

Решетки

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

Отношения эквивалентности и математическая логика

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

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

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

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

Евклидовы отношения

Евклид Элементы включают следующее «Общее понятие 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}}_ {\ Box}

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

См. Также

Примечания

Ссылки

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

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

Последняя правка сделана 2021-05-19 12:47:24
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте