www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Relationen" - Hüllen einer binären Relation
Hüllen einer binären Relation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Hüllen einer binären Relation: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 23:24 Mo 05.09.2011
Autor: el_grecco

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


        
Bezug
Hüllen einer binären Relation: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Hüllen einer binären Relation: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
        
Bezug
Hüllen einer binären Relation: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:20 Do 08.09.2011
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.mathebank.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]