Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » kleinste reflexiv-transitive Relation

kleinste reflexiv-transitive Relation

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges

Komisch aktiv_icon

12:21 Uhr, 15.12.2014

Hallo,

ich wollte fragen, was "kleinste" in diesem Zusammenhang bedeutet - was versteht man unter der Eigenschaft in Bezug auf Relationen?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DrBoogie aktiv_icon

12:47 Uhr, 15.12.2014

Die kleinste Anzahl der Paare, also die kleinste Mächtigkeit der Relation als Menge gesehen.

Komisch aktiv_icon

14:14 Uhr, 15.12.2014

hmm gut,

auf Wikipedia steht:

R^{*}

ist die kleinste reflexive und transitive Relation, die R enthält. Wie zeigt man sowas? Also ich meine man kann

R^{*}

ja als

R^{*} := ⋃_{i \in ℕ_{0}} R^{i}

darstellen und dann müsste ich ja irgendwie zeigen können, dass jede echte Teilmenge von

R^{*}

nicht reflexiv und transitiv ist. Kann mir jemand zeigen wie zu dieser Aussage der Beweis aussehen würde? (Für mich ist das nicht selbstverständlich, dass es so ist - anders gesagt ich verstehe es nicht.) de.wikipedia.org/wiki/Transitive_H%C3%BClle_(Relation)#Eigenschaften

DrBoogie aktiv_icon

14:18 Uhr, 15.12.2014

Brauchst Du wirklich so einen abstrakten Beweis oder hast Du vielleicht einen einfacheren Fall? Was ist genau Deine Aufgabe?

Komisch aktiv_icon

14:39 Uhr, 15.12.2014

Hmm, naja

also dass

R^{*}

reflexiv ist folgt ja aus der Identität also

R^{0} = i d_{M}

. Damit bildet die Relation auf sich selbst ab. Die Transitivität folgt aus der Tatsache, dass für

(x, y) \in R^{t}

und

(y, z) \in R^{s}

mit

x, y, z \in M

und

t, s \geq 0

damit ist dann

R^{t} \circ R^{s} = R^{s + t}

.

Aber dies schließt ja nicht aus, dass es auch andere Teilmengen von

R^{*}

gibt die transitiv und reflexiv sind oder?

Ps.: Meine Aufgabe ist es zu zeigen, dass

R^{*}

die kleinste transitiv, reflexive Relation ist.

DrBoogie aktiv_icon

14:46 Uhr, 15.12.2014

Irgendwei schaffst Du es nicht, Deine Aufgabe rüber zu bringen.
Du musst beweisen, dass

R^{*}

transitiv-reflexive Hülle ist?
Wie ist dann

R^{*}

definiert?

Komisch aktiv_icon

14:53 Uhr, 15.12.2014

Zeigen Sie: R* ist die kleinste reflexiv-transitive Relation, die R umfasst. (R ist eine binäre Relation auf MxM)

Das ist die Aufgabe die ich versuche zu lösen.

DrBoogie aktiv_icon

15:02 Uhr, 15.12.2014

Fantastisch.
Und was ist denn

R^{*}

. Wie ist es definiert?

Komisch aktiv_icon

15:11 Uhr, 15.12.2014

Ähm joar also folgendes ist gegeben:

R^{0} := i d_{A}

R^{i + 1} := R^{i} \circ R, i \in ℕ_{0}

und

R^{*} := ⋃_{i \in ℕ_{0}} R^{i}

Dachte, dass das allgemein gültig ist.

DrBoogie aktiv_icon

15:28 Uhr, 15.12.2014

Das jede transitive und reflexive Hülle

R^*

enthält, ist einfach zu zeigen.
Jede reflexive Hülle muss zuerst mal

R^0

enthalten.
Und für jede

(r_1, r_n)

aus

R^n

gilt ja

r_1 R^+ r_2

,...,

r_{n - 1} R^+ r_n

, woraus folgt:

(r_1, r_n)

in der transitiven Hülle von

R

, also

R^n \ s u b s e t

transitive Hülle von

R

, stimmt für jede transitive Hülle.

Damit

R^* = R^0 \ c u p R^1 \ c u p R^2 \ c u p R^3 . . .

ist in jeder reflexiven transitiven Hülle drin.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1205612

1205562

	Status: nicht eingeloggt	Noch nicht registriert?