Definisjon: Transitiv relasjon
Test deg selv
Anta at $\{ \langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 1, 3 \rangle, \langle 2, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 3 \rangle\}$ er en binær relasjon på en ukjent mengde. (Ut fra relasjonen vet vi at $1$, $2$ og $3$ er elementer i mengden, men vi vet ikke om mengden også inneholder andre elementer.) Hvilke(n) av følgende egenskaper kan vi med sikkerhet si at relasjonen har?
Vi kan ikke avgjøre om relasjonen er refleksiv eller ikke ved å kun se på tuplene i relasjonen. Vi er også nødt til å kjenne til hvilke elementer som inngår i den underliggende mengden. Hvis relasjonen over er på mengden $\{\1, 2, 3\}$, er den refleksiv, men hvis relasjonen er på mengden $\{1, 2, 3, 4\}$, er den ikke refleksiv, siden $\langle 4, 4 \rangle$ ikke er med.
Relasjonen er ikke symmetrisk, fordi $\tuple{1,2}$ er med, men $\tuple{2,1}$ er ikke med.
Relasjonen er transitiv, fordi hvis $\tuple{x,y}$ og $\tuple{y,z}$ er med, er også $\tuple{x,z}$ med.