Matematisk relasjon

I matematikken er ein relasjon eit forhold mellom objekt. Døme på relasjonar er «er mindre enn», «er lik» og «er ei delmengd av». I mengdeteori definerer ein ein relasjon som ei mengd av n-tuplar. Objekt som står i relasjonen R til kvarandre dannar ein n-tuppel, som er eit element av R. Når ikkje anna er sagt, forstår ein ein relasjon som ein binær relasjon, det vil seie ein relasjon mellom to objekt.

Definisjon

Ein binær relasjon R er ei delmengd av det kartesiske produktet av to mengder A og B.

$R\subseteq A\times B\quad {\mbox{der}}\quad A\times B:=\{(a,b)\,|\,\left(a\in A\right)\ \land \left(\ b\in B\right)\}$

Meir generelt kan ein relasjon vere ei delmengd av det kartesiske produktet av n mengder A₁, ..., A_n.

Forklaring

Det kartesiske produktet er mengda av alle ordna par av a og b, der a er eit element i mengda A, og b er eit element i mengda B. Viss a og b er relatert med relasjonen R, tyder det at (a,b) ∈ R, og ein skriv aRb. Ofte er A = B, slik at R ⊂ A×A. Då er relasjonen homogen.

Døme

Relasjonen ≤, «er mindre enn», er ein relasjon mellom til dømes reelle tal. Her er x ≤ y viss, og berre viss, x er eit tal som ikkje er større enn y.

Relasjonen «er far til» er eit døme på ein relasjon mellom til dømes menneskjer.

Eigenskapar

La R vere ein relasjon definert på ei mengd A. Nokre viktige eigenskapar som ein relasjon kan ha er følgjande: (x, y og z er element i A.)

• refleksiv: For kvar x er xRx. Til dømes er «mindre enn eller lik» ein refleksiv relasjon, men «mindre enn» er det ikkje.
• irrefleksiv: For kvar x er ikkje xRx.
• symetrisk: Viss xRy, så er òg yRx.
• antisymmetrisk: Viss xRy og yRx så er x = y. «Mindre enn eller lik» er ein antisymmetrisk relasjon, av di viss x ≤ y og y ≤ x, så må x = y.
• transitiv: Viss xRy og yRz, så er xRz.
• total: For kvar x og y i A er anten xRy eller yRx.

Ein relasjon som er refleksiv, symmetrisk og transitiv, er ein ekvivalensrelasjon. Ein relasjon som er refleksiv, antisymmetrisk og transitiv er ei partiell ordning. En partiell ordning som er total er ei lineær ordning.

Ein relasjon R mellom element i A og B er ein funksjon viss det for kvart element x i A finst eitt og berre eitt element y i B sånn at xRy.