Kapittel 17 – Abstraksjon med ekvivalenser og partisjoner / Ekvivalensklasser

Definisjon: Ekvivalensklasse

Hva syns du om denne videoen?
(Én stjerne er dårligst, tre stjerner er middels og fem stjerner er best.)
(Hvordan kan denne videoen bli bedre?)

Utfordring

La oss lage en ekvivalensrelasjon $R$ på mengden $M = \left\{ 1,2,3,4,5 \right\}$. En ekvivalensrelasjon er en binær relasjon på en mengde som er refleksiv, transitiv og symmetrisk (definisjon 6.5).

  • Siden $R$ skal være refleksiv må $\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 4, 4 \rangle, \langle 5, 5 \rangle \in R$.
  • La oss også si at $\langle 1, 2 \rangle \in R$. Da må også $\langle 2, 1 \rangle \in R$ siden $R$ skal være symmetrisk.
  • La oss også si at $\langle 1, 4 \rangle \in R$. Da må $\langle 4, 1 \rangle, \langle 2, 4 \rangle, \langle 4, 2 \rangle \in R$ siden $R$ skal være transitiv og symmetrisk.
  • La også $\langle 3, 5 \rangle \in R$. Da må også $\langle 5, 3 \rangle \in R$ siden $R$ er symmetrisk.

Tegn først opp denne relasjonen som fem prikker med piler mellom seg. Ser du at ekvivalensrelasjonen «binder sammen» elementene i ulike grupper?

Hvor mange ekvivalensklasser gir denne ekvivalensrelasjonen opphav til?

Utfordring

La $R$ være følgende relasjon.

$$ \big\{ \langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 4, 4 \rangle, \langle 5, 5 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 4 \rangle, \langle 4, 1 \rangle, \langle 2, 4 \rangle, \langle 4, 2 \rangle, \langle 3, 5 \rangle, \langle 5, 3 \rangle \big\} $$

Hvilke elementer finner vi i ekvivalensklassen til elementet $1$?

Utfordring

La $R$ være følgende relasjon.

$$ \big\{ \langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 4, 4 \rangle, \langle 5, 5 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 4 \rangle, \langle 4, 1 \rangle, \langle 2, 4 \rangle, \langle 4, 2 \rangle, \langle 3, 5 \rangle, \langle 5, 3 \rangle \big\} $$

Hvilke elementer finner vi i ekvivalensklassen til elementet $5$?