Äquivalenzrelation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:02 So 21.11.2010 | | Autor: | el_grecco |
| Aufgabe | Welche der Eigenschaften reflexiv, symmetrisch, antisymmetrisch, transitiv sind für die folgende Relation [mm] $\sim$ [/mm] auf [mm] $\IN$ [/mm] erfüllt (Beweis oder Gegenbeispiel)?
Für n und m in den natürlichen Zahlen ist $n [mm] \sim [/mm] m [mm] :\gdw [/mm] n = [mm] m^{2}$. [/mm] |
Hallo,
ich möchte mich kurz vergewissern, ob ich auf dem richtigen Dampfer bin.
In einem Lehrbuch heißt es:
"Sind A und B Mengen, so heißt jede Teilmenge von $A [mm] \times [/mm] B$ eine Relation zwischen A und B. Gilt A = B, so spricht man von einer Relation auf A."
Auf die Aufgabe übertragen bedeutet das doch:
Ich habe zwei Mengen A und B, die jeweils alle natürlichen Zahlen ohne die 0 beinhalten. Entsprechend:
$A [mm] \times B=\{(1,1),(1,2),(1,3),(1,4),...$
$(2,1),(2,2),(2,3),(2,4),...$
$...\}$
[/mm]
Daraus ergeben sich folgende Relationen:
[mm] $R_{1}=\emptyset$
[/mm]
[mm] $R_{2}=\{(1,1)\}$
[/mm]
[mm] $R_{3}=\{(1,4)\}$
[/mm]
[mm] $R_{4}=\{(1,9)\}$
[/mm]
$...$
Vielen Dank soweit.
Gruß
el_grecco
|
|
| |
|
Erneuter Versuch:
$A [mm] \times B=\{(1,1),(1,2),(1,3),(1,4),...$
$(2,1),(2,2),(2,3),(2,4),...\}$
[/mm]
Dann ergeben sich die Relationen:
[mm] $R_{1}=\{\}$
[/mm]
[mm] $R_{2}=\{(1,1)\}$
[/mm]
[mm] $R_{3}=\{(4,2)\}$
[/mm]
[mm] $R_{4}=\{(9,3)\}$
[/mm]
[mm] $R_{5}=\{(16,4)\}$
[/mm]
...
Mein Problem ist jetzt, dass ich keinen Ansatz finde, wie ich z.B. die Reflexivität beweise?
Reicht es, wenn ich sage, dass keine Reflexivität besteht, da z.B.
[mm] $(2,2)\not\in \mathcal [/mm] R$
[mm] $(3,3)\not\in \mathcal [/mm] R$
[mm] $(4,4)\not\in \mathcal [/mm] R$
Vielen Dank.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:56 So 21.11.2010 | | Autor: | Marc |
Hallo el_grecco,
> Erneuter Versuch:
>
> [mm]A \times B=\{(1,1),(1,2),(1,3),(1,4),...[/mm]
>
> [mm](2,1),(2,2),(2,3),(2,4),...\}[/mm]
>
> Dann ergeben sich die Relationen:
> [mm]R_{1}=\{\}[/mm]
> [mm]R_{2}=\{(1,1)\}[/mm]
> [mm]R_{3}=\{(4,2)\}[/mm]
> [mm]R_{4}=\{(9,3)\}[/mm]
> [mm]R_{5}=\{(16,4)\}[/mm]
> ...
Nein, es geht hier um eine konkrete Relation, nämlich diese
[mm] $R=\{(n,m)\in\IN\times\IN\ |\ n=m^2\}=\{(1,1),(4,2),(9,3),(16,4),\ldots\}$
[/mm]
> Mein Problem ist jetzt, dass ich keinen Ansatz finde, wie
> ich z.B. die Reflexivität beweise?
>
> Reicht es, wenn ich sage, dass keine Reflexivität besteht,
> da z.B.
> [mm](2,2)\not\in \mathcal R[/mm]
> [mm](3,3)\not\in \mathcal R[/mm]
>
> [mm](4,4)\not\in \mathcal R[/mm]
Genau, allerdings reicht natürlich die Aussage [mm] $(2,2)\not\in [/mm] R$, um die Reflexivität zu widerlegen.
Viele Grüße,
Marc
|
|
|
| |
|
Vielen Dank, Marc.
Abschließend noch zwei Punkte:
1.) Warum ist es nicht nötig, die leere Menge in deiner Notation zu erwähnen?
2.) Bitte um Korrektur meines Lösungsweges für die restlichen Eigenschaften:
- Keine Symmetrie, da z.B. aus $(4,2) [mm] \in \mathcal [/mm] R$ nicht folgt $(2,4) [mm] \in \mathcal [/mm] R$
- Keine Antisymmetrie, da z.B. $(9,3) [mm] \in \mathcal [/mm] R$ gilt, aber nicht gleichzeitig $(3,9) [mm] \in \mathcal [/mm] R$ gilt.
- Keine Transitivität, da z.B. $(4,2) [mm] \in \mathcal [/mm] R$ und gleichzeitig muss $(2,z) [mm] \in \mathcal [/mm] R$ gelten sodass $(4,z) [mm] \in \mathcal [/mm] R$.
Es gibt aber kein $(2,z) [mm] \in \mathcal [/mm] R$.
Vielen Dank.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:40 So 21.11.2010 | | Autor: | Marc |
Hallo el_grecco,
> Abschließend noch zwei Punkte:
>
> 1.) Warum ist es nicht nötig, die leere Menge in deiner
> Notation zu erwähnen?
Weil eine Menge da nichts zu suchen hat. Die Relation besteht aus Paaren von [mm] $A\times [/mm] B$ bzw. hier [mm] $\IN\times\IN$.
[/mm]
Ich glaube du verwechselst das mit der gesamten Relation.
Eine Relation ist eine Menge von Paaren, d.h. es sind folgende Mengen tatsächlich Relationen:
[mm] $R_1=\{\}$
[/mm]
[mm] $R_2=\{(1,1)\}$
[/mm]
[mm] $R_3=\{(4,2)\}$
[/mm]
[mm] $R_4=\{(1,1),(4,2)\}$
[/mm]
Dies sind aber alles Relationen, die nichts mit der Aufgabe zu tun haben. In der Aufgabe geht es um die eine Relation
[mm] $R=\{(1,1),(4,2),(9,3),\ldots\}$
[/mm]
> 2.) Bitte um Korrektur meines Lösungsweges für die
> restlichen Eigenschaften:
>
> - Keine Symmetrie, da z.B. aus [mm](4,2) \in \mathcal R[/mm] nicht
> folgt [mm](2,4) \in \mathcal R[/mm]
Es stimmt zwar, aber hier möchte man doch sehen, warum es nicht stimmt. Eine Behauptung alleine reicht nicht.
> - Keine Antisymmetrie, da z.B.
> [mm](9,3) \in \mathcal R[/mm] gilt, aber nicht gleichzeitig [mm](3,9) \in \mathcal R[/mm]
> gilt.
Nein, das ist Käse.
Für Antisymmetrie muss das gelten:
WENN [mm] $(x,y)\in [/mm] R$ und [mm] $(y,x)\in [/mm] R$, dann $x=y$
Um die Antisymmetrie zu widerlegen, musst du wenigstens die Voraussetzung (den WENN-Teil) erfüllen.
> - Keine Transitivität, da z.B. [mm](4,2) \in \mathcal R[/mm] und
> gleichzeitig muss [mm](2,z) \in \mathcal R[/mm] gelten sodass [mm](4,z) \in \mathcal R[/mm].
>
> Es gibt aber kein [mm](2,z) \in \mathcal R[/mm].
Hier genauso.
Transitätivt bedeutet:
WENN [mm] $(x,y)\in [/mm] R$ und [mm] $(y,z)\in [/mm] R$, dann [mm] $(x,z)\in [/mm] R$.
Wenn du die Voraussetzung nicht erfüllen kannst (weil du keine passenden Paare findest (was hier aber nicht der Fall ist, es gibt passende Paare)), dann wäre die Relation transitiv.
Viele Grüße,
Marc
|
|
|
| |
|
Vielen Dank, Marc.
> > - Keine Symmetrie, da z.B. aus [mm](4,2) \in \mathcal R[/mm] nicht
> > folgt [mm](2,4) \in \mathcal R[/mm]
>
> Es stimmt zwar, aber hier möchte man doch sehen, warum es
> nicht stimmt. Eine Behauptung alleine reicht nicht.
>
Ich dachte, um eine Behauptung zu widerlegen, würde ein Gegenbeispiel genügen und nur bei Richtigkeit muss ein allgemeiner Beweis her...?
Ist es dann besser, wenn ich ausgehend von der Definition für Symmetrie $(x,y) [mm] \in \mathcal [/mm] R [mm] \Rightarrow [/mm] (y,x) [mm] \in \mathcal [/mm] R$ für alle $x,y [mm] \in [/mm] A$ das so schreibe?
$(4,2) [mm] \in \mathcal [/mm] R [mm] \Rightarrow [/mm] (2,4) [mm] \not\in \mathcal [/mm] R$
> > - Keine Antisymmetrie, da z.B.
> > [mm](9,3) \in \mathcal R[/mm] gilt, aber nicht gleichzeitig [mm](3,9) \in \mathcal R[/mm]
> > gilt.
>
> Nein, das ist Käse.
> Für Antisymmetrie muss das gelten:
> WENN [mm](x,y)\in R[/mm] und [mm](y,x)\in R[/mm], dann [mm]x=y[/mm]
> Um die Antisymmetrie zu widerlegen, musst du wenigstens
> die Voraussetzung (den WENN-Teil) erfüllen.
>
Hier würde ich dann wieder ein Beispiel in die Definition einsetzen und so zeigen, dass die Eigenschaft nicht erfüllt ist:
$(9,3) [mm] \in [/mm] R [mm] \wedge [/mm] (3,9) [mm] \not\in [/mm] R [mm] \Rightarrow [/mm] 9 [mm] \not= [/mm] 3$
>
> > - Keine Transitivität, da z.B. [mm](4,2) \in \mathcal R[/mm] und
> > gleichzeitig muss [mm](2,z) \in \mathcal R[/mm] gelten sodass [mm](4,z) \in \mathcal R[/mm].
>
> >
> > Es gibt aber kein [mm](2,z) \in \mathcal R[/mm].
>
> Hier genauso.
> Transitätivt bedeutet:
> WENN [mm](x,y)\in R[/mm] und [mm](y,z)\in R[/mm], dann [mm](x,z)\in R[/mm].
>
> Wenn du die Voraussetzung nicht erfüllen kannst (weil du
> keine passenden Paare findest (was hier aber nicht der Fall
> ist, es gibt passende Paare)), dann wäre die Relation
> transitiv.
>
Kannst du mir bitte ein Beispiel nennen bzw. kann es sein, dass es nur ein Paar gibt (1,1)?
> Viele Grüße,
> Marc
Gruß
el_Grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:07 So 21.11.2010 | | Autor: | Marc |
Hallo,
> Vielen Dank, Marc.
>
> > > - Keine Symmetrie, da z.B. aus [mm](4,2) \in \mathcal R[/mm] nicht
> > > folgt [mm](2,4) \in \mathcal R[/mm]
> >
> > Es stimmt zwar, aber hier möchte man doch sehen, warum es
> > nicht stimmt. Eine Behauptung alleine reicht nicht.
> >
>
> Ich dachte, um eine Behauptung zu widerlegen, würde ein
> Gegenbeispiel genügen und nur bei Richtigkeit muss ein
> allgemeiner Beweis her...?
![[ok]](/images/smileys/ok.gif "[ok]")
> Ist es dann besser, wenn ich ausgehend von der Definition
> für Symmetrie [mm](x,y) \in \mathcal R \Rightarrow (y,x) \in \mathcal R[/mm]
> für alle [mm]x,y \in A[/mm] das so schreibe?
Nein, das ist doch das gleiche.
Ich meinte es so:
[mm] $(4,2)\in [/mm] R$, da [mm] $4=2^2$
[/mm]
[mm] $(2,4)\not\in [/mm] R$, da [mm] $2\not=4^2$
[/mm]
> [mm](4,2) \in \mathcal R \Rightarrow (2,4) \not\in \mathcal R[/mm]
>
> > > - Keine Antisymmetrie, da z.B.
> > > [mm](9,3) \in \mathcal R[/mm] gilt, aber nicht gleichzeitig [mm](3,9) \in \mathcal R[/mm]
> > > gilt.
> >
> > Nein, das ist Käse.
> > Für Antisymmetrie muss das gelten:
> > WENN [mm](x,y)\in R[/mm] und [mm](y,x)\in R[/mm], dann [mm]x=y[/mm]
> > Um die Antisymmetrie zu widerlegen, musst du wenigstens
> > die Voraussetzung (den WENN-Teil) erfüllen.
> >
>
> Hier würde ich dann wieder ein Beispiel in die Definition
> einsetzen und so zeigen, dass die Eigenschaft nicht
> erfüllt ist:
>
> [mm](9,3) \in R \wedge \red{(3,9) \not\in R} \Rightarrow 9 \not= 3[/mm]
Das ist doch kein Gegenbeispiel, weil die Voraussetzung für die Behauptung immer noch nicht erfüllt ist!
Meine Behauptung: "Wenn heute Montag ist, dann ist morgen Mittwoch" kannst du doch auch nicht so widerlegen: "Heute ist Donnerstag, und morgen ist Freitag".
Wenn du ein Gegenbeispiel suchst, musst du zwei Paare finden, für die [mm] $(x,y)\in [/mm] R$ UND [mm] $(y,x)\in [/mm] R$ GILT, aber [mm] $x\not= [/mm] y$.
> > > - Keine Transitivität, da z.B. [mm](4,2) \in \mathcal R[/mm] und
> > > gleichzeitig muss [mm](2,z) \in \mathcal R[/mm] gelten sodass [mm](4,z) \in \mathcal R[/mm].
>
> >
> > >
> > > Es gibt aber kein [mm](2,z) \in \mathcal R[/mm].
> >
> > Hier genauso.
> > Transitätivt bedeutet:
> > WENN [mm](x,y)\in R[/mm] und [mm](y,z)\in R[/mm], dann [mm](x,z)\in R[/mm].
> >
> > Wenn du die Voraussetzung nicht erfüllen kannst (weil du
> > keine passenden Paare findest (was hier aber nicht der Fall
> > ist, es gibt passende Paare)), dann wäre die Relation
> > transitiv.
> >
>
> Kannst du mir bitte ein Beispiel nennen bzw. kann es sein,
> dass es nur ein Paar gibt (1,1)?
Wie meinst du das, dass "es nur ein Paar gibt"? Ein Paar, das die Voraussetzung für die Behauptung erfüllt oder das die ganze Aussage zu einer wahren Aussage macht?
Es gibt mehrere Möglichkeiten, damit die Voraussetzung [mm] $(x,y)\in [/mm] R$, [mm] $(y,z)\in [/mm] R$ erfüllt ist, aber nur eines (nämlich (1,1)), für das die gesamte Behauptung erfüllt ist (und was damit uninteressant für ein Gegenbeispiel ist).
Viele Grüße,
Marc
|
|
|
| |
|
1000 Dank für deinen starken Support, Marc.
>
> Das ist doch kein Gegenbeispiel, weil die Voraussetzung
> für die Behauptung immer noch nicht erfüllt ist!
> Meine Behauptung: "Wenn heute Montag ist, dann ist morgen
> Mittwoch" kannst du doch auch nicht so widerlegen: "Heute
> ist Donnerstag, und morgen ist Freitag".
> Wenn du ein Gegenbeispiel suchst, musst du zwei Paare
> finden, für die [mm](x,y)\in R[/mm] UND [mm](y,x)\in R[/mm] GILT, aber
> [mm]x\not= y[/mm].
>
Erlaubt die Definition ein Paar wie (4,2) UND (9,3) oder geht da nur so etwas wie (4,2) UND (2,4) (quasi wenn x und y einmal festgelegt sind, müssen sie weiterverwendet werden)?
> > > > - Keine Transitivität, da z.B. [mm](4,2) \in \mathcal R[/mm] und
> > > > gleichzeitig muss [mm](2,z) \in \mathcal R[/mm] gelten sodass [mm](4,z) \in \mathcal R[/mm].
>
> >
> > >
> > > >
> > > > Es gibt aber kein [mm](2,z) \in \mathcal R[/mm].
> > >
> > > Hier genauso.
> > > Transitätivt bedeutet:
> > > WENN [mm](x,y)\in R[/mm] und [mm](y,z)\in R[/mm], dann [mm](x,z)\in R[/mm].
> >
> >
> > > Wenn du die Voraussetzung nicht erfüllen kannst (weil du
> > > keine passenden Paare findest (was hier aber nicht der Fall
> > > ist, es gibt passende Paare)), dann wäre die Relation
> > > transitiv.
> > >
> >
> > Kannst du mir bitte ein Beispiel nennen bzw. kann es sein,
> > dass es nur ein Paar gibt (1,1)?
>
> Wie meinst du das, dass "es nur ein Paar gibt"? Ein Paar,
> das die Voraussetzung für die Behauptung erfüllt oder das
> die ganze Aussage zu einer wahren Aussage macht?
>
> Es gibt mehrere Möglichkeiten, damit die Voraussetzung
> [mm](x,y)\in R[/mm], [mm](y,z)\in R[/mm] erfüllt ist, aber nur eines
> (nämlich (1,1)), für das die gesamte Behauptung erfüllt
> ist (und was damit uninteressant für ein Gegenbeispiel
> ist).
>
Ich habe das so gemeint, dass es eben nur dieses eine Paar (1,1) gibt, sodass die Definition für Transitivität erfüllt ist.
Wenn es nur ein Paar gibt, dann liegt doch hier keine Transitivität vor, denn es müssten alle Paare die Definition erfüllen...?
> Viele Grüße,
> Marc
Nochmals vielen Dank, Marc.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:49 So 21.11.2010 | | Autor: | Marc |
Hallo el_grecco,
> > Mittwoch" kannst du doch auch nicht so widerlegen: "Heute
> > ist Donnerstag, und morgen ist Freitag".
> > Wenn du ein Gegenbeispiel suchst, musst du zwei Paare
> > finden, für die [mm](x,y)\in R[/mm] UND [mm](y,x)\in R[/mm] GILT, aber
> > [mm]x\not= y[/mm].
> >
>
> Erlaubt die Definition ein Paar wie (4,2) UND (9,3) oder
> geht da nur so etwas wie (4,2) UND (2,4) (quasi wenn x und
> y einmal festgelegt sind, müssen sie weiterverwendet
> werden)?
Wenn in der Mathematik im selben Kontext dieselben Variablen auftreten, dann sind sie immer mit denselben Werten belegt.
> > > > > - Keine Transitivität, da z.B. [mm](4,2) \in \mathcal R[/mm] und
> > > > > gleichzeitig muss [mm](2,z) \in \mathcal R[/mm] gelten sodass [mm](4,z) \in \mathcal R[/mm].
>
> >
> > >
> > > >
> > > > >
> > > > > Es gibt aber kein [mm](2,z) \in \mathcal R[/mm].
> > > >
> > > > Hier genauso.
> > > > Transitätivt bedeutet:
> > > > WENN [mm](x,y)\in R[/mm] und [mm](y,z)\in R[/mm], dann [mm](x,z)\in R[/mm].
>
> > >
> > >
> > > > Wenn du die Voraussetzung nicht erfüllen kannst (weil du
> > > > keine passenden Paare findest (was hier aber nicht der Fall
> > > > ist, es gibt passende Paare)), dann wäre die Relation
> > > > transitiv.
> > > >
> > >
> > > Kannst du mir bitte ein Beispiel nennen bzw. kann es sein,
> > > dass es nur ein Paar gibt (1,1)?
> >
> > Wie meinst du das, dass "es nur ein Paar gibt"? Ein Paar,
> > das die Voraussetzung für die Behauptung erfüllt oder das
> > die ganze Aussage zu einer wahren Aussage macht?
> >
> > Es gibt mehrere Möglichkeiten, damit die Voraussetzung
> > [mm](x,y)\in R[/mm], [mm](y,z)\in R[/mm] erfüllt ist, aber nur eines
> > (nämlich (1,1)), für das die gesamte Behauptung erfüllt
> > ist (und was damit uninteressant für ein Gegenbeispiel
> > ist).
> >
>
> Ich habe das so gemeint, dass es eben nur dieses eine Paar
> (1,1) gibt, sodass die Definition für Transitivität
> erfüllt ist.
> Wenn es nur ein Paar gibt, dann liegt doch hier keine
> Transitivität vor, denn es müssten alle Paare die
> Definition erfüllen...?
Nein, ich fürchte, da ist dir etwas grundsätzliches bei logischen Aussagen nicht klar.
Die Aussage "Wenn heute Montag ist, dann ist morgen Dienstag" ist doch ein wahre Aussage, obwohl es nur einen Wochentag gibt, bei dem die Voraussetzung ("wenn heute Montag ist") erfüllt ist. Die Aussage bleibt auch korrekt, wenn heute Mittwoch ist (denn die Aussage folgert nichts, was falsch sein könnte, falls heute Mittwoch ist).
Ich löse nun die Antisymmetrie und Transitivität auf.
Die Relation ist antisymmetrisch, denn:
Es seien [mm] $(x,y)\in [/mm] R$ und [mm] $(y,x)\in [/mm] R$
[mm] $\Rightarrow\ x=y^2$ [/mm] und [mm] $y=x^2$
[/mm]
Einsetzen der zweiten Gleichung in die erste:
[mm] $\Rightarrow\ x=x^4$
[/mm]
[mm] $\Rightarrow\ [/mm] x=1$ (da [mm] $x\in\IN$) [/mm] und damit auch $y=1$
[mm] $\Rightarrow\ [/mm] x=y$
Die Aussage "WENN [mm] $(x,y)\in [/mm] R$ und [mm] $(y,x)\in [/mm] R$, DANN x=y$" ist also immer wahr.
Die Relation ist nicht transitiv, denn:
[mm] $(16,4)\in [/mm] R$ und [mm] $(4,2)\in [/mm] R$, aber [mm] $(16,2)\not\in [/mm] R$
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:53 So 21.11.2010 | | Autor: | el_grecco |
Vielen Dank, Marc.
Vermutlich war das heute zuviel Input für mich und ich werde mir morgen diese Aufgabe in alter Frische nochmals vergegenwärtigen.
Nochmals vielen Dank für deine Geduld und Hilfe.
Gruß
el_grecco
|
|
|
|
