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