Theoretische Informatik (Vorlesung 4)

Sei M eine Menge. Eine zweistellige Relation R ist eine Teilmenge R ⊂ MxM. Für ( x, y) ∈ R schreiben wir xRy ( x steht in Relation zu y)
Bsp.: <, =, > = {(x,y) ∈ NxN, x = y} = N x N
Eine Relation heißt:
1. reflexiv, wenn für alle x ∈ M : xRx
  1. ≤ ↔ ja
  2. = ↔ ja
  3. < ↔ nein ( da z.B.: 3 < 3 falsch ist )
2. symmetrisch, wenn für alle x,y ∈ M: xRy → yRx
  1. ≤ ↔ nein ( da 3 = 5 aber 5 = 3 ! )
  2. = ↔ ja
  3. < ↔ nein
3. asymmetrisch, wenn für alle x,y ∈ M: xRy → ¬(yRx)
  1. ≤ ↔ nein ( da 5 = 5 → wahr, aber ¬ ( 5 = 5 ) → falsch )
  2. = ↔ nein
  3. < ↔ ja
4. antisymmetrisch, wenn für alle x,y ∈ M: xRy und yRx folgt: x = y
  1. ≤ ↔ ja
  2. = ↔ ja
  3. < ↔ ja ( da es keine gültige Lösung für die Vorbedingung gibt → leere Menge, für diese ist es wieder wahr )
5. transitiv, wenn für alle x,y,z ∈ M aus xRy und yRz => xRz
  1. gilt für alle Operationen

Sei R eine zweistellige Relation auf M. Dann heißt R eine Äquivlanzrelation, wenn R:
1. reflexiv,
2. symmetrisch und
3. transitiv ist
Beispiel: Drei Parallele Geraden im ℝ² ( Parallelität ist eine Äquivalenzrelation )

Sei M die Menge aller Schüler eine Schule. Ein Schüler X stehe in Relation zu Schüler Y, wenn X und Y die selbe Klassen besuchen. ( X ~ Y )

Reflexivität: ( X ~ X )
- Schüler X steht in Relation zu sich selbst
Symmetrie: X ~ Y → Y ~ X
- Wenn X die Klasse besucht, besucht auch Y diese
Transitivität: X ~ Y → Y ~ Z → X ~ Z
- Wenn X die Klasse mit Y besucht und Y die Klasse mit Z, dann besucht X und Z die gleiche Klasse

Hiermit haben wir bewiesen, dass die definierte Relation eine Äquivalenzrelation ist.

[X]^~ = { y ∈ M, X~Y ) = Wenn X ein Schüler der Klasse 6c ist, dann sind [X]^~ alle Schüler der Klasse 6c. Alle Schüler einer bestimmten Eigenschaft (Schulklasse) werden in Äquivalenzklassen zusammengefasst.
X ∈ [X]^~ ( X ist immer Teil seiner eigenen Äquivalenzklasse )
a) Für alle x,y ∈ M mit X ~ Y gilt [X]^~ = [Y]^~
- zz.:
  - [X]^~ ⊂ [Y]^~, [Y]^~ ⊂ [X]^~ sei z ∈ [X]^~, also gilt X ~ Z.
  - Aus der Symmetrie folgt Z ~ X.
  - Da X ~ Y, folgt aus der Transitivität Z ~ Y.
  - Wieder aus der Symmetrie folgt Y ~ Z und damit Z ∈ [Y]^~
b) Für alle x,y ∈ M mit x ~/~ y gilt [X]^~ ∩ [Y]^~ = Ø ( leere Menge )
- Da X in keiner Relation zu Y steht, handelt es sich bei deren Äquivalenzklassen um 2 verschiedene Teilmengen aus M. Diese Teilmengen repräsentieren disjunkten Äquivalenzklassen und erzeugen bei der Schnittmengen-Operation die leere Menge.