06 Relasjoner Flashcards
relasjon
En binær relasjon (eng: binary relation) fra mengden S til mengden T er en delmengde av S x T.
En binær mengde på mengden S er en delmengde av S^2.
Mer generelt, en n-ær relasjon (eng: n-ary relation) er en delmengde av A1 x … x An, og en n-ær relasjon på en mengde A er en delmengde av A^n.
refleksiv relasjon
En binær relasjon R på mengden S er refleksiv (eng: reflexive) hvis det for alle x i S er slik at ⟨x, x⟩ ∈ R.
symmetrisk relasjon
En binær relasjon R på mengden S er symmetrisk (eng: symmetric) hvis det for alle x, y er slik at hvis ⟨x, y⟩ ∈ R, så ⟨y, x⟩ ∈ R.
transitiv relasjon
En binær relasjon R på mengden S er transitiv (eng: transitive) hvis det for alle x, y, z er slik at hvis ⟨x, y⟩ ∈ R og ⟨y, z⟩ ∈ R, så ⟨x, z⟩ ∈ R.
ekvivalensrelasjon
En binær relasjon R på mengden S er en ekvivalensrelasjon (eng: equivalence relation) hvis den er refleksiv, symmetrisk og transitiv.
anti-symmetrisk relasjon
En binær relasjon R på mengden S er anti-symmetrisk hvis det for alle x, y er slik at hvis ⟨x, y⟩ ∈ R og ⟨y, x⟩ ∈ R, så x = y.
irrefleksiv relasjon
En binær relasjon R på mengden S er irrefleksiv (eng: irreflexive) hvis det ikke er noen x ∈ S slik at ⟨x, x⟩ ∈ R.
partiell ordning
En binær relasjon på mengden S er en partiell ordning (eng: partial order) hvis den er refleksiv, transitiv og anti-symmetrisk.
Partielle ordninger er altså relasjoner med “retning”.
total ordning
En partiell ordning R på en mengde S kalles en total ordning (eng: total order) eller en lineær ordning (eng: linear order) hvis det for alle x og y i S er slik at xRy eller yRx.
Totale ordninger er altså relasjoner som ordner alle elementene i en mengde etter hverandre.
