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>. En mengde med en partiell (total) ordning kalles en partiellt (totalt) ordnet mengde.

Hausdorffs maksimalitetsprinsipp

La <tex>X</tex> være en mengde med en partiell ordningsrelasjon. Da sier Hausdorffs maksimalitetsprinsipp an enhver totalt ordnet undermengde av <tex>X</tex> er inkludert i en maksimal totalt ordnet undermengde.

Utsagnet er ekvivalent med Zorns lemma, som sier at enhver totalt ordnet undermengde har en øvre grense i <tex>X</tex>.

Det er også et av mange utsagn som er ekvivalent til utvalgsaksiomet i mengdelære.

Ekvivalensrelasjoner

En relasjon som oppfyller 1., 2. og 4. kalles en ekvivalensrelasjon på <tex>X</tex>.

For en gitt ekvivalensrelasjon på <tex>X</tex> kan vi definere ekvivalensklassen til et element <tex>a</tex> som

<tex>[a]=\{ b \in X | a\sim b\}</tex>

Noen elementære egenskaper til ekvivalensklasser er

1. <tex>a\sim b \, \Rightarrow \, [a]=[b]</tex>

2. Hvis <tex>A</tex> og <tex>B</tex> er ekvivalensklasser, har vi <tex>A\cap B \neq \emptyset \, \Rightarrow \, A=B</tex>

3. Enhver <tex>a\in X</tex> er et medlem av én og bare én ekvivalensklasse.

Partisjoner

Definer en partisjon av <tex>X</tex> som en samling av disjunkte undermengder av <tex>X</tex> hvis union er <tex>X</tex>. Da følger det umiddelbart at enhver <tex>a\in X</tex> er et element i én og kun én av disse undermengdene. Definer <tex>a\sim b</tex> hvis og bare hvis <tex>a</tex> og <tex>b</tex> er medlemmer av samme undermengde i en gitt partisjon. Da er <tex>\sim</tex> en ekvivalensrelasjon, og ekvivalensklassene er undermengdene i partisjonen.

På den andre siden kan vi la <tex>\sim</tex> være en ekvivalensrelasjon, og av egenskapene til ekvivalensklassene over kan vi fastslå at ekvivalensklassene partisjonerer <tex>X</tex>.

Vi har dermed en naturlig sammenheng mellom partisjoner av <tex>X</tex> på den ene siden, og ekvivalensrelasjoner på <tex>X</tex> på den andre.