EGYSZERŰ TUDNIVALÓK AZ EKVIVALENCIA-RELÁCIÓRÓL:

Kétváltozós relációkkal foglalkozunk. Ilyenek például az egyenlőség, az azonosság, a kisebb reláció, a nagyobb reláció, de ilyen két alakzat egyebevágósága és hasonlósága, vagy két egyenes párhuzamossága is. Vagy ilyen az oszthatóság is. Ha a relációt R-rel jelöljük, akkor aRb jelöli azt, hogy fennáll a és b között. Például a kisebb esetében R = <, a párhuzamosság esetében R = ||,  az oszthatóság esetében R = |.

DEFINÍCIÓ: Egy kétváltozós R relációt akkor nevezünk szimmetrikusnak, hogyha valahányszor fennáll a és b között, mindig fennáll b és a között is (azaz aRb-ből következik bRa).

Ilyen például a rokonság, az egyenlőség, az egybevágóság, a párhuzamosság (amit azonban bizonyítani kell), a hasonlóság. A gráfoknál ilyen például az a reláció, hogy két pontot út köt össze. Viszont irányított gráfoknál ez már nem feltételenül szimmetrikus reláció. Nem ilyen például emberek között az „a szimpatikus b-nek” reláció. Egyáltalán nem ilyen a kisebb reláció: ha a<b, akkor b<a nem állhat fenn. Az olyan relációkat, mint a kisebb reláció, ahol a<b-ből b<a tagadása következik, antiszimmetrikus relációnak nevezzük. Az oszthatóság csak akkor ilyen, ha hozzátesszük, hogy osztható és nem egyenlő.

DEFINÍCIÓ: Az R relációt tranzitívnak nevezzük, ha aRb és bRc-ből következik aRc is.

Ilyen tranzitív reláció a felsoroltak közül a kisebb és a nagyobb reláció, másrészt az egyenlőség, az egybevágóság és a hasonlóság, a párhuzamosság. Tranzitív a gráfon belül az úttal összeköthetőség is. Nem tranzitív viszont például a (vér)rokonság.

DEFINÍCIÓ: Ha egy reláció szimmetrikus és tranzitív, akkor ekvivalencia-reláció. Az ilyen relációk azt a halmazt, amelyen értelmezve vannak, osztályokba sorolják. Ezek az osztályok a következőt „tudják”: egy osztályon belül bármely két elem között fennáll a reláció, különböző osztályokba tartozó elemek között nem áll fenn a reláció. Például a párhuzamosság esetén az azonos irányú egyenesek alkotják az osztályokat, egybevágóság esetén az egybevágó alakzatok. Az előbbi esetben az „irány” fogalmát szokás is így bevezetni, az utóbbi esetben önkéntelenül is például az egységkörről beszélünk. Nevezetes ekvivalencia-reláció az, hogy a és b ugyanazt a maradékot adja például tízzel osztva. Ez is ekvivalencia-reláció és az egész számokat úgynevezett maradékosztályokba sorolja aszerint, hogy mennyit adnak maradékul tízzel osztva. Ha tíz helyett kettőre nézzük ezt a relációt, akkor a páros és a páratlan számok osztályát kapjuk.

DEFINÍCIÓ: Általában az ekvivalencia-reláció által meghatározott osztályokat ekvivalenciaosztályoknak nevezzük.

Már az eddig mondottakból is kitűnik, hogy az ekvivalenciaosztályoknak fontos szerepük van. Gráfok esetén például az összefüggő komponensek ilyen ekvivalenciaosztályok, ha az ekvivalencia-reláció az „a úttal van összekötve b-vel”. Ekvivalencia-reláció az is, hogy a és b egy egyenesnek ugyanazon a partján van. Ez a reláció két osztályt határoz meg: az egyenes két oldalát.