Relasjoner

Relasjoner er sammenhenger som eksisterer mellom elementer i en mengde.

Definisjoner

La <tex>X</tex> være en mengde, og la <tex>a,b,c\in X</tex>. Vi noterer en relasjone mellom <tex>a</tex> og <tex>b</tex> ved å skrive <tex>a\sim b</tex>. La oss se på følgende egenskaper en relasjon kan tenkes å ha:

1. <tex>a\sim a</tex> (Refleksivitet)

2. <tex>a\sim b \, \Leftrightarrow \, b\sim a</tex> (Symmetri)

3. Hvis <tex>a\sim b</tex> og <tex>b\sim a</tex>, så er <tex>a=b</tex> (Antisymmetri)

4. Hvis <tex>a\sim b</tex> og <tex>b\sim c</tex>, så er <tex>a\sim c</tex> (Transitivitet)

Ordningsrelasjoner

En relasjon som oppfyller 1., 3. og 4. kalles en partiell ordningsrelasjon på <tex>X</tex>. I dette tilfellet kan vi skrive <tex>\sim</tex> som <tex>\leq</tex>. En ordning er total (evt. lineær eller enkel), hvis vi for hvert par <tex>a,b\in X</tex> har enten <tex>a\leq b</tex> eller <tex>b\leq a</tex>.