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. $\forall a\ aRa$ (zakon o povratnosti – refleksivnosti)
2. $\forall a\forall b\ (aRb\implies bRa)$ (zakon o vzajemnosti – simetričnosti)
3. $\forall a\forall b\forall c\ (aRb\land bRc\implies 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\Leftrightarrow [a]=[b]$
• Če $a$ ni v relaciji z $b$, potem je $[a]\cap [b]=\emptyset$
• 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