Relasjoner er sammenhenger som eksisterer mellom elementer i en mengde.

Innhold

Definisjoner

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


1. $a\sim a$ (Refleksivitet)

2. $a\sim b \, \Leftrightarrow \, b\sim a$ (Symmetri)

3. Hvis $a\sim b$ og $b\sim a$ , så er $a=b$ (Antisymmetri)

4. Hvis $a\sim b$ og $b\sim c$ , så er $a\sim c$ (Transitivitet)


Ordningsrelasjoner

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

Hausdorffs maksimalitetsprinsipp

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

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å $X$ .

For en gitt ekvivalensrelasjon på $X$ kan vi definere ekvivalensklassen til et element $a$ som

$[a]=\{ b \in X | a\sim b\}$


Noen elementære egenskaper til ekvivalensklasser er

1. $a\sim b \, \Rightarrow \, [a]=[b]$

2. Hvis $A$ og $B$ er ekvivalensklasser, har vi $A\cap B \neq \emptyset \, \Rightarrow \, A=B$

3. Enhver $a\in X$ er et medlem av én og bare én ekvivalensklasse.

Partisjoner

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

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

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