Hüllen einer binären Relation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] $\!R\$ [/mm] eine binäre Relation, deren beide Bereiche die selbe Menge [mm] $\!M\$ [/mm] sind. Die transitive Hülle von [mm] $\!R\$ [/mm] ist die kleinste Teilmenge von $M [mm] \times [/mm] M$, die eine Obermenge von [mm] $\!R\$ [/mm] und transitiv ist.
Sei [mm] $\IN_{1} [/mm] := [mm] \IN \backslash \{0\}.$ [/mm] Zeigen Sie: die transitive Hülle von [mm] $\!R\$ [/mm] ist [mm] $R^{+}=\bigcup_{n \in \IN_{1}}R^{n}.$ [/mm] |
Hallo,
mir bereitet diese Aufgabe leider etliche Schwierigkeiten...
Mir ist nicht klar, was hier verlangt wird und vor allem was hier gemacht wird. Von daher wäre es sehr nett, wenn jemand in einfachen Worten schreiben könnte, was Sache ist. 
Lösung:
Behauptung: [mm] $R^{+}\subseteq [/mm] M [mm] \times [/mm] M$
Gilt, da [mm] $R^{n} \subseteq [/mm] M [mm] \times [/mm] M$ für alle $n [mm] \in \IN.$
[/mm]
Behauptung: [mm] $R^{+} \supseteq [/mm] R$
Es gilt [mm] $R=R^{1} \subseteq \bigcup_{n \in \IN_{1}}R^{n}=R^{+}.$
[/mm]
Behauptung: [mm] $R^{+}$ [/mm] ist transitiv
Sei [mm] $xR^{+}y$ [/mm] und [mm] $yR^{+}z.$
[/mm]
Dann gibt es $i,j [mm] \in \IN$ [/mm] mit [mm] $xR^{i}y$ [/mm] und [mm] $yR^{j}z.$
[/mm]
Dann gilt [mm] $x(R^{i} \circ R^{j})z,$ [/mm] also [mm] $xR^{i+j}z,$ [/mm] also [mm] $xR^{+}z.$
[/mm]
Behauptung: [mm] $R^{+}$ [/mm] ist die kleinste derartige Relation,
d.h., für jedes transitive $R'$ mit $R [mm] \subseteq [/mm] R' [mm] \subseteq [/mm] M [mm] \times [/mm] M$ gilt [mm] $R^{+} \subseteq [/mm] R'.$
Sei $R'$ eine transitive Relation mit $R [mm] \subseteq [/mm] R' [mm] \subseteq [/mm] M [mm] \times [/mm] M.$
Lemma: für alle $n [mm] \in \IN_{1}$ [/mm] gilt [mm] $R^{n} \subseteq [/mm] R'.$
Damit gilt dann auch [mm] $R^{+}=\bigcup_{n \in \IN_{1}}R^{n} \subseteq [/mm] R'.$
Beweis des Lemmas durch vollständige Induktion nach n
Induktionsbasis n=1: [mm] $R^{1}=R \subseteq [/mm] R'$ Voraussetzung
Induktionsannahme: [mm] $R^{n} \subseteq [/mm] R'$
Induktionsbehauptung: [mm] $R^{n+1} \subseteq [/mm] R'$
Induktionsschritt:
Sei [mm] $xR^{n+1}z,$ [/mm] also $x(R [mm] \circ R^{n}).$ [/mm] Def. Potenz
Dann gibt es $y [mm] \in [/mm] M$ mit [mm] $\!xRy\$ [/mm] und [mm] $yR^{n}z.$ [/mm] Def. [mm] $\circ$
[/mm]
Dann $xR'y$ wegen $R [mm] \subseteq [/mm] R'$ Voraussetzung
und $yR'z$ wegen [mm] $R^{n} \subseteq [/mm] R'$ Induktionsannahme
Dann $xR'z$ wegen Transitivität $R'$ Voraussetzung
Vielen Dank!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:09 Di 06.09.2011 | | Autor: | statler |
Guten Morgen!
> Sei [mm]\!R\[/mm] eine binäre Relation, deren beide Bereiche die
> selbe Menge [mm]\!M\[/mm] sind. Die transitive Hülle von [mm]\!R\[/mm] ist
> die kleinste Teilmenge von [mm]M \times M[/mm], die eine Obermenge
> von [mm]\!R\[/mm] und transitiv ist.
>
> Sei [mm]\IN_{1} := \IN \backslash \{0\}.[/mm] Zeigen Sie: die
> transitive Hülle von [mm]\!R\[/mm] ist [mm]R^{+}=\bigcup_{n \in \IN_{1}}R^{n}.[/mm]
>
> Hallo,
>
> mir bereitet diese Aufgabe leider etliche
> Schwierigkeiten...
> Mir ist nicht klar, was hier verlangt wird und vor allem
> was hier gemacht wird. Von daher wäre es sehr nett, wenn
> jemand in einfachen Worten schreiben könnte, was Sache
> ist.
Das oder ein Problem liegt wohl darin, daß du nicht gesagt hast, was [mm] R^n [/mm] ist. Es ist hier jedenfalls nicht das, was man in der Mengenlehre - und Relationen gehören zur Mengenlehre - gemeinhin darunter versteht.
Üblicherweise ist [mm] R^n [/mm] das n-fache cartesische Produkt mit sich selbst. Aber dann ist [mm] R^n [/mm] eine Teilmenge von [mm] M^{2n}, [/mm] was sofort der 1. Behauptung in deiner Lösung widerspricht.
> Lösung:
>
> Behauptung: [mm]R^{+}\subseteq M \times M[/mm]
> Gilt, da [mm]R^{n} \subseteq M \times M[/mm]
> für alle [mm]n \in \IN.[/mm]
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:09 Di 06.09.2011 | | Autor: | el_grecco |
Hallo Dieter,
Danke für Deinen Beitrag.
Diesen Themenbereich haben wir nur kurz angeschnitten (Vorlesung: Logik und diskrete Strukturen) und ein Skript gibt es leider nicht.
Inzwischen denke ich, dass allenfalls eine vollständige Induktion in diesem Themenzusammenhang in der Klausur vorkommen könnte, welche mir hier aber verständlich ist.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Do 08.09.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
