Nachweis partielle Ordnung < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:49 Di 21.11.2006 | | Autor: | Phoney |
| Aufgabe | [mm] \le [/mm] = geschwungenes Zeichen
Zeigen Sie, dass durch a [mm] \le [/mm] b : [mm] \gdw [/mm] a|b eine partielle Ordnung auf [mm] \IN [/mm] definiert ist. Untersichen sie auch, ob es sich um eine partielle Ordnung auf [mm] \IZ [/mm] anstatt [mm] \IN [/mm] handelt. |
Guten Abend.
Ich muss hierbei ja einfach nur nachweisen, dass eine Relation R auf X partielle Ordnung heißt, wenn sie reflexiv, antisymmetrisch und transitiv ist.
Für reflexiv gilt ja beispielsweise: $x R x$ $ [mm] \forall [/mm] x [mm] \in [/mm] X$
Die Relation dürfte ja sein, a|b.
Theoretisch muss ich das ja einsetzen, nur was habe ich dann?
reflexiv: $x a|b x$ [mm] $\forall [/mm] x [mm] \in [/mm] X$
Ähm, nicht wirklich richtig, oder?
Was muss ich dann machen?
reflexiv $a|b R a|b$ [mm] $\forall [/mm] a|b [mm] \in [/mm] X$
???
Gruß
Johann
|
|
| |
|
Hallo Phoney!
> [mm]\le[/mm] = geschwungenes Zeichen
Äh - du meinst nicht zufällig dieses hier: ~? Das findest du auf deiner Tastatur. Wenn du etwas anderes meinst, beschreib mal bitte, wie das aussehen soll und vor allem, was es bedeuten soll!
> Zeigen Sie, dass durch a [mm]\le[/mm] b : [mm]\gdw[/mm] a|b eine partielle
> Ordnung auf [mm]\IN[/mm] definiert ist. Untersichen sie auch, ob es
> sich um eine partielle Ordnung auf [mm]\IZ[/mm] anstatt [mm]\IN[/mm]
> handelt.
> Guten Abend.
>
> Ich muss hierbei ja einfach nur nachweisen, dass eine
> Relation R auf X partielle Ordnung heißt, wenn sie
> reflexiv, antisymmetrisch und transitiv ist.
Naja, schlecht formuliert. Du kannst nicht eine Definition beweisen...
> Für reflexiv gilt ja beispielsweise: [mm]x R x[/mm] [mm]\forall x \in X[/mm]
>
> Die Relation dürfte ja sein, a|b.
Hä? ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]") Was meinst du hier?
> Theoretisch muss ich das ja einsetzen, nur was habe ich
> dann?
>
> reflexiv: [mm]x a|b x[/mm] [mm]\forall x \in X[/mm]
>
> Ähm, nicht wirklich richtig, oder?
Da steht ja gar nichts. Du musst zeigen, dass die Relation reflexiv ist. Soweit ich deine Relation verstehe, sind zwei Elemente a und b in Relation zueinander gdw a durch b teilbar ist. Nun bedeutet reflexiv, dass a durch a teilbar ist, was ja offensichtlich der Fall ist.
> Was muss ich dann machen?
>
> reflexiv [mm]a|b R a|b[/mm] [mm]\forall a|b \in X[/mm]
Das heißt, wenn a durch b teilbar ist, ist auch b durch a teilbar. Und? Stimmt das? Allerdings ist das die Eigenschaft der Symmetrie, nicht der Antisymmetrie. Und diese Definition guckst du mal bitte nach, ich verwechsel das immer mit der Asymmetrie...
Und transitiv bedeutet dann, wenn a durch b teilbar ist und b durch c, so ist auch a durch c teilbar. Das müsste man aber evtl. noch mit "Formeln" hinschreiben.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:52 Mi 22.11.2006 | | Autor: | Phoney |
Hallo Bastiane!
Das Zeichen? Das sieht wohl so aus, allerdings muss da noch dieses Gleichheitszeichen drunter: $a [mm] \prec [/mm] b : [mm] \gdw [/mm] a|b$
>> reflexiv a|b R a|b $ [mm] \forall [/mm] a|b [mm] \in [/mm] X $
>Das heißt, wenn a durch b teilbar ist, ist auch b durch a teilbar.
Ich verstehe das leider immernoch nicht. Ist das, was ich da geschrieben habe, die richtige Schreibweise?
Müsste X dann nicht [mm] \IN [/mm] sein?
Wie schriebe ich dann die anderen Eigenschaften? (Also das mit Asymmetrie stimmt schon)
reflexiv: $a|a$ [mm] $\forall [/mm] a [mm] \in \IN$
[/mm]
asymm: $ (a|b) [mm] \wedge [/mm] ( b|a) [mm] \Rightarrow [/mm] a=b$
transitiv: [mm] $(a|b)\wedge(b|c) \Rightarrow [/mm] a|c$
Schreibt man das so, oder ist es immernoch falsch?
Die Eigenschaften treffen jedenfalls alle zu.
Nur was ist die partielle Ordnung dann auch auf [mm] \IZ [/mm] definiert? Ich sehe hier keinen Widerspruch!
Viele liebe Grüße
Johann
|
|
|
| |
|
Hallo Phoney!
> Das Zeichen? Das sieht wohl so aus, allerdings muss da noch
> dieses Gleichheitszeichen drunter: [mm]a \prec b : \gdw a|b[/mm]
Mmh, das ist ja ein seltsames Zeichen, das kenne ich gar nicht. Aber es soll bedeuten, dass die beiden in Relation stehen genau dann, wenn a durch b teilbar ist, oder?
> >> reflexiv a|b R a|b [mm]\forall a|b \in X[/mm]
>
> >Das heißt, wenn a durch b teilbar ist, ist auch b durch a
> teilbar.
>
> Ich verstehe das leider immernoch nicht. Ist das, was ich
> da geschrieben habe, die richtige Schreibweise?
Das, was du hier geschrieben hast? Mit reflexiv? Ich kann das gerade nicht ganz zuordnen, ob das nicht schon in deinem ersten Post da stand... Aber so wie da oben ist das nicht richtig. Es soll doch allgemein a in Relation zu b stehen. Und für die Reflexivität soll a in Relation zu sich selber stehen, also a in Relation zu a. Da hat dann das b gar nichts mehr zu suchen. Das heißt, du musst zeigen: a R a (wenn du es so schreiben möchtest). Bei einer Äquivalenzrelation würde man wohl so schreiben: a~a. Das bedeutet aber nichts anderes, als a|a, denn so ist doch genau die Relation definiert. Und das bedeutet doch, dass a durch a teilbar ist. 
> Müsste X dann nicht [mm]\IN[/mm] sein?
Äh - wo ist da der Zusammenhang zu vorigem? Und hat jemand gesagt, dass X nicht [mm] =\IN [/mm] ist?
> Wie schriebe ich dann die anderen Eigenschaften? (Also das
> mit Asymmetrie stimmt schon)
>
> reflexiv: [mm]a|a[/mm] [mm]\forall a \in \IN[/mm]
> asymm: [mm](a|b) \wedge ( b|a) \Rightarrow a=b[/mm]
>
> transitiv: [mm](a|b)\wedge(b|c) \Rightarrow a|c[/mm]
>
> Schreibt man das so, oder ist es immernoch falsch?
Nein, falsch ist das nicht, aber du hast damit noch nichts gezeigt.
> Die Eigenschaften treffen jedenfalls alle zu.
>
> Nur was ist die partielle Ordnung dann auch auf [mm]\IZ[/mm]
> definiert? Ich sehe hier keinen Widerspruch!
Naja, es muss ja nicht unbedingt ein Widerspruch sein. Aber so wie die Frage gestellt ist, kann man das vermuten. Ich schätze, dass die Asymmetrie nicht erfüllt ist. Betrachte z. B. zwei Elemente a=5 und b=-5. Dann gilt doch a|b und b|a, aber es gilt nicht a=b.
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:36 Mi 22.11.2006 | | Autor: | Phoney |
Guten Abend.
Vielen Dank für deine guten Antworten, Bastiane. Aber eins will mir noch nicht ganz in den Kopf
> bedeutet aber nichts anderes, als a|a, denn so ist doch
> genau die Relation definiert. Und das bedeutet doch, dass a
> durch a teilbar ist.
> > reflexiv: [mm]a|a[/mm] [mm]\forall a \in \IN[/mm]
> > asymm: [mm](a|b) \wedge ( b|a) \Rightarrow a=b[/mm]
>
> >
> > transitiv: [mm](a|b)\wedge(b|c) \Rightarrow a|c[/mm]
> >
> > Schreibt man das so, oder ist es immernoch falsch?
>
> Nein, falsch ist das nicht, aber du hast damit noch nichts
> gezeigt.
Wie soll man das denn dann anders zeigen? Soll ich Zahlen einsetzen und gucken, ob es stimmt oder wie? Z. B. beim Transitiven.
Wenn a ein Teiler von b ist und eine ganze Zahl heraus kommt... b ist ja auch eine natürliche (ganze) Zahl, Nun ist b teiler von c, und es kommt wieder eine natürliche Zahl heraus, dann muss - wenn man c durch a teilt, doch auch eine natürliche (ganze) Zahl herauskommen.
Müsste, theoretisch. Praktisch denke ich gerade darüber nach, aber wenn a=3, b=6 ist,
b/a = 6/3=2
c/b = 12/6 = 2
c/a = 12/3 = 4
Ich erkenne das c>b sein muss. c ist hier jetzt auch ein vielfaches von b, d. h. für
c/a könnte ich schreiben (2b)/a
Irgendwie bin ich entmutigt und möchte daher fragen, wie man es richtig zeigt? :(
Grüße
Phoney
|
|
|
| |
|
Hallo Phoney!
Ist das eigentlich richtig, dass du das erst in 13 Tagen brauchst?
> > bedeutet aber nichts anderes, als a|a, denn so ist doch
> > genau die Relation definiert. Und das bedeutet doch, dass a
> > durch a teilbar ist.
>
> > > reflexiv: [mm]a|a[/mm] [mm]\forall a \in \IN[/mm]
> > > asymm:
> [mm](a|b) \wedge ( b|a) \Rightarrow a=b[/mm]
> >
> > >
> > > transitiv: [mm](a|b)\wedge(b|c) \Rightarrow a|c[/mm]
> > >
> > > Schreibt man das so, oder ist es immernoch falsch?
> >
> > Nein, falsch ist das nicht, aber du hast damit noch nichts
> > gezeigt.
>
> Wie soll man das denn dann anders zeigen? Soll ich Zahlen
> einsetzen und gucken, ob es stimmt oder wie? Z. B. beim
> Transitiven.
>
> Wenn a ein Teiler von b ist und eine ganze Zahl heraus
> kommt... b ist ja auch eine natürliche (ganze) Zahl, Nun
> ist b teiler von c, und es kommt wieder eine natürliche
> Zahl heraus, dann muss - wenn man c durch a teilt, doch
> auch eine natürliche (ganze) Zahl herauskommen.
>
> Müsste, theoretisch. Praktisch denke ich gerade darüber
> nach, aber wenn a=3, b=6 ist,
>
> b/a = 6/3=2
> c/b = 12/6 = 2
> c/a = 12/3 = 4
>
> Ich erkenne das c>b sein muss. c ist hier jetzt auch ein
> vielfaches von b, d. h. für
> c/a könnte ich schreiben (2b)/a
>
> Irgendwie bin ich entmutigt und möchte daher fragen, wie
> man es richtig zeigt? :(
Zur Not könntest du es so mit Worten schreiben. Dann weiß man wenigstens, dass du dir was dabei gedacht hast (das davor war ja nur das, was du zeigen solltest). So hunderprozentig sicher bin ich mir auch nicht, wie man das richtig zeigt, aber es müsste wohl so ähnlich gehen:
ich mach's mal mit der Antisymmetrie. zu zeigen ist also: (a|b [mm] \wedge [/mm] b|a) [mm] \Rightarrow [/mm] a=b
Nun bedeutet a|b aber nichts anderes als dass a ein Vielfaches von b ist, das kann man auch so schreiben: a=k*b für ein [mm] k\in\IN [/mm] (im Fall über [mm] \IZ [/mm] wäre dann natürlich auch [mm] k\in \IZ).
[/mm]
Machen wir dasselbe mit b|a: b=l*a für [mm] l\in\IN.
[/mm]
Da jetzt ja beides gelten soll, setzen wir einfach die zweite Gleichung in die erste ein:
a=k*l*a
Damit diese Gleichung erfüllt ist, muss wohl k*l=1 gelten, und da k und l beide aus [mm] \IN [/mm] sind, folgt: k=l=1 und damit a=b.
Hier siehst du auch, wo der Unterschied zu [mm] \IZ [/mm] ist, da muss dann zwar auch gelten k*l=1, aber es kann k=l=-1 gelten, woraus dann a=-b folgt.
Mit der Transitivität muss es sehr ähnlich gehen. Willst du das jetzt mal alleine versuchen?
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:18 Fr 24.11.2006 | | Autor: | Phoney |
Hallo Bastiane!
> Ist das eigentlich richtig, dass du das erst in 13 Tagen
> brauchst?
Theoretisch schon, da es sich lediglich um Übungsaufgaben handelt. Ich denke mal, wenn ich es bis dahin nicht verstanden habe, kann ich die Aufgabe auch getrost mal bei Seite legen. Solche Aufgaben gibts doch, die man leider niemals versteht... Ich meine, in 13 Tagen wäre ich auch voll aus der Materie schon wieder raus.
> > > bedeutet aber nichts anderes, als a|a, denn so ist doch
> > > genau die Relation definiert. Und das bedeutet doch, dass a
> > > durch a teilbar ist.
> >
> > > > reflexiv: [mm]a|a[/mm] [mm]\forall a \in \IN[/mm]
> > > >
> asymm:
> > [mm](a|b) \wedge ( b|a) \Rightarrow a=b[/mm]
> > >
> > > >
> > > > transitiv: [mm](a|b)\wedge(b|c) \Rightarrow a|c[/mm]
> > > >
> > > > Schreibt man das so, oder ist es immernoch falsch?
> > >
> > > Nein, falsch ist das nicht, aber du hast damit noch nichts
> > > gezeigt.
> >
> > Wie soll man das denn dann anders zeigen? Soll ich Zahlen
> > einsetzen und gucken, ob es stimmt oder wie? Z. B. beim
> > Transitiven.
> >
> > Wenn a ein Teiler von b ist und eine ganze Zahl heraus
> > kommt... b ist ja auch eine natürliche (ganze) Zahl, Nun
> > ist b teiler von c, und es kommt wieder eine natürliche
> > Zahl heraus, dann muss - wenn man c durch a teilt, doch
> > auch eine natürliche (ganze) Zahl herauskommen.
> >
> > Müsste, theoretisch. Praktisch denke ich gerade darüber
> > nach, aber wenn a=3, b=6 ist,
> >
> > b/a = 6/3=2
> > c/b = 12/6 = 2
> > c/a = 12/3 = 4
> >
> > Ich erkenne das c>b sein muss. c ist hier jetzt auch ein
> > vielfaches von b, d. h. für
> > c/a könnte ich schreiben (2b)/a
> >
> > Irgendwie bin ich entmutigt und möchte daher fragen, wie
> > man es richtig zeigt? :(
>
> Zur Not könntest du es so mit Worten schreiben. Dann weiß
> man wenigstens, dass du dir was dabei gedacht hast (das
> davor war ja nur das, was du zeigen solltest). So
> hunderprozentig sicher bin ich mir auch nicht, wie man das
> richtig zeigt, aber es müsste wohl so ähnlich gehen:
>
> ich mach's mal mit der Antisymmetrie. zu zeigen ist also:
> (a|b [mm]\wedge[/mm] b|a) [mm]\Rightarrow[/mm] a=b
>
> Nun bedeutet a|b aber nichts anderes als dass a ein
> Vielfaches von b ist, das kann man auch so schreiben: a=k*b
> für ein [mm]k\in\IN[/mm] (im Fall über [mm]\IZ[/mm] wäre dann natürlich auch
> [mm]k\in \IZ).[/mm]
>
> Machen wir dasselbe mit b|a: b=l*a für [mm]l\in\IN.[/mm]
>
> Da jetzt ja beides gelten soll, setzen wir einfach die
> zweite Gleichung in die erste ein:
>
> a=k*l*a
>
> Damit diese Gleichung erfüllt ist, muss wohl k*l=1 gelten,
> und da k und l beide aus [mm]\IN[/mm] sind, folgt: k=l=1 und damit
> a=b.
>
> Hier siehst du auch, wo der Unterschied zu [mm]\IZ[/mm] ist, da muss
> dann zwar auch gelten k*l=1, aber es kann k=l=-1 gelten,
> woraus dann a=-b folgt.
>
> Mit der Transitivität muss es sehr ähnlich gehen. Willst du
> das jetzt mal alleine versuchen?
Na klar.
transitiv: $ [mm] (a|b)\wedge(b|c) \Rightarrow [/mm] a|c $
Das müsste ja richtig sein?
Nun vergesse ich es immer, heißt das b/a oder a/b?
Ich Glaube es heisst a ist Teiler von...?
Dann ist b auch ein Vielfaches von a, also b=k*a (da das Ergebnis ja in IN sein muss) und c ist ebenfalls ein Vielfaches von a: c=l*a
Für b|c würde in einer Gleichung dann gelten [mm] \br{c}{b}=\br{l*a}{k*a}
[/mm]
Das heißt c durch b ist l/k.
l,k [mm] \in \IN.
[/mm]
c ist auch ein Vielfaches von b. c=s*b
Hm, vielleicht noch mal:
b=k*a
c=s*b
Erste in die zweite
c=s*k*a
Das heißt schon einmal, dass c ein Vielfaches von a ist.
Nur wenn s jetzt [mm] \in \IZ [/mm] ist, dann ist c ja negatives Vielfaches. Hm, ändert das etwas?
Ne, oder?
Gruß von
Johann
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:28 Sa 16.12.2006 | | Autor: | Marc |
Hallo Johann,
damit es noch vor Weihnachten ein Happy End gibt, führe ich die Beweise noch mal vor
> [mm]\le[/mm] = geschwungenes Zeichen
[mm] $\preceq$
[/mm]
>
> Zeigen Sie, dass durch a [mm]\le[/mm] b : [mm]\gdw[/mm] a|b eine partielle
> Ordnung auf [mm]\IN[/mm] definiert ist. Untersichen sie auch, ob es
> sich um eine partielle Ordnung auf [mm]\IZ[/mm] anstatt [mm]\IN[/mm]
> handelt.
> Guten Abend.
>
> Ich muss hierbei ja einfach nur nachweisen, dass eine
> Relation R auf X partielle Ordnung heißt, wenn sie
> reflexiv, antisymmetrisch und transitiv ist.
a|b bedeutet: "a teilt b" bzw. "a ist Teiler von b" bzw. "b wird geteilt von a" bzw. "Es existiert ein [mm] $k\in\IZ$ [/mm] so dass a*k=b"
Für die Reflexivität muss gelten [mm] "$a\preceq [/mm] a$ für alle [mm] $a\in\IG$" ($\IG$ [/mm] ist wahlweise [mm] $=\IN$ [/mm] bzw. [mm] $=\IZ$).
[/mm]
Sei [mm] $a\in\IG$.
[/mm]
[mm] $\Rightarrow\ [/mm] a=1*a$
[mm] $\Rightarrow$ [/mm] Es existiert [mm] $k\in\IZ$ [/mm] mit $a=k*a$ (nämlich k=1)
[mm] $\Rightarrow\ [/mm] a|a$
[mm] $\Rightarrow\ a\preceq [/mm] a$
Für die Antisymmetrie muss gelten: [mm] "$a\preceq [/mm] b\ [mm] \wedge\ b\preceq [/mm] a\ [mm] \Rightarrow\ [/mm] a=b$"
Seien [mm] $a,b\in\IG$ [/mm] mit [mm] $a\preceq [/mm] b\ [mm] \wedge\ b\preceq [/mm] a$
[mm] $\Rightarrow\ \exists k_1\in\IZ\ [/mm] :\ [mm] a=k_1*b$ [/mm] und [mm] $\exists k_2\in\IZ\ [/mm] :\ [mm] b=k_2*a$
[/mm]
[mm] $\Rightarrow\ b=k_2*(k_1*b)$
[/mm]
[mm] $\Rightarrow\ [/mm] b=0\ [mm] \vee\ 1=k_2*k_1$
[/mm]
[mm] $\Rightarrow\ [/mm] b=0\ [mm] \vee\ (k_1,k_2)=(1,1)\ \vee\ (k_1,k_2)=(-1,-1)$
[/mm]
Der Fall $b=0$ kann nur auftreten, wenn auch $a=0$, also $a=b$.
Im Fall [mm] $(k_1,k_2)=(1,1)$ [/mm] gilt ebenfalls $a=b$.
Der Fall [mm] $(k_1,k_2)=(-1,-1)$ [/mm] kann nur auftreten, falls [mm] $\IG=\IZ$ [/mm] ist, es gilt dann aber $a=-b$ bzw. [mm] $a\not=b$. [/mm] Die partielle Ordnung auf [mm] $\IZ$ [/mm] ist damit vom Tisch.
Für die Transitivität muss gelten: [mm] "$a\preceq [/mm] b, [mm] b\preceq [/mm] c\ [mm] \Rightarrow\ a\preceq [/mm] c$"
Seien [mm] $a,b\in\IG$ [/mm] mit [mm] $a\preceq [/mm] b, [mm] b\preceq [/mm] c$
[mm] $\Rightarrow\ \exists k_1\in\IZ\ [/mm] :\ [mm] b=k_1*a$ [/mm] und [mm] $\exists k_2\in\IZ\ [/mm] :\ [mm] c=k_2*b$
[/mm]
[mm] $\Rightarrow\ c=k_2*k_2*a$
[/mm]
[mm] $\Rightarrow$ [/mm] Es existiert [mm] $k\in\IZ$ [/mm] mit $c=k*a$ (nämlich [mm] $k=k_1*k_2$)
[/mm]
[mm] $\Rightarrow\¸a\preceq [/mm] c$
Viele Grüße,
Marc
|
|
|
|
