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

Aus VoWi
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

Reflexiviät:

Transitivität:

Antisymmetrie:

Lösungsvorschlag von L[Bearbeiten | Quelltext bearbeiten]

zu a)


Da reflexiv ist, muss für jedes Element in gelten:

Da transitiv ist, muss für alle Element in gelten:


zu b)

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


Da reflexiv und transitiv ist, ist eine Quasiordnung.

Reflexivität: (siehe a)

Transitivität: (siehe a)


zu c)

Reflexivität:

Antisymmetrie:

Transitivität:


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


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