Релација еквиваленције

У литератури се користе различите ознаке да би се означило да су два елемента ${\displaystyle a}$  и ${\displaystyle b}$  скупа еквивалентна у односу еквиваленције ${\displaystyle R;}$  најчешћи су „${\displaystyle a\sim b}$ ” и „a ≡ b”, који се користе када је ${\displaystyle R}$  имплицитно, а варијације „${\displaystyle a\sim _{R}b}$ ”, „a ≡_R b”, или „${\displaystyle {a\mathop {R} b}}$ ” да се ${\displaystyle R}$  експлицитно. Нееквивалентност се може записати као „a ≁ b” или „${\displaystyle a\not \equiv b}$ ”.

Каже се да је бинарна релација ${\displaystyle \,\sim \,}$  на скупу ${\displaystyle X}$  релација еквиваленције, ако и само ако је рефлексивна, симетрична и транзитивна. То јест, за свако ${\displaystyle a,b,}$  и ${\displaystyle c}$  у ${\displaystyle X:}$ 

• ${\displaystyle a\sim a.}$  (Рефлексивност)
• ${\displaystyle a\sim b}$  ако и само ако је ${\displaystyle b\sim a.}$  (Симетрија)
• Ако је ${\displaystyle a\sim b}$  и ${\displaystyle b\sim c}$  онда је ${\displaystyle a\sim c.}$  (Транзитивност)

${\displaystyle X}$  заједно са релацијом ${\displaystyle \,\sim \,}$  се назива сетоид. Класа еквиваленције ${\displaystyle a}$  под ${\displaystyle \,\sim ,}$  означава се са ${\displaystyle [a],}$  и дефинисана је као ${\displaystyle [a]=\{x\in X:x\sim a\}.}$ ^[2][3]

Велики део математике је заснован на проучавању еквиваленција и односа реда. Теорија решетки обухвата математичку структуру релација реда. Иако су релације еквиваленције једнако свеприсутне у математици као и релације реда, алгебарска структура еквиваленција није у истој мери позната као структура редова. Прва структура се ослања првенствено на теорију група и, у мањој мери, на теорију решетки, категорија и групоида.

Као што су релације поретка утемељене у уређеним скуповима, скупови затворени под упареним супремумом и инфимумом, односи еквиваленције су утемељени у партиционисаним скуповима, који су скупови затворени под бијекцијама који очувавају партициону структуру. Пошто све такве бијекције мапирају класу еквиваленције на саму себе, такве бијекције су такође познате као пермутације. Отуда пермутационе групе (такође познате као трансформационе групе) и сродни појам орбите бацају светло на математичку структуру релација еквиваленције.

Нека '~' означава релацију еквиваленције над неким непразним скупом A, који се назива универзум или основни скуп. Нека G означи скуп бијективних функција над A које презервирају партициону структуру A, што значи за свако ${\displaystyle x\in A}$  и ${\displaystyle g\in G,g(x)\in [x].}$  Тада важе следеће три повезане теореме:^[4]

• ~ дели A на класе еквиваленције. (Ово је Основна теорема релација еквиваленције, поменута горе);
• С обзиром на партицију од A, G је трансформациона група под саставом, чије су орбите ћелије партиције;^[8]
• С обзиром на трансформациону групу G над A, постоји релација еквиваленције ~ над A, чије класе еквиваленције су орбите G.^[9][10]

Све у свему, с обзиром на релацију еквиваленције ~ над A, постоји трансформациона група G над A чије су орбите класе еквиваленције A под ~.

Ова трансформациона групна карактеризација односа еквиваленције суштински се разликује од начина на који решетке карактеришу односе поретка. Аргументи операција теорије решетки обједињавају и спајају елементе неког универзума A. Аргументи композиције и инверзије операција групе трансформације су елементи скупа бијекција, A → A.

Прелазећи на групе у општем случају, нека је H подгрупа неке групе G. Нека је ~ релација еквиваленције на G, таква да је ${\displaystyle a\sim b{\text{ ако и само ако }}ab^{-1}\in H.}$  Класе еквиваленције ~— такође назване орбите деловања H на G— јесу десни косетови H у G. Заменом a и b добијају се леви косетови.^[11]

Нека је G скуп и нека „~” означава релацију еквиваленције над G. Тада се може формирати гроупоид који представља ову релацију еквиваленције на следећи начин. Објекти су елементи G, а за било која два елемента x и y из G постоји јединствени морфизам од x до y ако и само ако је ${\displaystyle x\sim y.}$ 

Предности посматрања релације еквиваленције као посебног случаја групноида укључују:

• Док појам „слободне релације еквиваленције” не постоји, појам слободног групноида на усмереном графу постоји. Стога је смислено говорити о „презентацији релације еквиваленције”, тј. о презентацији одговарајућег групноида;
• Скупови група, групне акције, скупови и релације еквиваленције могу се сматрати посебним случајевима појма групноида, што је тачке гледишта која сугерише бројне аналогије;
• У многим контекстима је важно „квоцијентирање“, а тиме и одговарајуће релације еквиваленције које се често називају конгруенције. Ово доводи до појма унутрашњег групноида у категорији.^[12]

Очигледан пример релације еквиваленције је једнакост ("="), релација између елемената сваког скупа. Следи још примера:

• „Рођен је истог дана као и“ на скупу свих људских бића.
• „Је сличан“ или „је подударан“ на скупу свих троуглова.
• Логичка еквиваленција исказа у логици.
• Нека a, b, c, d ∈ 'N', и (a, b) и (c, d) су уређени парови. Релације (a, b)~(c, d) ако a+d = b+c, и (a, b)~(c, d) ако ad = bc, су релације еквиваленције, чијим класама еквиваленције се могу сматрати цели бројеви и позитивни рационални бројеви, редом.
• „Је конгруентно по модулу n" за скуп целих бројева.
• „Је паралелно“, на скупу афиних потпростора афиног простора.

• Hazewinkel Michiel, ур. (2001). „Equivalence relation”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Bogomolny, A., "Equivalence Relationship" cut-the-knot. Accessed 1 September 2009
• Equivalence relation at PlanetMath
• OEIS sequence A231428 (Binary matrices representing equivalence relations)
• Релације еквиваленције