Ekvivalenčna relacija

Ekvivalenčna relacija v matematiki je dvočlena relacija ~ (označena tudi kot $R$) v množici $A$, če veljajo za poljubne elemente $a$, $b$ in $c$ množice značilnosti:

1. $\mathrm{\forall }aaRa$ (zakon o povratnosti – refleksivnosti)
2. $\mathrm{\forall }a\mathrm{\forall }b(aRb⟹bRa)$ (zakon o vzajemnosti – simetričnosti)
3. $\mathrm{\forall }a\mathrm{\forall }b\mathrm{\forall }c(aRb\wedge bRc⟹aRc)$ (zakon o prehodnosti – tranzitivnosti)

Za vsako ekvivalenčno relacijo na množici $A$, lahko množico $A$ razdelimo na disjunktne podmnožice, imenovane ekvivalenčni razredi. Ekvivalenčni razred elementa $a$ iz množice $A$ je množica vseh elementov, ki so v relaciji z $a$, kar zapisujemo kot $[a]$.

Za ekvivalenčno relacijo na množici $A$ velja:

• $aRb\iff [a]=[b]$
• Če $a$ ni v relaciji z $b$, potem je $[a]\cap [b]=\mathrm{\varnothing }$
• Vsak element množice $A$ pripada natanko enemu ekvivalenčnemu razredu.

Zgledi ekvivalenčnih relacij

• enakost ($=$), relacija enakosti med realnimi števili ali množicami,
• relacija »je kongruentno po modulu $m$« ($\equiv$) med celimi števili,
• relacija »je podobno« med množico vseh trikotnikov,
• relacija »ima rojstni dan kot« med množico vseh ljudi,
• relacija »logične enakovrednosti« med stavki logike prvega reda,
• relacija »izomorfizma« med modeli množice stavkov,
• relacija ekvipolence med množicami.

Glej tudi

• ekvivalenčni razred