TU Wien:Mathematisches Arbeiten VU (Hetzl)/Übungen 2023W/Beispiel 7

Aufgabe 1. Sei A eine Menge und sei R eine beliebige Relation auf A. Die reflexiv-transitive Hülle von R ist eine Relation R* auf A die wie folgt definiert ist:

x R* y :⇔ ∃n ≥ 1, x1, ... , xn ∈ A so dass x = x1 R x2 R · · · R xn = y .

Beachten Sie dass x = x1 = xn = y dabei auch möglich ist. Im Webseiten-Beispiel der Vorlesung würde etwa R den Hyperlinks und R* der Erreichbarkeit durch Hyperlinks entsprechen.

a) Sei A0 = {0, 1, 2, 3} und R0 = {(0, 1), (1, 2), (2, 3)}. Bestimmen Sie R*0.

Sei nun A wieder eine beliebige Menge und R eine beliebige Relation auf A.

b) Zeigen Sie dass R* eine Quasiordnung ist.

Sei X eine Menge.

c) Zeigen Sie dass (P(X), ⊆) eine partielle Ordnung ist.

Jetzt setzen wir X = A × A. Dann ist (P(X ), ⊆) eine Relation auf den Relationen auf A. Für zwei Relationen R1 und R2 auf A ist R1 ⊆ R2 gleichbedeutend mit ∀x, y ∈ A (x R1 y ⇒ x R2 y). Ist zum Beispiel A die Menge aller für diese Lehrveranstaltung angemeldeten Studenten, R1 die Relation den selben Geburtstag zu haben und R2 die Relation das selbe Geburtsjahr zu haben, dann gilt R1 ⊆ R2.

d) Zeigen Sie dass R* die kleinste Quasiordnung (bezüglich ⊆) ist, die R enthält. D.h. genauer: Zeigen Sie dass für jede Quasiordnung S mit R ⊆ S gilt: R* ⊆ S.

Hinweis: Die einzelnen Unterpunkte können unabhängig voneinander gelöst werden.

Dieses Beispiel ist als unsolved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Dieses Beispiel hat noch keinen Lösungsvorschlag. Um einen zu erstellen, kopiere folgende Zeilen, bearbeite die Seite und aktualisiere den status=unsolved Mögliche status=... Werte stehen hier: Vorlage:Beispiel

== Lösungsvorschlag von ~~~ ==
--~~~~

Siehe auch Hilfe:Formeln und Hilfe:Beispielseiten.

Hilfreiches

Reflexiviät: $\mathrm{\forall }a\in A:aRa$

Transitivität: $\mathrm{\forall }a,b,c\in A:aRb\wedge bRc\Rightarrow aRc$

Antisymmetrie: $\mathrm{\forall }a,b\in A:aRb\wedge bRa\Rightarrow a=b$

Lösungsvorschlag von L

zu a)

$R_0^{\ast }=\{(0,0),(0,1),(0,2),(0,3),(1,1),(1,2),(1,3),(2,2),(2,3)\}$

Da $R_0^{\ast }$ reflexiv ist, muss für jedes Element in $A_0$ gelten: $\mathrm{\forall }a\in A_0:aRa$

Da $R_0^{\ast }$ transitiv ist, muss für alle Element in $A_0$ gelten: $\mathrm{\forall }a,b,c\in A_0:aRb\wedge bRc\Rightarrow aRc$

zu b)

R ist eine Quasiordnung, wenn R reflexiv und transitiv ist.

Da $R^{\ast }$reflexiv und transitiv ist, ist $R^{\ast }$eine Quasiordnung.

Reflexivität: $\mathrm{\forall }a\in A:aRa$ (siehe a)

Transitivität: $\mathrm{\forall }a,b,c\in A:aRb\wedge bRc\Rightarrow aRc$ (siehe a)

zu c)

Reflexivität: $\mathrm{\forall }x\in X:xRx$

Antisymmetrie: $\mathrm{\forall }x,y\in X:xRy\wedge yRx\Rightarrow x=y$

Transitivität: $\mathrm{\forall }x,y,z\in X:xRy\wedge yRz\Rightarrow xRz$

Da die Potenzmenge all diese Eigenschaften besitzt, ist sie auch eine partielle Ordnung

--L 22:05, 27. Nov. 2023 (CET)