Relasjoner: Forskjell mellom sideversjoner
m Teksterstatting – «<tex>» til «<math>» |
|||
| Linje 3: | Linje 3: | ||
==Definisjoner== | ==Definisjoner== | ||
La < | 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. < | 1. <math>a\sim a</tex> (Refleksivitet) | ||
2. < | 2. <math>a\sim b \, \Leftrightarrow \, b\sim a</tex> (Symmetri) | ||
3. Hvis < | 3. Hvis <math>a\sim b</tex> og <math>b\sim a</tex>, så er <math>a=b</tex> (Antisymmetri) | ||
4. Hvis < | 4. Hvis <math>a\sim b</tex> og <math>b\sim c</tex>, så er <math>a\sim c</tex> (Transitivitet) | ||
==Ordningsrelasjoner== | ==Ordningsrelasjoner== | ||
En relasjon som oppfyller 1., 3. og 4. kalles en partiell ordningsrelasjon på < | 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=== | ===Hausdorffs maksimalitetsprinsipp=== | ||
La < | 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 < | 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. | Det er også et av mange utsagn som er ekvivalent til utvalgsaksiomet i mengdelære. | ||
| Linje 29: | Linje 29: | ||
==Ekvivalensrelasjoner== | ==Ekvivalensrelasjoner== | ||
En relasjon som oppfyller 1., 2. og 4. kalles en ekvivalensrelasjon på < | En relasjon som oppfyller 1., 2. og 4. kalles en ekvivalensrelasjon på <math>X</tex>. | ||
For en gitt ekvivalensrelasjon på < | For en gitt ekvivalensrelasjon på <math>X</tex> kan vi definere ekvivalensklassen til et element <math>a</tex> som | ||
< | <math>[a]=\{ b \in X | a\sim b\}</tex> | ||
Noen elementære egenskaper til ekvivalensklasser er | Noen elementære egenskaper til ekvivalensklasser er | ||
1. < | 1. <math>a\sim b \, \Rightarrow \, [a]=[b]</tex> | ||
2. Hvis < | 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 < | 3. Enhver <math>a\in X</tex> er et medlem av én og bare én ekvivalensklasse. | ||
===Partisjoner=== | ===Partisjoner=== | ||
Definer en partisjon av < | 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 < | 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 < | 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. | ||
[[Kategori:Logikk og mengdelære]] | [[Kategori:Logikk og mengdelære]] | ||
Sideversjonen fra 5. feb. 2013 kl. 20:57
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
<math>[a]=\{ b \in X | a\sim b\}</tex>
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.