Relation Basics < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Auf [mm] \IN\backslash\{0,1\} [/mm] sei die Relation R, die für alle [mm] n,m\in\IN\backslash\{0,1\} [/mm] durch nRm ⇔ ggT(n,m)>1 definiert ist, gegeben.
(a) Welche der Eigenschaften Reflexivität, Symmetrie oder Transitivität erfüllt R? Beweisen Sie Ihre Antwort!
(b) Eine natürliche Zahl [mm] n\in\IN\backslash\{0,1\} [/mm] heißt minimal bezüglich R, wenn keine natürliche Zahl [mm] m\in\IN\backslash\{0,1\} [/mm] existiert, die (echt) kleiner als n ist, und für die mRn gilt. Bestimmen Sie alle bezüglich R minimalen natürlichen Zahlen in [mm] \IN\backslash\{0,1\}! [/mm] Beweisen Sie Ihre Antwort! |
Hallo Leute,
Sei M eine Menge und definiert mit [mm] M=\IN\backslash\{0,1\}. [/mm] Dann folgt daraus, dass eine "binäre" Relation definiert ist als:
[mm] R\subseteq\IN\backslash\{0,1\} [/mm] x [mm] \IN\backslash\{0,1\}\gdw R\subseteq [/mm] MxM
[mm] MxM:=\{(n,m)|(n\in M)\wedge(m\in M)\}
[/mm]
Je nach Relation gibt es n-Tupeln mit der Darstellung (a,b). Also wenn sich jedes Element mit jedem anderen kombinieren lässt, hat man folgende Kombinationsmöglichkeiten.
[mm] \pmat{ (2,2) & (2,3) & \ldots& \ldots & (2,b) \\ (3,2) & (3,3) & \ldots& \ldots & (3,b) \\ (4,2) & (4,3) & \ldots& \ldots & (4,b) \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ (a,2) & (a,3) & \ldots & \ldots & (a,b)}
[/mm]
a) Die Relation [mm] R\subseteq [/mm] MxM ist reflexiv, wenn [mm] \forall x\in [/mm] M:xRx gilt.
Da nRm ⇔ ggT(n,m)>1 definiert ist, müssen wir beweisen, dass die Tupel (1,1),(2,2),....,(n,n)=(m,m), existieren. Okay. Es existiert sowohl ggT(n,n)>1 als auch ggT(m,m)>1 mit n=m, daraus folgt nRn => Reflexiv^^?
Die Relation R ist symmetrisch: Da ggT(n,m)=ggT(m,n) gilt, folgt daraus nRm [mm] \wedge [/mm] mRn. Somit ist R symmetrisch.
Transitiv ist die Relation nie. Aus ggT(8,4) [mm] \wedge [/mm] ggT(4,2) folgt nicht ggT(8,2) also auch nicht nRm [mm] \wedge [/mm] mRo => nRo. Richtig gezeigt?
Alle Teilerfremden Zahlenpaare n,n+1 mit [mm] n\ge2 [/mm] sind nicht Teil der Menge in der Relation.
b) Wenn ich das richtig verstanden habe, dann wäre die minimale natürliche Zahl für n=2, da es kein kleineres m in der Menge [mm] \IN\{0,1\}, [/mm] und das kleinste Tupel (2,4) wäre. Aber wie begründe/beweise ich das formal?
Liebe Grüße, BeeRe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:43 Fr 27.11.2009 | | Autor: | felixf |
Hallo BeeRe!
> Auf [mm]\IN\backslash\{0,1\}[/mm] sei die Relation R, die für alle
> [mm]n,m\in\IN\backslash\{0,1\}[/mm] durch nRm ⇔ ggT(n,m)>1
> definiert ist, gegeben.
>
> (a) Welche der Eigenschaften Reflexivität, Symmetrie oder
> Transitivität erfüllt R? Beweisen Sie Ihre Antwort!
>
> (b) Eine natürliche Zahl [mm]n\in\IN\backslash\{0,1\}[/mm] heißt
> minimal bezüglich R, wenn keine natürliche Zahl
> [mm]m\in\IN\backslash\{0,1\}[/mm] existiert, die (echt) kleiner als
> n ist, und für die mRn gilt. Bestimmen Sie alle bezüglich
> R minimalen natürlichen Zahlen in [mm]\IN\backslash\{0,1\}![/mm]
> Beweisen Sie Ihre Antwort!
>
> Sei M eine Menge und definiert mit [mm]M=\IN\backslash\{0,1\}.[/mm]
> Dann folgt daraus, dass eine "binäre" Relation definiert
> ist als:
>
> [mm]R\subseteq\IN\backslash\{0,1\}[/mm] x [mm]\IN\backslash\{0,1\}\gdw R\subseteq[/mm]
> MxM
>
> [mm]MxM:=\{(n,m)|(n\in M)\wedge(m\in M)\}[/mm]
>
> Je nach Relation gibt es n-Tupeln mit der Darstellung
> (a,b). Also wenn sich jedes Element mit jedem anderen
> kombinieren lässt, hat man folgende
> Kombinationsmöglichkeiten.
>
> [mm]\pmat{ (2,2) & (2,3) & \ldots& \ldots & (2,b) \\ (3,2) & (3,3) & \ldots& \ldots & (3,b) \\ (4,2) & (4,3) & \ldots& \ldots & (4,b) \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ (a,2) & (a,3) & \ldots & \ldots & (a,b)}[/mm]
Was willst du damit sagen?
> a) Die Relation [mm]R\subseteq[/mm] MxM ist reflexiv, wenn [mm]\forall x\in[/mm]
> M:xRx gilt.
> Da nRm ⇔ ggT(n,m)>1 definiert ist, müssen wir beweisen,
> dass die Tupel (1,1),(2,2),....,(n,n)=(m,m), existieren.
Hmm? Du musst einfach zeigen, dass fuer jede natuerliche Zahl $n [mm] \ge [/mm] 2$ gilt $n R n$.
> Okay. Es existiert sowohl ggT(n,n)>1 als auch ggT(m,m)>1
> mit n=m, daraus folgt nRn => Reflexiv^^?
So solltest du das nicht aufschreiben.
Was ist denn ggT(n, n)? Und wieso ist das groesser 1?
> Die Relation R ist symmetrisch: Da ggT(n,m)=ggT(m,n) gilt,
Ja.
> folgt daraus nRm [mm]\wedge[/mm] mRn.
Was willst du damit sagen? Warum sollte fuer irgendein $n, m$ gelten $n R m$ und $m R n$?
Du meinst: $n R m [mm] \Rightarrow [/mm] m R n$.
> Somit ist R symmetrisch.
Ja.
> Transitiv ist die Relation nie. Aus ggT(8,4) [mm]\wedge[/mm]
> ggT(4,2)
Was soll "Zahl [mm] $\wedge$ [/mm] Zahl" bedeuten?!? Der Ausdruck macht keinen Sinn.
> folgt nicht ggT(8,2) also auch nicht nRm [mm]\wedge[/mm]
> mRo => nRo. Richtig gezeigt?
Es gilt $8 R 4$, $4 R 2$ und $8 R 2$. Dieses Beispiel hilft dir also nicht weiter.
Versuch mal etwas z.B. mit 6.
> b) Wenn ich das richtig verstanden habe, dann wäre die
> minimale natürliche Zahl für n=2, da es kein kleineres m
> in der Menge [mm]\IN\{0,1\},[/mm] und das kleinste Tupel (2,4)
> wäre. Aber wie begründe/beweise ich das formal?
Schreib doch mal bitte alle Relationen zwischen den Zahlen 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 auf. Faellt dir irgendetwas auf? Insbesondere fuer welche Zahlen $n$ die Bedingung aus (b) erfuellt ist?
LG Felix
|
|
|
| |
|
> Hallo BeeRe!
>
> > Auf [mm]\IN\backslash\{0,1\}[/mm] sei die Relation R, die für alle
> > [mm]n,m\in\IN\backslash\{0,1\}[/mm] durch nRm ⇔ ggT(n,m)>1
> > definiert ist, gegeben.
> >
> > (a) Welche der Eigenschaften Reflexivität, Symmetrie oder
> > Transitivität erfüllt R? Beweisen Sie Ihre Antwort!
> >
> > (b) Eine natürliche Zahl [mm]n\in\IN\backslash\{0,1\}[/mm] heißt
> > minimal bezüglich R, wenn keine natürliche Zahl
> > [mm]m\in\IN\backslash\{0,1\}[/mm] existiert, die (echt) kleiner als
> > n ist, und für die mRn gilt. Bestimmen Sie alle bezüglich
> > R minimalen natürlichen Zahlen in [mm]\IN\backslash\{0,1\}![/mm]
> > Beweisen Sie Ihre Antwort!
> >
> > Sei M eine Menge und definiert mit [mm]M=\IN\backslash\{0,1\}.[/mm]
> > Dann folgt daraus, dass eine "binäre" Relation definiert
> > ist als:
> >
> > [mm]R\subseteq\IN\backslash\{0,1\}[/mm] x [mm]\IN\backslash\{0,1\}\gdw R\subseteq[/mm]
> > MxM
> >
> > [mm]MxM:=\{(n,m)|(n\in M)\wedge(m\in M)\}[/mm]
> >
> > Je nach Relation gibt es n-Tupeln mit der Darstellung
> > (a,b). Also wenn sich jedes Element mit jedem anderen
> > kombinieren lässt, hat man folgende
> > Kombinationsmöglichkeiten.
> >
> > [mm]\pmat{ (2,2) & (2,3) & \ldots& \ldots & (2,b) \\ (3,2) & (3,3) & \ldots& \ldots & (3,b) \\ (4,2) & (4,3) & \ldots& \ldots & (4,b) \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ (a,2) & (a,3) & \ldots & \ldots & (a,b)}[/mm]
>
> Was willst du damit sagen?
Das man sich so unsere Menge [mm] R\subseteq\IN\backslash\{0,1\}x\IN\backslash\{0,1\} [/mm] als 2er-Tupeln vorstellen kann. So hab ich mir versucht logisch ne Menge zuerklären. Ich hab das mit dieser Definition in Wikipedia nachgelesen.
> > a) Die Relation [mm]R\subseteq[/mm] MxM ist reflexiv, wenn [mm]\forall x\in[/mm]
> > M:xRx gilt.
> > Da nRm ⇔ ggT(n,m)>1 definiert ist, müssen wir
> beweisen,
> > dass die Tupel (1,1),(2,2),....,(n,n)=(m,m), existieren.
>
> Hmm? Du musst einfach zeigen, dass fuer jede natuerliche
> Zahl [mm]n \ge 2[/mm] gilt [mm]n R n[/mm].
Einfach nur zeigen, dass ggT(n,n)>1? Hm, okay. Beweis durch Wiederspruch, also angenommen ggT(n,n)=1 dann folgt [mm] \bruch{n}{1}=x [/mm] und [mm] \bruch{n}{1}=y [/mm] <=> 2n=x+y <=> 2n=2n <=> n=n.
Aber das ist doch richtig n=n. Was mach ich hier falsch?
>
> > Okay. Es existiert sowohl ggT(n,n)>1 als auch ggT(m,m)>1
> > mit n=m, daraus folgt nRn => Reflexiv^^?
>
> So solltest du das nicht aufschreiben.
>
> Was ist denn ggT(n, n)? Und wieso ist das groesser 1?
>
> > Die Relation R ist symmetrisch: Da ggT(n,m)=ggT(m,n) gilt,
>
> Ja.
>
> > folgt daraus nRm [mm]\wedge[/mm] mRn.
>
> Was willst du damit sagen? Warum sollte fuer irgendein [mm]n, m[/mm]
> gelten [mm]n R m[/mm] und [mm]m R n[/mm]?
>
> Du meinst: [mm]n R m \Rightarrow m R n[/mm].
Wieso "folgt"? Es gilt doch ggT(n,m)=ggT(m,n), also nRm=mRn (Ich dachte, ich könnte das Äquivalenzzeichen, durch ein logisches Und ersetzen.)
> > Somit ist R symmetrisch.
>
> Ja.
>
> > Transitiv ist die Relation nie. Aus ggT(8,4) [mm]\wedge[/mm]
> > ggT(4,2)
>
> Was soll "Zahl [mm]\wedge[/mm] Zahl" bedeuten?!? Der Ausdruck macht
> keinen Sinn.
>
> > folgt nicht ggT(8,2) also auch nicht nRm [mm]\wedge[/mm]
> > mRo => nRo. Richtig gezeigt?
>
> Es gilt [mm]8 R 4[/mm], [mm]4 R 2[/mm] und [mm]8 R 2[/mm]. Dieses Beispiel hilft dir
> also nicht weiter.
Wieso gilt 8R4, 4R2 und 8R2 ? Das sind doch auch Zahlen, die Relation "verarbeitet" doch (8,4),(4,2),(8,2). Da kommen doch jeweils Ergebnisse raus? Oder denkt man sich das einfach so. Wenn 8R4 "verarbeitet" werden kann und 4R2 ebenso, dann folgt daraus dass auch 8R2 "verarbeitet werden kann? Ich verstehe diese Schreibweisen noch nicht 100%, denke ich.
> Versuch mal etwas z.B. mit 6.
6R4 und 4R2 => 6R2 Reicht ein Bsp so zuzeigen als Beweis, damit ich nun davon ausgehen kann, dass nRm und mRo => nRo und somit ggT(n,m)>1 transitiv ist.^^?
> > b) Wenn ich das richtig verstanden habe, dann wäre die
> > minimale natürliche Zahl für n=2, da es kein kleineres m
> > in der Menge [mm]\IN\{0,1\},[/mm] und das kleinste Tupel (2,4)
> > wäre. Aber wie begründe/beweise ich das formal?
>
> Schreib doch mal bitte alle Relationen zwischen den Zahlen
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 auf. Faellt dir irgendetwas
> auf? Insbesondere fuer welche Zahlen [mm]n[/mm] die Bedingung aus
> (b) erfuellt ist?
Mir ist aufgefallen, dass es viel weniger Relationen für 1,...10 gibt, als ich zuvor angenommen habe, was mir dann auch plausibel wurde. ggT(n,m)>1 müssen mindestens einen gemeinsamen Primteiler besitzen. Speziell für die Bedingung dass m>n gilt und mRn gelten soll, is mir aufgefallen, dass als Ergebnis von mRn jede natürliche Zahl aus IN außer 0,1 auftritt.
Bin aber auch gerade am Zweifeln ob ich das Kriterium wirklich verstanden habe...je öfter ich es durchlese, desto mehr confused es mich.
Lg BeeRe
> LG Felix
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 29.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
