Relationen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei R [mm] \subseteq \IN^{2} [/mm] mit R = { (1,2), (2,3), (1,3)}
R ist antisymmetrisch und transitiv. |
Hallo,
Relationen sind lange her.
Die Definition für Antisymmetrie ist folgende Definition:
R heißt antisymmetrisch, falls für alle x,y [mm] \in \forall [/mm] aus xRy und yRx stets folgt x = y.
Ok, schon mal gut.
Aber ich verstehe nicht, warum die Relation in der Aufgabenstellung antisymmetrisch sein soll. Wie prüft man das noch mal? Wir haben zum Beispiel (1,2) und (2,3)
ist x = (1,2) und y = (2,3) ? Ich habe leider keinen blassen Schimmer und bin auf Hilfe angewiesen, wie immer :)
Zweite Frage: Was soll R für eine Relation sein ? kleiner gleich, größer etc ? Warum wurde hier die Relation nicht näher beschrieben?
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:44 So 13.11.2016 | | Autor: | tobit09 |
Hallo pc_doctor!
> Die Definition für Antisymmetrie ist folgende Definition:
> R heißt antisymmetrisch, falls für alle x,y [mm]\in \forall[/mm]
> aus xRy und yRx stets folgt x = y.
Es muss (in unserem Beispiel) heißen: "..., falls für alle [mm] $x,y\in\red{\IN}$..."
[/mm]
Im Allgemeinen muss es heißen: "..., falls für alle [mm] $x,y\in \red{M}$...", [/mm] wenn R eine (binäre) Relation auf $M$, d.h. eine Teilmenge von [mm] $M^2$ [/mm] ist.
> Aber ich verstehe nicht, warum die Relation in der
> Aufgabenstellung antisymmetrisch sein soll. Wie prüft man
> das noch mal? Wir haben zum Beispiel (1,2) und (2,3)
> ist x = (1,2) und y = (2,3) ?
x und y sind hier natürliche Zahlen, nicht Elemente von $R$!
Zunächst ein formaler Beweis der Antisymmetrie:
Seien also [mm] $x,y\in\IN$.
[/mm]
Wir müssen zeigen: Aus $xRy$ und $yRx$ folgt $x=y$.
Gelte also $xRy$ und $yRx$.
Zu zeigen ist $x=y$.
Wie können x und y nur aussehen?
Wegen $xRy$ liegt einer der Fälle
1. x=1 und y=2
2. x=2 und y=3
3. x=1 und y=3
vor.
In jedem dieser Fälle erhalten wir [mm] $\neg [/mm] yRx$ im Widerspruch zu $yRx$.
Aus dem Widerspruch können wir alles, insbesondere $x=y$ folgern.
Der Kern dieses Beweises ist im Grunde folgender: Der Fall "$xRy$ und $yRx$" tritt hier nie ein, egal wie wir [mm] $x,y\in\IN$ [/mm] wählen. Daher müssen wir auch für keinen Fall wirklich nachweisen, dass $x=y$ gilt.
Vielleicht magst du mal folgende Relationen auf [mm] $\IN$ [/mm] auf Antisymmetrie untersuchen?
[mm] $R_1:=\{(1,1),(1,2)\}$
[/mm]
[mm] $R_2:=\{(1,1),(1,2),(2,1)\}$.
[/mm]
> Zweite Frage: Was soll R für eine Relation sein ? kleiner
> gleich, größer etc ? Warum wurde hier die Relation nicht
> näher beschrieben?
Die Relation wurde ja vollständig angegeben.
Es gilt [mm] $xRy\iff (x,y)\in [/mm] R$, also $1R2$, $2R3$ und $1R3$, aber z.B. [mm] $\neg [/mm] 3R4$ und [mm] $\neg [/mm] 3R1$.
Die vorliegende Relation R stimmt mit keiner der "vertrauten" Relationen auf [mm] $\IN$ [/mm] wie "kleiner gleich", "größer", ... überein.
Viele Grüße
Tobias
|
|
|
| |
|
>
> Zunächst ein formaler Beweis der Antisymmetrie:
>
> Seien also [mm]x,y\in\IN[/mm].
> Wir müssen zeigen: Aus [mm]xRy[/mm] und [mm]yRx[/mm] folgt [mm]x=y[/mm].
>
> Gelte also [mm]xRy[/mm] und [mm]yRx[/mm].
> Zu zeigen ist [mm]x=y[/mm].
>
> Wie können x und y nur aussehen?
> Wegen [mm]xRy[/mm] liegt einer der Fälle
> 1. x=1 und y=2
> 2. x=2 und y=3
> 3. x=1 und y=3
> vor.
> In jedem dieser Fälle erhalten wir [mm]\neg yRx[/mm] im
> Widerspruch zu [mm]yRx[/mm].
> Aus dem Widerspruch können wir alles, insbesondere [mm]x=y[/mm]
> folgern.
Hallo nochmal,
das verstehe ich irgendwie nicht. Ich sehe hier noch nicht die Antisymmetrie.
Wenn wir
> 1. x=1 und y=2
> 2. x=2 und y=3
> 3. x=1 und y=3
haben , dann folgt daraus NICHT, dass x=y ist.
Zweiter Teil der Frage, deine Relationen:
$ [mm] R_1:=\{(1,1),(1,2)\} [/mm] $
$ [mm] R_2:=\{(1,1),(1,2),(2,1)\} [/mm] $.
Zu zeigen ist die Antisymmetrie.
Aus $ xRy $ und $ yRx $ folgt $ x=y $.
Es gelte also xRy und yRx
Für [mm] R_1 [/mm] :
1. x = 1 und y = 1 => x=y( erstes Tupel)
2. x = 1 und y = 2 => keine Antisymmetrie(zweites Tupel)
3. x = 1 und y = 2 => keine Antisymmetrie(erstes Tupel x und zweites Tupel y)
4. x = 1 und y = 1 = > x=y ( das x=1 aus dem zweiten Tupel und das y = 1 aus dem ersten Tupel)
Für [mm] R_2:
[/mm]
1. x = 1 und y = 1 = > x=y ( erstes Tupel)
2. x = 1 und y = 2 => keine Antisymm. (zweites Tupel)
3. x = 2 und y = 1 => keine Antisymm. (drittes Tupel)
4. x = 1 und y = 2 => keine Antisymm. (erstes Tupel x=1 und zweites Tupel y =2)
5. x = 1 und y = 1 => x=y (erstes Tupel x=1 und drittes Tupel y = 1)
6. x = 2 und y = 2 => x=y ( drittes Tupel x =2 und zweites Tupel y =2)
usw..
Deshalb dritte Frage:
Wie wir sehen, ist zum Beispiel die Nummer 4 bei [mm] R_2 [/mm] nicht antisymmetrisch. Wann kann man sagen, dass eine Relation antisymmetrisch ist? Wenn sie MINDESTENS eine Relation mit xRy und yRx hat, sodass x=y gilt ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:40 So 13.11.2016 | | Autor: | tobit09 |
> > Gelte also [mm]xRy[/mm] und [mm]yRx[/mm].
> > Zu zeigen ist [mm]x=y[/mm].
> >
> > Wie können x und y nur aussehen?
> > Wegen [mm]xRy[/mm] liegt einer der Fälle
> > 1. x=1 und y=2
> > 2. x=2 und y=3
> > 3. x=1 und y=3
> > vor.
> > In jedem dieser Fälle erhalten wir [mm]\neg yRx[/mm] im
> > Widerspruch zu [mm]yRx[/mm].
> > Aus dem Widerspruch können wir alles, insbesondere [mm]x=y[/mm]
> > folgern.
> das verstehe ich irgendwie nicht. Ich sehe hier noch nicht
> die Antisymmetrie.
Gut, dass du nachfragst. Mein Beweis war zwar formal richtig, aber wohl keine didaktische Meisterleistung...
> Wenn wir
> > 1. x=1 und y=2
> > 2. x=2 und y=3
> > 3. x=1 und y=3
> haben , dann folgt daraus NICHT, dass x=y ist.
Daraus alleine in der Tat nicht. Aber zusammen mit der Annahme $yRx$ (siehe die oberste zitierte Zeile dieses Beitrages) erhalten wir einen Widerspruch:
In allen drei Fällen liegt nämlich $yRx$ jeweils NICHT vor, wie man an der Definition von R sieht.
Alleine aus der Annahme [mm] $x,y\in\IN$ [/mm] mit $xRy$ und $yRx$ haben wir also einen Widerspruch erhalten.
Also kann dieser Fall gar nicht vorliegen.
Die vorliegende Relation heißt antisymmetrisch, wenn für alle [mm] $x,y\in\IN$ [/mm] gilt:
Aus xRy und yRx folgt $x=y$.
Seien also [mm] $x,y\in\IN$.
[/mm]
Zu zeigen ist: Aus xRy und yRx folgt x=y (mit anderen Worten: Wenn xRy und yRx, dann x=y.)
Das haben wir nun dadurch gezeigt, dass wir nachgewiesen haben, dass NICHT ($xRy$ und $yRx$) gilt.
Oder um Freds (sehr guten!) Vorschlag aufzugreifen:
Angenommen R wäre nicht antisymmetrisch.
Dann gäbe es [mm] $x,y\in\IN$ [/mm] mit $xRy$ und $yRx$, aber [mm] $x\not=y$.
[/mm]
Nun führen wir wie von mir oben dargestellt allein schon die Annahme $xRy$ und $yRx$ zum Widerspruch.
Also war die Annahme, R wäre nicht antisymmetrisch, falsch und somit ist R tatsächlich antisymmetrisch.
> Zweiter Teil der Frage, deine Relationen:
>
> [mm]R_1:=\{(1,1),(1,2)\}[/mm]
> [mm]R_2:=\{(1,1),(1,2),(2,1)\} [/mm].
>
> Zu zeigen ist die Antisymmetrie.
> Aus [mm]xRy[/mm] und [mm]yRx[/mm] folgt [mm]x=y [/mm].
> Es gelte also xRy und yRx
>
> Für [mm]R_1[/mm] :
> 1. x = 1 und y = 1 => x=y( erstes Tupel)
Ja.
> 2. x = 1 und y = 2 => keine Antisymmetrie(zweites Tupel)
Keine Antisymmetrie bedeutet, wie Fred schrieb: Es gibt [mm] $x,y\in\IN$ [/mm] mit $xR_1y$ und $yR_1x$ aber [mm] $x\not=y$.
[/mm]
x=1 und y=2 erfüllen zwar xR_1y und [mm] $x\not=y$, [/mm] aber nicht $yR_1x$.
Also hast du NICHT die Antisymmetrie von [mm] $R_1$ [/mm] widerlegt.
> 3. x = 1 und y = 2 => keine Antisymmetrie(erstes Tupel x
> und zweites Tupel y)
> 4. x = 1 und y = 1 = > x=y ( das x=1 aus dem zweiten Tupel
> und das y = 1 aus dem ersten Tupel)
Die Fälle hattest du ja schon. Du brauchst sie nicht doppelt zu behandeln.
[mm] $R_1$ [/mm] ist antisymmetrisch, denn:
Seien [mm] $x,y\in\IN$ [/mm] mit $xR_1y$ und $yR_1x$.
Zu zeigen ist $x=y$.
Viele würden jetzt durch Hinsehen feststellen, dass nur $x=1$ und $y=1$ sowohl $xR_1y$ als auch $yR_1x$ erfüllen.
Wenn wir es formal einsehen wollen:
Wegen $xR_1y$ liegt einer der Fälle
1. $x=1$ und $y=1$
2. $x=1$ und $y=2$
vor.
Wegen $yR_1x$ scheidet der Fall 2. aus.
Es bleibt noch der Fall 1. übrig.
In diesem Fall folgt wie gewünscht $x=1=y$.
> Für [mm]R_2:[/mm]
> 1. x = 1 und y = 1 = > x=y ( erstes Tupel)
> 2. x = 1 und y = 2 => keine Antisymm. (zweites Tupel)
> 3. x = 2 und y = 1 => keine Antisymm. (drittes Tupel)
> 4. x = 1 und y = 2 => keine Antisymm. (erstes Tupel x=1
> und zweites Tupel y =2)
> 5. x = 1 und y = 1 => x=y (erstes Tupel x=1 und drittes
> Tupel y = 1)
> 6. x = 2 und y = 2 => x=y ( drittes Tupel x =2 und zweites
> Tupel y =2)
Mir ist etwas unklar, warum du so viele Fälle betrachtest.
Warum folgt aus 3./4. dass [mm] $R_2$ [/mm] nicht antisymmetrisch ist?
Entscheidend ist: Es gilt $1R_22$ und $2R_21$, aber [mm] $1\not=2$.
[/mm]
Damit kann [mm] $R_2$ [/mm] nicht antisymmetrisch sein.
> usw..
> Deshalb dritte Frage:
> Wie wir sehen, ist zum Beispiel die Nummer 4 bei [mm]R_2[/mm] nicht
> antisymmetrisch.
Entweder [mm] $R_2$ [/mm] ist antisymmetrisch oder nicht. [mm] $R_2$ [/mm] kann nicht in gewissen Fällen antisymmetrisch und in anderen Fällen nicht antisymmetrisch sein!
> Wann kann man sagen, dass eine Relation
> antisymmetrisch ist? Wenn sie MINDESTENS eine Relation mit
> xRy und yRx hat, sodass x=y gilt ?
Nein.
Eine Relation R auf M ist antisymmetrisch, wenn für ALLE [mm] $x,y\in [/mm] M$ mit $xRy$ und $yRx$ bereits $x=y$ gilt.
R ist NICHT antisymmetrisch, wenn [mm] $x,y\in [/mm] M$ mit $xRy$ und $yRx$ EXISTIEREN, für die [mm] $x\not=y$ [/mm] gilt.
Wenn du also keinen formalen Beweis brauchst und eine überschaubare endliche Relation vorliegen hast, guckst du nach, ob du [mm] $x\not=y$ [/mm] mit $xRy$ und $yRx$ findest.
Falls ja, ist die Relation nicht antisymmetrisch.
Falls nein, ist die Relation antisymmetrisch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:14 So 13.11.2016 | | Autor: | pc_doctor |
Vielen lieben Dank an euch für die Antworten. Jetzt habe ich es verstanden!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:53 So 13.11.2016 | | Autor: | fred97 |
vielleicht hilft Dir das: eine Relation R ist nicht antisymmetrisch, wenn es x,y gibt mit
xR y und yRx, aber x [mm] \ne [/mm] y
fred
|
|
|
|
