Relasjoner

Relasjoner er sammenhenger som eksisterer mellom elementer i en mengde.

Definisjoner

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

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

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

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

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

Ordningsrelasjoner

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

Hausdorffs maksimalitetsprinsipp

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

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</math>.

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

Noen elementære egenskaper til ekvivalensklasser er

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

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

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

Partisjoner

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

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

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