C/C++ Forum :: Beweis von 3 teilt b, dann 9 teilt b mit Kontraposition

W0lf Mitglied 19:35:41 08.02.2010 Titel:

Hallo,

ich versuche mich gerade an einfachen mathematischen Beweisen und hänge bei folgendem schon fest:

Code:
Wenn 3 kein Teiler von b ist, dann ist 9 kein Teiler von b.

Code:
Wenn 3 kein Teiler von b ist, dann ist 9 kein Teiler von b.

Code:
Wenn 3 kein Teiler von b ist, dann ist 9 kein Teiler von b.

Beweis mittels Kontraposition ist dann:

Code:
Wenn 9 ein Teiler von b ist, dann ist 3 ein Teiler von b

Code:
Wenn 9 ein Teiler von b ist, dann ist 3 ein Teiler von b

Code:
Wenn 9 ein Teiler von b ist, dann ist 3 ein Teiler von b

9 teilt b impliziert doch, dass 3 b teilt. Ja und 3*3 = 9, aber irgendwie weiß ich jetzt nicht, wie ich weitermachen muss.

Vielen Dank schonmal

SeppJ Moderator 19:45:04 08.02.2010 Titel:

Gaaannnzzz ausführlich:

(A) Definition der Teilbarkeit: Wenn a ein Teiler von c ist, dann gibt es eine natürliche Zahl b, so dass a*b=c
(B) 3*3=9
(C) Die natürlichen Zahlen sind abgeschlossen bezüglich *

Aus (A) folgt: Wenn 9 ein Teiler von d ist, dann gibt es eine natürliche Zahl e, so dass e*9=d.
Mittels (B) folgt: e*3*3=d
Laut (C) ist e*3=f eine natürliche Zahl. Es gilt f*3=d
Nach (A) gilt daher: 3 ist ein Teiler von d

drakon Mitglied 22:00:39 08.02.2010 Titel:

So ausführlich ist es nicht.

Und vor allem benutzt du da die Kommutativität bzg. *, was du nicht sagst, dass es gilt (natürlich gilt es), aber auch gar nicht nötig ist, wenn du den Beweis korrekt führst:

Das hier ist schon falsch:

Zitat:

Aus (A) folgt: Wenn 9 ein Teiler von d ist, dann gibt es eine natürliche Zahl e, so dass e*9=d.

eher: 9*e=d sonst weichst du bereits von der Definition ab.

Zitat:

Mittels (B) folgt: e*3*3=d

Wird zu 3*3*e=d

und das zu: 3*f=d

und somit ist 3 ein Teiler von d.

Wie du siehst wird die Kommutativität von * nicht benutzt.

Mag kleinkrämerisch wirken, aber das korrekte anwenden der Definitionen ist essentiell, ansonsten ist der Beweis genau so falsch, wie wenn du sagst "ja, ist doch klar".

/EDIT
@W0lf:
Halte dich immer exakt an die Definitionen. Vor allem dann, wenn dir alles klar erscheint musst du dich komplett auf die Definitionen zurück ziehen und diese benutzen und rein gar nichts einfach mal so als gegeben annehmen. (Wenn man z.B Teilbarkeit für Matrizen definieren will ist der Fehler, der oben gemacht wurde verheerend).

SeppJ Moderator 22:20:21 08.02.2010 Titel:

drakon hat natürlich vollkommen Recht. Merke: Auch wenn etwas unglaublich einfach aussieht, sollte man trotzdem sorgfältig arbeiten.

Unregistrierter

W0lf schrieb:

Code:
Wenn 9 ein Teiler von b ist, dann ist 3 ein Teiler von b

Code:
Wenn 9 ein Teiler von b ist, dann ist 3 ein Teiler von b

Code:
Wenn 9 ein Teiler von b ist, dann ist 3 ein Teiler von b

Aus 3|9 und 9|b folgt 3|b
Beweis: 9 = q*3, b = p*9 --> b = p*(q*3) = (p*q)*3 --> 3|b

drakon Mitglied 22:53:06 08.02.2010 Titel:

Auch du benutzt hier Kommutativität, sowie auch Assoziativität. Ich halte den Beweis von SeppJ für besser, weil er auf weniger Annahmen basiert und daher allgemeiner ist.
btw:
Du hättest eher den Doppelpfeil nehmen sollen, weil sonst ist es eher eine Aussage (Implikation), aber ob sie jetzt wahr oder falsch ist steht da jetzt noch nicht.

Unregistrierter

drakon schrieb:

Ich halte den Beweis von SeppJ für besser, weil er auf weniger Annahmen basiert und daher allgemeiner ist.

3*3=9 ist keine Annahme?

drakon schrieb:

Du hättest eher den Doppelpfeil nehmen sollen, weil sonst ist es eher eine Aussage (Implikation), aber ob sie jetzt wahr oder falsch ist steht da jetzt noch nicht.

Sie ist nur dann wahr, wenn 3|9 und 9|b. Fehlt Dir der Beweis für 3|9 ?

drakon Mitglied 23:33:57 08.02.2010 Titel:

Dragoner schrieb:

drakon schrieb:

Ich halte den Beweis von SeppJ für besser, weil er auf weniger Annahmen basiert und daher allgemeiner ist.

3*3=9 ist keine Annahme?

Nein. Folgt aus A.

Zitat:

drakon schrieb:

Du hättest eher den Doppelpfeil nehmen sollen, weil sonst ist es eher eine Aussage (Implikation), aber ob sie jetzt wahr oder falsch ist steht da jetzt noch nicht.

Sie ist nur dann wahr, wenn 3|9 und 9|b. Fehlt Dir der Beweis für 3|9 ?

Ich meinte da eher die syntaktische Feinheit. -> steht für Implikation. => steht für eine Implikation, die wahr ist (aka Folgerung). Bsp:
(1) a->b ( := ¬a v b )
(2) a=>b ( := a->b ist wahr )
Bei (1) kann ich nichts über die Wahrheitswerte von a und b sagen. Bei (2) weiss ich, dass wenn a wahr ist auch b wahr sein muss.

W0lf Mitglied 23:45:21 08.02.2010 Titel:

Danke.

Die Diskussion, die darum jetzt entstanden ist, hilft auch ungemein zum Verständnis :-) (Nein, keine Ironie)

Unregistrierter

drakon schrieb:

Dragoner schrieb:

drakon schrieb:

Ich halte den Beweis von SeppJ für besser, weil er auf weniger Annahmen basiert und daher allgemeiner ist.

3*3=9 ist keine Annahme?

Nein. Folgt aus A.

Nein, A, die Definition der Teilbarkeit, ist allgemein. Wenn a (≠0, was er vergessen hat) c teilt, dann gibt es eine natürliche Zahl b, so dass a*b=c Das sagt nichts über den konkreten Fall 3|9 aus. Hätte er es sonst hinschreiben müssen?

drakon Mitglied 01:46:03 09.02.2010 Titel:

Dragoner schrieb:

drakon schrieb:

Dragoner schrieb:

drakon schrieb:

Ich halte den Beweis von SeppJ für besser, weil er auf weniger Annahmen basiert und daher allgemeiner ist.

3*3=9 ist keine Annahme?

Nein. Folgt aus A.

Nein, A, die Definition der Teilbarkeit, ist allgemein. Wenn a (≠0, was er vergessen hat) c teilt, dann gibt es eine natürliche Zahl b, so dass a*b=c Das sagt nichts über den konkreten Fall 3|9 aus. Hätte er es sonst hinschreiben müssen?

Ich war unpräzise. Wir dürfen 3*3=9 benutzen, weil * definiert ist. (Sonst können wir ja Teilbarkeit gar nicht definieren). Das 3|9 folgt dann aus A. So meinte ich das. Und das ist keine Annahme.
Ok, genau genommen ist es die Annahme der Assoziativität. Man braucht sie, wenn man die Transitivität allgemein beweisen will (daher ist es besser solche Beweise allgemein zu halten, dann passiert eine solche Subtilität nicht):

Code:
Behauptung: a\|b AND b\|c => a\|c Beweis: d,e Elemente von Z a\|b =>(def.) ad=b => (ad)e=c =>(ass.) a(de)=c =>(def.) a\|c q.e.d. b\|c =>(def.) be=c

Code:
Behauptung: a\|b AND b\|c => a\|c Beweis: d,e Elemente von Z a\|b =>(def.) ad=b => (ad)e=c =>(ass.) a(de)=c =>(def.) a\|c q.e.d. b\|c =>(def.) be=c

Code:
Behauptung: a\|b AND b\|c => a\|c Beweis: d,e Elemente von Z a\|b =>(def.) ad=b => (ad)e=c =>(ass.) a(de)=c =>(def.) a\|c q.e.d. b\|c =>(def.) be=c

Kommutativität ist aber nicht notwendig.

life Mitglied 12:16:21 09.02.2010 Titel:

drakon schrieb:

Kommutativität ist aber nicht notwendig.

Benutzten auch weder SeppJ noch Dragoner...

drakon Mitglied 17:56:54 09.02.2010 Titel:

life schrieb:

drakon schrieb:

Kommutativität ist aber nicht notwendig.

Benutzten auch weder SeppJ noch Dragoner...

Doch.

life Mitglied 23:28:08 09.02.2010 Titel:

drakon schrieb:

life schrieb:

drakon schrieb:

Kommutativität ist aber nicht notwendig.

Benutzten auch weder SeppJ noch Dragoner...

Doch.

Wo denn?

drakon Mitglied 23:43:40 09.02.2010 Titel:

Sepp:

Zitat:

e*9=d.

Dragoner:

Zitat:

(p*q)*3 --> 3|b

Um nur 2 zu nennen.

life Mitglied 23:46:11 09.02.2010 Titel:

Beide gehen offensichtlich von einer Definition ala "a teilt b gdw. es ein c \in Z mit c*a=b gibt" aus. Dementsprechend benutzen sie keine Kommutativität, sondern nur eine leicht andere Definition als Du.

drakon Mitglied 23:51:13 09.02.2010 Titel:

Sie benutzen aber nicht konseqent die andere Schreibweise. Wenn es nur eine gibt, dann geht es in Ordnung, aber sobald man mischt wirds gefährlich.

life Mitglied 23:59:09 09.02.2010 Titel:

Ich sehe keine inkonsistente Benutzung der Definition..

drakon Mitglied 00:15:10 10.02.2010 Titel:

Meine Güte:

Zitat:

(A) Definition der Teilbarkeit: Wenn a ein Teiler von c ist, dann gibt es eine natürliche Zahl b, so dass a*b=c

Aus (A) folgt: Wenn 9 ein Teiler von d ist, dann gibt es eine natürliche Zahl e, so dass e*9=d.

Nach obiger Definition muss es lauten 9*e=d. Er schreibt aber e*9=d. Er benutzt Kommutativität.

Im übrigen hast du ja selbst gemerkt, dass Wikipedia keine andere Definition verwendet und ich kann nicht sagen, ob es überhaupt erlaubt ist.

life Mitglied 00:21:45 10.02.2010 Titel:

Seine Definition habe ich mir nicht angeschaut. Verwendet man aber die Definition von Teilbarkeit wie ich sie oben angegeben habe, so benutzen sowohl SeppJ als auch Dragoner _keine_ Kommutativität.

Wikipedia definiert Teilbarkeit wie Du bzw. wie in (A).

drakon Mitglied 01:12:04 10.02.2010 Titel:

Ich hatte im Kopf, dass sie gemischt haben, aber machen sie tatsächlich nicht.

Allerdings ändert das nichts an meiner Aussage. Mit der obigen Definition war Kommutativität im Spiel. Einfach eine andere Definition zu nehmen geht nicht. Und ich habe deine Version der Teilbarkeit auch noch nie gesehen.

Man muss sich an die gegebenen Definitionen halten, ansonsten macht das ganze gar keinen Sinn.

Unregistrierter

>> Man muss sich an die gegebenen Definitionen halten, ansonsten macht das ganze gar keinen Sinn.

Z bildet mit der Multiplikation, auf die wir Teilbarkeit zurückführen, einen kommutativen Ring. Auch gilt in Z das Assoziativgesetz. Wir können alle bekannten Eigenschaften benutzen, ohne sie neu hinterfragen zu müssen, wenn wir z.B. wie hier Transivität der Teilbarkeit beweisen wollen.

Unregistrierter

>> Transivität
Soll heissen Transitivität

SeppJ Moderator 10:07:22 10.02.2010 Titel:

Dann gilt das aber nur in Z. Ich habe bei meinem Beweis zwar auch von natürlichen Zahlen gesprochen, aber im Prinzip könnte man da alle Mengen einsetzen die eine Multiplikation kennen (z.B. Matrizen). Und so kann man dann ein viel allgemeineres Gesetz formulieren, sofern man nicht die Kommutativität benutzt.

Ist dann zwar an der Aufgabenstellung vorbei, aber dafür viel schöner :live:

.

life Mitglied 11:47:56 10.02.2010 Titel:

drakon schrieb:

Man muss sich an die gegebenen Definitionen halten, ansonsten macht das ganze gar keinen Sinn.

Stimmt. Bei SeppJ könnte man tatsächlich bemängeln, dass erst Teilbarkeit nochmal definiert, nur um dann doch eine andere Definition zu benutzen. Aber woher weißt du, welche Definition Dragoner im Kopf hatte / vom Prof gegeben wurde?

Edit: Ich habe übrigens grad mal in meinem schlauen Zahlentheoriebüchlein nachgeschaut: Dort verwendet sie die Definition, die ich angegeben habe (sogar genau die gleichen Buchstaben

).

drakon Mitglied 16:58:50 10.02.2010 Titel:

Dragoner schrieb:

>> Man muss sich an die gegebenen Definitionen halten, ansonsten macht das ganze gar keinen Sinn.

Z bildet mit der Multiplikation, auf die wir Teilbarkeit zurückführen, einen kommutativen Ring. Auch gilt in Z das Assoziativgesetz. Wir können alle bekannten Eigenschaften benutzen, ohne sie neu hinterfragen zu müssen, wenn wir z.B. wie hier Transivität der Teilbarkeit beweisen wollen.

Die Eigenschaft, dass Teilbarkeit Transitiv ist ist ebenfalls bekannt.

Man ist üblicherweise ja auch daran interessiert einen Beweis auf möglichst tiefer (und somiter allgemeiner) Stufe durchzuführen. Z.B ist der erste Beweis von SeppJ lediglich für exakt diese Zahlen erbracht und könnte ja theoretisch darauf beruhen, dass 3^2=9 ist. Und dann würde die Teilbarkeit für andere Zahlen nicht mehr gehen. (ob das jetzt viel Sinn macht ist eine komplett andere Frage, aber solche Sachen sind wichtig, wenn man in nicht ganz so bekannten Algebren operieren und etwas beweise will und da ist es sehr wichtig genau die Definitionen zu benutzen, die man hat)
Klar, wenn explizit in der Aufgabenstellung steht, dass man Kommutativität benutzen darf, dann ist es kein Thema, aber üblicherweise sind die Aufgaben ja so gestellt, dass man genau das hat, was man braucht.

Wie ich schon sagte ist das nette an einer solchen Abstraktion ja, dass man lediglich bei testen muss, ob die Voraussetzungen gegeben sind und schon kann ich den gleichen Beweis benutzen und weitere Eigenschaften folgern, ohne dass ich sonst noch was machen muss.

Zitat:

Stimmt. Bei SeppJ könnte man tatsächlich bemängeln, dass erst Teilbarkeit nochmal definiert, nur um dann doch eine andere Definition zu benutzen. Aber woher weißt du, welche Definition Dragoner im Kopf hatte / vom Prof gegeben wurde?

Ich bin davon ausgegangen, dass er bereits genannte Definition verwendet.

Bashar Mitglied 17:10:50 10.02.2010 Titel:

Ich finde, man sollte schon manchmal die Kirche im Dorf lassen und nicht jeden Beweis in der allgemeinsten Theorie, in der die Aussage wahr ist, durchführen.

drakon Mitglied 17:18:23 10.02.2010 Titel:

Bashar schrieb:

Ich finde, man sollte schon manchmal die Kirche im Dorf lassen und nicht jeden Beweis in der allgemeinsten Theorie, in der die Aussage wahr ist, durchführen.

Ja, aber mein Punkt war eher das exakte arbeiten und wenn man es nicht bereits bei einfachen Aufgaben macht, dann hat man relativ schnell bei etwas komplexeren Probleme, wenn man sich nicht penibelst an die Definition hält. Das war eher der Punkt, den ich hervorheben wollte. An meiner Uni gäbe ein solcher Fehler, wie SeppJ gemacht hat 0 Punkte.

life Mitglied 17:46:08 10.02.2010 Titel:

drakon schrieb:

An meiner Uni gäbe ein solcher Fehler, wie SeppJ gemacht hat 0 Punkte.

Echt? Ich fand ja bei uns schon die Korrektoren teilweise übertrieben pingelig, aber für soetwas 0 Punkte zu geben hätten die sich sicher nicht getraut

.

SeppJ Moderator 17:52:39 10.02.2010 Titel:

drakon schrieb:

Bashar schrieb:

Ich finde, man sollte schon manchmal die Kirche im Dorf lassen und nicht jeden Beweis in der allgemeinsten Theorie, in der die Aussage wahr ist, durchführen.

Ja, aber mein Punkt war eher das exakte arbeiten und wenn man es nicht bereits bei einfachen Aufgaben macht, dann hat man relativ schnell bei etwas komplexeren Probleme, wenn man sich nicht penibelst an die Definition hält. Das war eher der Punkt, den ich hervorheben wollte. An meiner Uni gäbe ein solcher Fehler, wie SeppJ gemacht hat 0 Punkte.

Woah, ihr habt aber strenge Tutoren/Profs. Ich hätte 7/10 Punkten gegeben. Aber dann wiederum mache ich auch keine reine Mathematik.

life Mitglied 18:02:47 10.02.2010 Titel:

Selbst 7/10 fände ich schon ziemlich streng. Im Prinzip ist es ja nur ein Zahlendreher gewesen, mit dem dann aber konsequent und richtig weitergerechnet wurde. Ich hätte wohl eher 9/10 Punkte gegeben, wenn mir der Fehler überhaupt aufgefallen wäre. Aber dann wiederum mache ich auch keine Korrekturen in der reinen Mathematik :P.

drakon Mitglied 19:50:48 10.02.2010 Titel:

Naja. Wenn man die Einfachheit der Aufgabe beachtet finde ich das nicht soo schlimm.
Wie gesagt wird bei uns Wert auf exaktes arbeiten gelegt. Ob das jetzt tatsächlich 0 Punkte gegeben hat weiss ich aber nicht soo genau (der Prof. hat uns damit immer gedroht, aber naja.. wahrscheinlich ist das auch ein wenig Angstmache gewesen, weil er halt will, dass wir exakt arbeiten), aber ich mehr als 5 von 10 Punkte hätte das nicht gegeben.
btw:
Ich studiere auch keine Mathematik.