Halbordnungsrelation bestimmen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:07 Sa 08.10.2011 | | Autor: | Tobi85_ |
| Aufgabe | Sei A = {Teiler von 360 >= 1}. Beispielsweise sind 1; 2; 3; 4; 5; 6; 8; 9; 10; 30; 40; 360 Elemente von
A, da 360 durch alle diese Zahlen ohne Rest teilbar ist. Betrachten Sie im Folgenden die Relation
R Teilmenge A x A mit (x; y) € R <-> x ist durch y ohne Rest teilbar.
a) Zeigen Sie die Gültigkeit der Behauptung, dass die Relation R eine Halbordnungsrelation ist |
Irendwie komme ich nicht auf die Bedingungen die zeigen, dass es eine Halbordnungsrelation ist.
Wenn ich die Relation bilde sind doch dann aufgrund der Vorschrift folgende Elemente enthalten oder?:
R= {(1,360),(2,360),(3,360),(4,360),(5,360),(6,360),(8,360),(9,360),(10,360),(30,360),(40,360),(360,360)}
Nur mit dieser konstellation lässt sich ja
transitivität,antisymmetrie und reflexivität für eine Halbordnungsrelation nicht nachweisen oder?
Oder gehören noch mehr Elemente in die Menge?
Vielen Dank für Rat!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:02 Sa 08.10.2011 | | Autor: | Fulla |
Hallo Tobi,
> Sei A = {Teiler von 360 >= 1}. Beispielsweise sind 1; 2; 3;
> 4; 5; 6; 8; 9; 10; 30; 40; 360 Elemente von
> A, da 360 durch alle diese Zahlen ohne Rest teilbar ist.
> Betrachten Sie im Folgenden die Relation
> R Teilmenge A x A mit (x; y) € R <-> x ist durch y ohne
> Rest teilbar.
>
> a) Zeigen Sie die Gültigkeit der Behauptung, dass die
> Relation R eine Halbordnungsrelation ist
> Irendwie komme ich nicht auf die Bedingungen die zeigen,
> dass es eine Halbordnungsrelation ist.
>
> Wenn ich die Relation bilde sind doch dann aufgrund der
> Vorschrift folgende Elemente enthalten oder?:
>
> R=
> {(1,360),(2,360),(3,360),(4,360),(5,360),(6,360),(8,360),(9,360),(10,360),(30,360),(40,360),(360,360)}
Das hieße ja z.B. für [mm](x,y)=(1,360)[/mm]: 1 ist ohne Rest durch 360 teilbar. Richtig wäre es andersrum, also etwa [mm](360,1)\in R[/mm].
> Nur mit dieser konstellation lässt sich ja
> transitivität,antisymmetrie und reflexivität für eine
> Halbordnungsrelation nicht nachweisen oder?
Doch. Für den Beweis der Transitivität nimmst du dir 3 Elemente [mm]x,y,z\in A[/mm] mit [mm](x,y)\in R[/mm] und [mm](y,z)\in R[/mm]. Wenn daraus folgt, dass [mm](x,z)\in R[/mm] ist die Relation transitiv.
Wenn du die Relation in [mm](x,y)\in R\ \Leftrightarrow\ y|x[/mm] (y teilt x) [mm]\Leftrightarrow\ x=k*y[/mm] für ein [mm]k\in\mathbb N[/mm] umschreibst, ist der Beweis ganz leicht.
Probier mal die drei Bedingungen zu beweisen und melde dich hier wieder, wenn du Probleme hast.
> Oder gehören noch mehr Elemente in die Menge?
> Vielen Dank für Rat!
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:11 Sa 08.10.2011 | | Autor: | Tobi85_ |
Oops!
Natürlich anders herum sorry. war ich wohl unaufmerksam!
Also wenn ich dann nun 3 Elemente raussuche zb: x= 360, y = 1 und z = 2. sind ja alle [mm] $\in$ [/mm] R.
So und dann wäre ja transitivität: [mm] (x,y)$\in$ [/mm] R => (360,1): 360:1 = 360 <=> 360 = 360*1
für (y,z) müsste ja dann die Bedingung lauten: [mm] (y,z)$\in$ [/mm] R => (1,2): 1:2 = 0,5 <=> 1 = 0,5 * 2
für (x,z): (360,2): 360:2 = 180 <=> 360 = 360*1 (da k*y)
Uff, kann man das so stehen lassen? Also ich glaub mit Beweisen hab ich echte Probleme...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:14 Sa 08.10.2011 | | Autor: | Fulla |
Hallo nochmal,
> Oops!
> Natürlich anders herum sorry. war ich wohl unaufmerksam!
>
> Also wenn ich dann nun 3 Elemente raussuche zb: x= 360, y =
> 1 und z = 2. sind ja alle [mm]\in[/mm] R.
Nein, das sind Elemente von A.
> So und dann wäre ja transitivität: (x,y)[mm]\in[/mm] R => (360,1):
> 360:1 = 360 <=> 360 = 360*1
> für (y,z) müsste ja dann die Bedingung lauten: (y,z)[mm]\in[/mm]
> R => (1,2): 1:2 = 0,5 <=> 1 = 0,5 * 2 [mm]\red{(1,2)\not\in R}[/mm] denn 1 ist nicht (ohne Rest) durch 2 teilbar!
> für (x,z): (360,2): 360:2 = 180 <=> 360 = 360*1 (da k*y)
Ich würde y und z tauschen: y=2, z=1 - sonst ist es nämlich falsch (siehe roter Kommentar). Dann gilt: [mm](x,y)=(360,2)\in R[/mm] und [mm](y,z)=(2,1)\in R[/mm] (2 teilt 360 und 1 teilt 2).
Die Aufgabe ist nun zu folgern, dass dann auch [mm](x,z)=(360,1)\in R[/mm] ist, bzw 1 teilt 360. Das stimmt natürlich, aber du hast jetzt nur ein Beispiel durchgerechnet. Um die Transitivität zu zeigen, musst es für alle Elemente aus A beweisen!
Natürlich ist es nicht falsch, von einem Beispiel auszugehen - im Gegenteil, das kann dich durchaus auf die richtige Spur bringen. Lass mich dieses Beispiel mal ganz ausführlich hinschreiben:
Wir haben [mm]x,y,z\in A[/mm] mit x=360, y=2, z=1 und es gilt [mm](x,y), (y,z)\in R[/mm]. Also [mm]2\ |\ 360[/mm] und [mm]1\ |\ 2[/mm]. Umgeschrieben heißt das: [mm]360=\green{180}*\blue{2}[/mm] und [mm]\blue{2}=\green{2}*1[/mm] (die grünen Zahlen sind jeweils die Reste beim Teilen). Wenn man jetzt die zweite blaue 2 (das ist unser y) in die erste einsetzt, steht da [mm]360=180*2*1[/mm] oder mit den Variablen [mm]x=180*2*z[/mm]. Das heißt aber, dass x ein Vielfaches von z ist, bzw, dass x durch z teilbar ist. Also gilt [mm](x,z)=(360,1)\in R[/mm].
So jetzt zum allgemeinen Beweis. Es steht ja schon fast da... Ersetze die grünen Zahlen durch Variablen, etwa n und m. Du kannst dann für beliebige [mm]x,y\in A[/mm] aus [mm](x,y)\in R[/mm] folgern, dass [mm]x=n*y[/mm]. Analog (mit [mm]z\in A[/mm]): [mm](y,z)\in R\ \Leftrightarrow\ y=m*z[/mm].
Kommst du jetzt alleine klar?
> Uff, kann man das so stehen lassen? Also ich glaub mit
> Beweisen hab ich echte Probleme...
Ach, das wird schon... Aber poste doch bitte Rückfragen auch als "Fragen", sonst gehen sie im Forum evtl unter...
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:47 Sa 08.10.2011 | | Autor: | Tobi85_ |
Hi nochmal,
Danke das du mir das Beispiel vorgerechnet hast.
Ja jetzt ist es mir klar wie ich vorgehen muss.
Du hast natürlich recht, allgemein muss ich es natürlich auch noch beweisen. Und das ist vermutlich mein Problem, das ich weiss ich muss es ja für alle Elemente in der Relation beweisen, aber dann wäre ich ja stundenlang am rechnen wenn ich jede Zahl durchgehe, und in der Klausur habe ich nur 1 1/2 zeit. Sogesehen vergesse ich immer das ich ja den Beweis dann mit den Variablen zeigen muss
Durch dein Beispiel habe ich es nun verstanden und kann hoffentlich die anderen zwei Bedingungen auch noch nachweisen.
|
|
|
|
