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