Aus Relation mach' ÄR

21.10.2009, 22:36

Airblader

Aus Relation mach' ÄR

Hi,

so - das Studium hat angefangen! Big Laugh

Wir hatten die Vorlesungen dazu noch nicht, aber ich habe mir das LAAG I - Übungsblatt schonmal angeschaut.

Folgende Aufgabe:

Zitat:

Zeigen Sie, dass es zu jeder Relation $\begin{eqnarray*} \mathcal R \subseteq A \times A \end{eqnarray*}$ eine Äquivalenzrelation gibt, die $\begin{eqnarray*} \mathcal R \end{eqnarray*}$ enthält.

Da ja nur verlangt ist, dass die Relation enthalten ist, und ich mit "enthalten" zunächst mal verstehen würde, dass sie eine Teilmenge ist, - kann ich nicht ganz stupide einfach $\begin{eqnarray*} \mathcal R^* = A^2 \end{eqnarray*}$ nehmen?
Dies muss doch immer eine Äquivalenzrelation sein, oder übersehe ich da gerade was?

Da ja schlicht alle nur denkbaren Paare von A² enthalten sind, ist sowohl Reflexivität als auch Symmetrie klar.
Und aus dem selben Grund muss auch Transitivität gelten. Jedes Paar ist drin - unerheblich, welche anderen enthalten sind. Dies schließt aber eben auch Transitivität ein.

Wie gesagt - ist das so banal, oder übersehe ich was? Dass ich das natürlich etwas besser begründen sollte, wäre schon klar.

air

21.10.2009, 22:39

Duedi

Auf diesen Beitrag antworten »

Ich denke, das ist korrekt.

21.10.2009, 22:57

Mystic

Auf diesen Beitrag antworten »

Wäre $\begin{eqnarray*} A \times A \end{eqnarray*}$ keine Äquivalenzrelation, dann wäre ja auch dein Satz falsch, da er ja insbesondere für $\begin{eqnarray*} \mathcal R = A \times A \end{eqnarray*}$ gelten sollte...

21.10.2009, 23:00

Airblader

Auf diesen Beitrag antworten »

Sorry - da komme ich nicht mit. Auf welchen Satz beziehst du dich nun?

Bei der Formulierung haper' ich noch. Das Ganze scheint mir so trivial, dass ich keine bedeutend bessere Erklärung finde, als dass sich alle drei Eigenschaften daraus ergeben, dass alle möglichen Paare auch vorhanden sind.

air

21.10.2009, 23:04

Mystic

Auf diesen Beitrag antworten »

Ich bezieh mich auf die zu zeigende Behauptung im Eingangsposting, nämlich

Zitat:

Zeigen Sie, dass es zu jeder Relation $\begin{eqnarray*} \mathcal R \subseteq A \times A \end{eqnarray*}$ eine Äquivalenzrelation gibt, die $\begin{eqnarray*} \mathcal R \end{eqnarray*}$ enthält.

Insbesondere muss das ja für $\begin{eqnarray*} \mathcal R = A \times A \end{eqnarray*}$ selbst gelten, sonst wäre ja die Behauptung glatt falsch... Big Laugh

21.10.2009, 23:08

Airblader

Auf diesen Beitrag antworten »

Edit: Ah - nun habe ich verstanden, was du meinst!

Wenn man schon als Relation A² nimmt, dann ist die einzig' mögliche "Erweiterung" zur Äquivalenzrelation ja auch nur A², sprich: Es muss A² auch eine ÄR sein. Richtig?

Okay - dann haben wir das Augenzwinkern

Jetzt macht mir die Formulierung noch etwas Probleme (s.o.). Hinweise, Anregungen?

air

(Edit #2: Wobei ich diese Argumentation natürlich nicht als Argument für "A² ist ÄR" nehmen kann - die Gültigkeit des Satzes einfach voraussetzen und daraus Schlüsse ziehen ist doch nicht so ganz super Augenzwinkern

Aber so hast du es ja auch nicht gemeint.)

21.10.2009, 23:23

Mystic

Auf diesen Beitrag antworten »

Man kann entweder alle drei Eigenschaften einer Äquivalenzrelation - Reflexivität, Symmetrie und Transitivität - formal durchgehen, die aber immer nur verlangen, dass gewisse Elemente in der zu untersuchenden Relation liegen, was aber für die Allrealtion, die ja alle Paare in A x A enthält, dann trivialerweise gilt, oder man macht sich das mit Hilfe der Bijektion zwischen Partitionen der Menge A und den Äquivalenzrealtionen auf A klar. Der Allrelation entspricht dabei einfach die Partition, die nur eine Klasse, nämlich A, enthält...

21.10.2009, 23:31

Airblader

Auf diesen Beitrag antworten »

Ja .. äh ... letztere Methode lassen wir mal außen vor! Big Laugh

Ich würde nun eben alle drei Eigenschaften ansprechen. Darf ich hier also wirklich auch davon ausgehen, dass diese drei Eigenschaften trivialerweise erfüllt sind?

air

21.10.2009, 23:37

Mystic

Auf diesen Beitrag antworten »

Ja, das sind sie... Daher werden die Allrelation und die identische Relation auch oft die "trivialen" Äquivalenzrelationen auf A genannt, weill es sie einerseits immer gibt und andererseits der Nachweis der 3 Eigenschaften einer Äquivalenzrelation kinderleicht ist... Augenzwinkern

21.10.2009, 23:44

Airblader

Auf diesen Beitrag antworten »

Okay. Dann wars doch so banal wie ich dachte. Big Laugh

Es geht übrigens noch weiter:

Zitat:

Begründen Sie, warum diese Aussage für Ordnungsrelationen falsch ist.

Simple Antwort: Sobald zwei Paare (a,b) und (b,a) mit a,b € A und a ungleich b in der Relation enthalten sind, ist eine Anti-Symmetrie unmöglich.
Durch Hinzufügen erhält man hier also keine Ordnungsrelation, viel mehr müsste man hier Paare der Relation entfernen (dann wäre R aber nicht mehr enthalten).

Richtig?

air

21.10.2009, 23:49

Mystic

Auf diesen Beitrag antworten »

Ja, richtig... Hier gilt der Satz, dass in jeder Relation $\begin{eqnarray*} \mathcal R \end{eqnarray*}$ auf A, die wenigstens reflexiv ist, eine Ordnungsrelation enthalten ist, nämlich die identische Relation auf A...

21.10.2009, 23:53

Airblader

Auf diesen Beitrag antworten »

Okay. Supi.

Dann bin ich mit dem ersten Übungsblatt sogar schon durch. Naja, okay, fast. Beim Beweis von Schröder-Bernstein weiß ich nicht, ob ich mich auf endliche Mengen beschränken darf - ja, ich weiß ... wenns nicht dasteht, dann nicht. Aber wie es aussieht wird der Beweis andernfalls wesentlich komplexer*.

Da wir aber die Vorlesungen zu dem Blatt noch gar nicht hatten, kann ich das ja mal getrost abwarten und nachfragen Augenzwinkern

Danke auf jeden Fall!

*) Dieser Beweis ist "Literaturrecherche", also durchaus so gedacht, dass ich nachschauen darf! Big Laugh

air

Neue Frage »

Antworten »

Aus Relation mach' ÄR

Verwandte Themen