Relationen


10.10.2012 (Nachmittags)
geordnetes Paar (a,b) ist ein Konstrukt bei dem a an erster Stelle steht und b an zweiter Stelle steht.

(a,b) = {{a,b},{a}

Kartesisches Produkt


A x B = {(a,b) : a ∈ A ⋀ b ∈ B}
A={rot, grün, gelb}
B={Apfel, Banane, Kirsche, Pflaume}

AxB: hat 12 Elemente
Eine Teilmenge R⊆AxB nennen wir Relation. Wir schreiben aRb wenn (a,b) ∈R ist.

Darstellung


zum Beispiel abstrakt durch Eigenschaften

R= {(a,b)∈AxB| b hat typischerweise  Farbe a}

Bei der Darstellung als Tabelle schreiben wir eine 1 wenn (a,b) ∈ R ist und 0 sonst
//Tabelle
Bei der Darstellung als Graph, zeichnen wir für jedes Element einen Punkt. Und verbinden zwei Punkte (a,b) wenn aRb gilt, mit einem Pfeil.
//Graph


R ⊆ A x A heißt Identitätsrelation geschrieben Ida oder Ia manchmal nur I (wenn klar ist, welche Menge A gemeint ist) <=> R = {(a,b) ∈ A x A | a = b}

Sei R⊆AxB irgendeine Relation, so ist:
Die Verkettung von zwei Relationen R1 ⊆ A x B und R2 ⊆ B x C is definiert durch
R2  ○ R1   = {(a, c) ∈ AxC | ∃b∈B     (a,b)∈R1  ⋂ (b,c) ∈ R2}}
Der Kringel "○" ist das Symbol für die Verkettung, auch Komposition genannt.

Sei R1 die Relation = {(a,b) ∈ FarbenxFrüchte | b hat nach Meinung des Dozenten typischerweise Farbe a}


R1^(-1) = {(b,a) ∈ Früchte x Farben | "b hat ........... Farbe a"}

R1○R1^(-1) ⊆ Früchte x Früchte

            Apfel    |    Banane    |     Kirsche   |     Pflaume   
rot         1        |    0         |      1        |   0           
grün        1        |    0         |      0        |   0           
gelb        1        |    1         |      0        |   0           

R1  ○ R1^(-1) | Apfel  |   Banane  | Kirsche  | Pflaume       
Apfel         |        |           |          |               
Banane        |        |           |          |               
Kirsche       |        |           |          |               
Pflaume       |        |           |          |               


A=B=C=R            f(x) =x+1
                          g(x) = x²

            f                     g
Frucht ------> Farben ------> {gekauft, nicht gekauft}

f:(Frucht) = meist vorkommende Farbe

g:(Farbe) 

g( f(Frucht))
=g(Farbe)=gekauft oder nicht gekauf (aka to be or not to be)

g ○ f ⊆ Frucht x {gekauft, nicht gekauft}

Äquivalenzrelationen


R⊆AxA ist eine Äquivalenzrelation
<=>
      (1) ∀a∈A: aRa Reflexivität
      (2) ∀a,b∈A: aRb <=> bRa Symmetrie
      (3) ∀a,b,c∈A: aRb⋀bRc => aRc Transitivität

Ganz nett als Hintergrundwissen hierzu: 
Beispiel: A = {1,2,3,4,5}
\      1        2       3        4        5  
1      1        0       1        0        1  
2      0        1       0        1        0  
3      1        0       1        0        1  
4      0        1       0        1        0  
5      1        0       1        0        1  

(3,1)⋀(1,5) => (3,5) Transitivität

☇ Nehmen wir an, dass (2,3) in R ist
(2,3)⋀(3,1) => (2,1)             ☇
(4,3)⋀(3,1) => (4,1)             ☇
(2,5)⋀(5,1) => (2,1)             ☇

nächstes Beispiel
A={Menschen}
a ~ b <=> a und b haben die selbe Haarfarbe.
Ist diese Relation reflexiv? JA!
Ist sie symmetrisch? JA!
Transitivität? JA!

Wenn a und b die selbe Haarfabe haben und b und c , na(?) dann aber wohl auch a und c.

Folgt Reflexivität aus Transitivität und Symmetrie?

falscher Beweis:
aRb ⋀ bRa
folgt aus Symmetrie und aus Transitivität folgt aRa

Suchen Gegenbeispiel welches transitiv, symmetrisch aber nich reflexiv ist.
A={1,2}
R|1|2
1|0|0
2|0|0
(Merke: eine Implikation ist immer wahr, wenn die Vorraussetzung falsch ist)

Diese Relation erfüllt das Gewünschte.

A=Z und ~ sei so definiert:
a~b <=> a-b gerade ist
zZ ~ und Äquivalentrelation
∀a∈Z a-a ist gerade
       0 ist gerade
∀a,b∈Z  a-b gerade
        =b-a gerade
    (a-b) ist gerade => ∃l: (a-b)=2*l
    =>(b-a)=2*(-l)=>(b-a) gerade
Wenn wir zeigen wollen, dass a genau dann, wenn b gilt, reicht es folgende zwei Implikationen zu zeigen:
A=>B und B=>A
A↔B≡(A→B)⋀(B→A)

Transitivität



(a-b) sie gerade und (b-c auch).
=> ∃k,l: (a-b)=2*k
         (b-c)=2*l
         (a-c)=2(k+l)
         
         


Nachtrag Relationen



Wir definieren die Verkettung von Relationen R ⊆ A x B und S ⊆ B x C als R ○ S = {(a,c)∈A x C: ∃b∈B aRb ⋀ bSc}

Siehe Beispiel Zeile 42ff + Graphen

Äquivalenzrelationen II



R|a|b|c|d|e
a|1|0|1|1|0
b|0|1|0|0|0
c|1|0|1|1|0
d|1|0|1|1|0
e|0|0|0|0|1

Sei {A1,A2,A3} eine Partition von der Menge
   3
A= UAi
  i=1
(d.h. Ai⋂Aj =∅ <=> i≠j)
a~b <=> ∃i{1, 2, 3}: a,b ∈A

Zeigen sie ~ ist eine Äquivalenzrelation.

A1=Steinobst={Kirschen,Pflaumen}
A2=Beeren={Erdbeere,Blaubeere}
A3=Zitrusfrüchte={Zitrone,Limette}

~  |Ki| PF| ERD| BLA| ZI| LI
KI |1 |  1| 0  |  0 |   |   
PF |1 |  1| 0  |  0 |   |   
ERD|0 |  0| 1  |  1 |   |   
BLA|0 |  0| 1  |  1 |   |   
ZI |  |   |    |    | 1 | 1 
LI |  |   |    |    | 1 | 1 


a ~ b <=> (a,b) ∈ ~

Reflexivität

Sei a∈A. Wir müssen zeigen:
∃i: a∈Ai  (das gilt)

Symmetrie

Seien a,b∈A. Wir müssen zeigen a~b <=> b~a
a~b <=> ∃i : a,b∈Ai <=> ∃i: b,a∈Ai
    <=> b~a

Transitivität

seien a,b,c∈A

a~b ⋀b~c =>a~c
Wir nehmen an die Vorraussetzung gilt.
Def. ∃i: a,b∈Ai
und ∃j:b,c∈Aj

Es reicht zu zeigen i=j
☇ Sei i≠j => b∈Ai⋂Aj
 =>Ai⋂Aj≠∅ => i=j ☇

|N={0,1,2,.....}  Möglich: Addieren,Multiplizieren
~⊆(|Nx|N)x(|Nx|N)
a-b=c-0
(a,b)~(c,d)
<=>a-b=c-d
<=>a+d=c+b <- Unsere Definition

Wir wollen zeigen ~ ist eine Äquivalenzrelation. 

(1) Reflexivität: (a,b)∈|Nx|N
gilt(a,b)~(a,b)?
a+b=a+b (JA)

(2)Symmetrie: Sei(a,b) und (c,d) ∈|Nx|N
zZ: (a,b)~(c,d)
    <=>(c,d)~(a,b)
Beweis:
  (a,b)~(c,d)
  <=> a+d=c+b         (Definition anwenden)
  <=> c+b=a+d
  <=> (c,d)~(a,b)     (Definition anwenden)

(3) Transitivität:
Sei (x,y), (x',y'),(x",y") ∈ (|Nx|N)x(|Nx|N)
Wir setzen voraus, dass:
 (x,y)~(x',y') und (x',y')~(x",y") gilt
 Wir müssen zeigen: (x,y)~(x",y")
 Def: x+y'=x'+y und x'+y"=x"+y'
 Wir addieren beide Gleichungen: x+y'+x'+y"=x'+y+x"+y'
                                =>x+y"=y+x"
                                =>(x,y)~(x",y")   (Definition)

Übung:
(11,7)~(4,0)~(5,1)~(28,24)~........

Äquivalenzklassen:
Sei R ⊆AxA eine Äquivalenzrelation und a∈A so definieren wir die Äquivalenzklasse [a]R als die Menge {x∈A|xRa} 

Lemma: Sein a,b∈A  und R eine Äquivalenzrelation dann gilt:
[a]r ⋂[b]R= ∅
<=> ¬(aRb)

Beweis: 
g.Z.Z. [a]R ⋂[b]R ≠  ∅
<=> aRb
"=>": Sei x ∈ [a]R ⋂ [b]R 

Nach Definition gilt xRa und xRb
=> (aRx) ⋀(xRb)
=> aRb (Transitivität)

"<=": Sei aRb
=> a ∈ [b]R        wir wissen aber auch a ∈ [a]R
=> a ∈ [a]R ⋂ [B]R ≠ ∅   :-)

Satz: Sei R eine Äquivalenzrelation, dann bildet die Menge der Äquivalenzklassen eine Partition
P = {[a]R    | a ∈ A}    :-)

S ist ein Repräsentantensystem von der Partition P gdw. ("genau dann, wenn") S aus jeder MEnge von P genau ein Element enthält


wir müssen das alles nicht verstehen. alles metal geht nach hause. Alles klar! :)
sehr schwer isses ja nun doch nicht


Übung:
0. A ⋃ B = {x | xa ⋃ xb}
1. (Ā ⋂ B)\C = {x | 0 }  = (¬xa ⋂ xb) ⋂ ¬xc)} = ∅
2. A\(B\C) = {x | xa ⋂ ¬(xb⋂¬xc)}
3. (C ⋂ B) ∪ (B ⋂ A)∪(!C) = { x | ((xc⋂xb)⋃(xb⋂xa))⋃(¬xc) }
    _________
4. (A ⋂ B ⋂ C) = { x | ¬(xa⋂xb⋂xc)}


Umkehrung: Stellen Sie die folgende Menge nur mit Hilfe von A, B, C und der Mengenoperationen dar.

5. { x | ¬xa ∪ (¬xa ⋂ xb)} =  !A ∪ (!A ⋂ B) = !A
6. {x|xa ∪ xb)⋂(xa ∪ !xb) = (A ∪ B)⋂(A ∪ !B) = A⋃(B⋂!B) = A
7. {x|xa ⋂(xb ∪ xc)} = A ⋂ (B ∪ C)




Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀ , ⋁, ¬, →, ↔, ☇, √, ∤, |, ≥, ≤, ≠, ∪, ⊂, ⊃, ⊆, ⊇, ○, Ā, Ē, Ū, Ō