Relasjoner

Relasjoner er sammenhenger som eksisterer mellom elementer i en mengde.

Definisjoner

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

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

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

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

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

Ordningsrelasjoner

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

Hausdorffs maksimalitetsprinsipp

La <math>X</tex> være en mengde med en partiell ordningsrelasjon. Da sier Hausdorffs maksimalitetsprinsipp an enhver totalt ordnet undermengde av <math>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 <math>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å <math>X</tex>.

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

Noen elementære egenskaper til ekvivalensklasser er

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

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

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

Partisjoner

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

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

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