Hva er en relasjon?

En binaer relasjon \(R\) paa en mengde \(A\) er en delmengde \(R \subseteq A \times A\). Vi skriver \(a\,R\,b\) naar \(\langle a,b\rangle \in R\). All teori bygger paa de fem grunnegenskapene.

De fem egenskapene

Refleksiv: \(\forall a\,(\langle a,a\rangle \in R)\)

Irrefleksiv: \(\forall a\,(\langle a,a\rangle \notin R)\)

Symmetrisk: \(\forall a,b\,(\langle a,b\rangle \in R \Rightarrow \langle b,a\rangle \in R)\)

Antisymmetrisk: \(\forall a,b\,(\langle a,b\rangle \in R \wedge \langle b,a\rangle \in R \Rightarrow a=b)\)

Transitiv: \(\forall a,b,c\,(\langle a,b\rangle \in R \wedge \langle b,c\rangle \in R \Rightarrow \langle a,c\rangle \in R)\)

Merk: "ikke refleksiv" er ikke det samme som "irrefleksiv". En relasjon kan vaere verken-eller. Tilsvarende kan en relasjon vaere baade symmetrisk og antisymmetrisk (kun hvis den kun har diagonale par).

Ekvivalensrelasjoner og ekvivalensklasser

En ekvivalensrelasjon er refleksiv, symmetrisk og transitiv (RST). Den deler \(A\) inn i ekvivalensklasser \([a]=\{x\in A:a\,R\,x\}\), som danner en partisjon av \(A\): ikke-tomme, parvis disjunkte, og dekker hele \(A\). Antall ekvivalensrelasjoner paa en \(n\)-mengde er Bell-tallet \(B_n\) (\(B_1{=}1,B_2{=}2,B_3{=}5,B_4{=}15,B_5{=}52\)).

Eksempel 1: Vis at \(a \sim b \Leftrightarrow a \equiv b \pmod 3\) er en ekvivalensrelasjon paa \(\mathbb{Z}\), og finn klassene.

Refleksiv: \(3 \mid (a-a)=0\), saa \(a \sim a\). OK.

Symmetrisk: hvis \(3 \mid (a-b)\) saa \(3 \mid (b-a)\). OK.

Transitiv: \(3\mid(a-b)\) og \(3\mid(b-c)\) gir \(3\mid((a-b)+(b-c))=3\mid(a-c)\). OK.

RST oppfylt, saa det er en ekvivalensrelasjon.

Klasser etter rest mod 3: \([0]=\{\dots,-3,0,3,\dots\},\ [1],\ [2]\) — totalt 3 klasser.

Partielle ordninger og Hasse-diagram

En partiell ordning er refleksiv, antisymmetrisk og transitiv (RAT). Paret \((A,\preceq)\) kalles en poset. I et Hasse-diagram utelater vi refleksive looper, transitive snarveier og pilretning — stoerre elementer plasseres hoeyere, og kun dekkrelasjonen (umiddelbare etterfoelgere) tegnes.

Elementtyper i en poset

Minimalt: ingen element strengt under. Maksimalt: ingen strengt over.

Minste: ligger under alle (\(\forall x:\,a \preceq x\)). Stoerste: ligger over alle. Minste/stoerste er unike hvis de finnes.

Eksempel 2: Delelighet \(\mid\) paa \(\{1,2,3,4,6,12\}\). Finn minste/stoerste og beskriv Hasse-diagrammet.

Sjekk poset: \(a\mid a\) (refleksiv); \(a\mid b \wedge b\mid a \Rightarrow a=b\) (antisymmetrisk); \(a\mid b\wedge b\mid c \Rightarrow a\mid c\) (transitiv).

Minste = 1 (1 deler alt). Stoerste = 12 (alle deler 12).

Dekkrelasjoner: \(1\!-\!2,\ 1\!-\!3,\ 2\!-\!4,\ 2\!-\!6,\ 3\!-\!6,\ 4\!-\!12,\ 6\!-\!12\).

Bunn: 1. Lag 2: \(2,3\). Lag 3: \(4,6\). Topp: 12. 2 og 3 er uforlignbare (ingen deler den andre).

Relasjoner via en funksjon

Gitt \(f:A \to B\), definer \(a \sim b \Leftrightarrow f(a)=f(b)\). Dette er alltid en ekvivalensrelasjon (kjernerelasjonen), siden den arver RST fra likhet \(=\). Ekvivalensklassen er urbildet \([a]=f^{-1}(\{f(a)\})\), og klassene staar i bijeksjon med bildet \(f(A)\).

Eksempel 3: \(f(x)=x^2\) paa \(\mathbb{Z}\), \(a\sim b \Leftrightarrow a^2=b^2\). Finn klassene.

Refleksiv/symmetrisk/transitiv arves fra \(=\), saa det er en ekvivalensrelasjon.

\([0]=\{x:x^2=0\}=\{0\}\).

\([3]=\{x:x^2=9\}=\{3,-3\}\). Generelt \([n]=\{n,-n\}\) for \(n\neq0\).

Matrise og rettet graf

En relasjon paa \(\{a_1,\dots,a_n\}\) representeres som en \(n\times n\) 0/1-matrise med \(M_R[i][j]=1 \Leftrightarrow \langle a_i,a_j\rangle \in R\), eller som en rettet graf med en kant \(a_i \to a_j\) per par. Egenskaper gjenkjennes raskt:

Lesing av matrisen \(M_R\)

Refleksiv: full diagonal av 1-ere. Irrefleksiv: diagonal kun 0.

Symmetrisk: \(M_R = M_R^T\). Antisymmetrisk: for \(i\neq j\) ikke baade \((i,j)\) og \((j,i)\) lik 1.

Stier av lengde 2: boolsk produkt \(M_R \odot M_R\) (AND for produkt, OR for sum). \(R\) er transitiv hvis hver 1 i \(M_R\odot M_R\) ogsaa er 1 i \(M_R\).

Eksempel 4: \(R\) paa \(\{1,2,3\}\) med 1-ere i \((1,2)\) og \((2,3)\). Er \(R\) transitiv?

Eneste sti av lengde 2: \(1\to2\to3\), saa \(M_R\odot M_R\) har 1 i \((1,3)\).

Men \(M_R[1][3]=0\) — snarveien mangler.

Konklusjon: \(R\) er IKKE transitiv. Transitiv tillukning faas ved aa legge til \(\langle1,3\rangle\).

Studieguide: Relasjoner