[PDF] Elementare Beweismethoden 24.04.2015 Bevor die

View - Download Elementare Beweismethoden

Previous PDF

Next PDF

Elementare Beweismethoden

Christian Hensel

24.04.2015

Vortrag zum Thema "Elementare Beweismethoden"

Inhaltsverzeichnis

1 Einführung und wichtige Begriffe 1

2 Direkter Beweis 2

3 Widerspruchsbeweis - indirekter Beweis 4

1 Einführung und wichtige Begriffe

Beweisführung besser verstanden werden.•EinAxiomist die Grundlage aller Beweise auf einem Gebiet. Es handelt sich

um einen unbeweisbaren Satz. Beispielsweise wird im Dezimalzahlensystem ohne

Beweis hingenommen, dass1 + 1 = 2gilt.[1]•SeienAundBzwei mathematische Aussagen, dann schreiben wirA?B, wenn

wir "ausAfolgtB" ausdrücken wollen. Dies bezeichnen wir alsImplikation.[2, S. 4]•Gilt die Implikation in beide Richtungen, alsoA?BundB?A, so schreiben wir auchA?B. Hier sprechen wir dann vonÄquivalenz.[2, S. 4] 1 •DieNegationeiner AussageAwird mit¬Abezeichnet und als "nichtA" gespro- chen. HatAalso den Wahrheitsgehaltw, so hat¬Aden Wahrheitsgehaltfund umgekehrt.[2, S. 3]

Wann ist eine Behauptung bewiesen?

Sei{A1,...,An}eine Menge von Axiomen undXeine Behauptung. Dann ist in der Ma- thematik die BehauptungXbewiesen, "wenn eine endliche Kette von logisch korrekten

Implikationen

{A1,...,An} ?B1? ··· ?Bm?X [...]zu der BehauptungXführt" [3, S. 7]. Anstatt einer Kette mit logisch korrekten

X?C1? ··· ?Cm? {A1,...,An}(1)

Diese Kette beginnt mit einer BehauptungXund endet mit einer Menge{A1,...,An} von Axiomen. Die Kette (1) ist für die Beweisführung hinreichend, jedoch nicht not- wendig, da für die Beweisführung lediglich die Implikation in der Richtung Axiome? Behauptung gebraucht werden. Wichtig bei einer Äquivalenzkette ist, dass es sich bei allen Kettenelementen um Äquivalenzen handelt [3, S. 7]. Dies zeigt das folgende Bei- spiel 1.

2 =-2????

BehauptungX?

fehlende Äquivalenz2

2= (-2)2?4 = 4????

Axiom(2)

2 Direkter BeweisEin direkter Beweis liegt vor, wenn die Implikationskette übersichtlich ist und gut nach-

vollzogen werden kann. Weiter werden hierbei keine besonderen Techniken verwendet [3,

S. 7].

Beispiel 1

2

Wir wollen folgenden Satz aus der Analysis I Vorlesungen stückweise beweisen:Seien(an)n?Nund(bn)n?Nzwei konvergente Folgen mit den Grenzwertenlimn→∞(an) =a

undlimn→∞(bn) =b. Dann konvergiert auch die Folge(an+bn)n?N.1

Entnommen aus [3, S. 7].

2Beispiel und Definition entnommen aus [2, S. 113-117].

2 Sie lautet:Eine Folgeanheißt konvergent gegena, falls gilt: Für alle? >0existiert einn0?N mit der Eigenschaft|an-a|< ?für allen≥n0. Hierbei bezeichnetaden Grenzwert der

Folge.

(an)n?N= 1-1n . Diese Folge besitzt offensichtlich den Grenzwertamita= limn→∞1-1n = 1

Grenzwerta.

0

0.20.40.60.811.2

0 5 10 15 20(an)n?Nn(an)n?N= 1-1n

?-Umgebung vona ?-Umgebung vona

Grenzwerta

Abbildung 1

V eranschaulichungder F olgendefinition

Wir erkennen, dassn0= 11gilt. Fürn≥n0erhalten wir|an-a|< ?. Nun wollen wir obigen Satz aber auch korrekt beweisen. Nach Voraussetzung existierenn1,n2?Nmit |an-a|Nun gilt für allen≥max{n1,n2} ?=?2 +?2 >|an-a|+|bn-b| ≥ |an-a+bn-b|=|an+bn-(a+b)| Hierbei ist die erste Ungleichung nach Voraussetzung erfüllt. Die zweite Ungleichung wird durch die Dreicksungleichung erfüllt. Hierbei handelt es sich um einen Satz aus der beiden anderen Seiten ist. Wegen? >|an+bn-(a+b)|ist die Summe zweier konvergenten Folgen somit auch konvergent. 3

Beispiel 2

3 (a+b)x=ax+bxund(a+b)y=ay+by, sowie das KommutativgesetzA2, für das gilt:xy=yx. Damit erhalten wir folgende transparente Implikationskette (a+b)2= (a+b)(a+b)???? x=a???? y

1(a+b) +b????

y

2(a+b)

=a2+ab+ba????

AxiomA2+b2=a2+ 2ab+b2

Beispiel 3

4 Hier soll bewiesen werden, dass fürx,y >0die Ungleichungx+y2 ≥⎷xy≥21 x +1y gilt. ⎷x-⎷y ?2≥0????? A ≥⎷xy Die erste Ungleichung ist also gezeigt. Wir erhalten die zweite Ungleichung wie folgt: ⎷xy=2xy2 ⎷xy ≥2xyx+y=21 x +1y

3 Widerspruchsbeweis - indirekter BeweisBei einem Widerspruchsbeweis handelt es sich um "eine endliche Kette von logisch kor-

rekten ImplikationenX?B1? ··· ?Bm?W=A,(3) an deren Anfang die Negation eine BehauptungXsteht und am Ende ein Widerspruch, also die NegationAeines Axioms"[3, S. 9]. Hierbei ist zu beachten, dass entweder die AussageXoder die AussageXrichtig sein

Entnommen aus [3, S. 7].

4Entnommen aus [3, S. 8].

5Entnommen aus [3, S. 10].

6Entnommen aus [3, S. 10].

4

Tabelle 1:V erschiedeneBeispiele

6zu richtigen und falschen NegationenBehauptungXrichtige Negation falsche NegationAlle Schafe sind schwarz Nicht alle Schafe sind schwarz Alle Schafe sind nicht schwarz

Jede Zahl ist gerade Nicht jede Zahl ist gerade Jede Zahl ist ungerade A. hat einen Sohn A. hat keinen Sohn A. hat eine Tochter i iist rationaliiist nicht rationaliiist irrationalBeispiel 4 7 Die BehauptungX="Es gibt unendliche viele Primzahlen" kann mit einem Wider- spruchsbeweis gezeigt werden. Die Negation dieser Behauptung lautetX="Es gibt endlich viele Primzahlen". AngenommenXsei richtig undJsei die endliche Anzahl al- ler Primzahlen. Wir listen alle Primzahlen

8p1= 2,p2= 3,...,pJ, aufsteigend auf und

bilden deren Produkt: N=J? k=1p k=p1·p2·...·pJ Nist durch alle Primzahlen teilbar. Somit istN+ 1durch keine Primzahl teilbar und somit selbst eine Primzahl. Diese Primzahl fehlt aber in der obigen Liste, da N+ 1> N≥pJgilt. Da wir aber angenommen haben, dass die obige Liste alle Prim-

Beispiel 5

9 Gegeben seinen drei irrationale Zahlen. Jetzt wollen wir die BehauptungX="Unter diesen drei Zahlen gibt es zwei, deren Summe ebenfalls irrational ist" mit einem Wider- drei irrationalen Zahlen gibt es keine zwei, deren Summe irrational ist". Anders ausge- drückt haben also je zwei von unseren drei Zahlen eine rationale Summe. Bezeichnen wir nun unsere irrationalen Zahlen mitx,yundz, dann sind also die Summena=y+z, b=z+xundc=x+yalle rational. Jetzt gilt aber x=(z+x) + (x+y)-(y+z)2 =b+c-a2 Nach unserer Annahme sind die Zahlena,bundcrational. Somit muss auchxrational sein. Das ist aber ein Widerspruch zu unserer Voraussetzung, dass alle drei Zahlenx,y undzirrational sind. Dieser Widerspruch impliziert, dass die ursprüngliche Behauptung

Xrichtig ist.7

Entnommen aus [3, S. 10].

81 ist keine Primzahl.

9Entnommen aus [3, S. 11].

5 X n=»die Zahln3-1ist durchn-1teilbar", lassen sich mit der Methode der voll-

chen wir vomInduktionsanfang.•In einem zweiten Schritt nehmen wir an, dass fürk≥n0die BehauptungXk

richtig sei. Wir sprechen dabei von derInduktionsvoraussetzungoder von derIn- duktionsannahme.•Abschließend muss gezeigt werden, dass die ImplikationXk?Xk+1richtig ist.

Wir sprechen vomInduktionsschritt.

Nach demInduktionsprinzipist dannXnfür jedesn≥n0richtig.

Beispiel 6

10 a i,j=? ?????-1fallsi=j-1

1fallsi=j

j

2fallsi=j+ 1

0sonst

Nun wollen wir zeigen, dassdet(An) =n!gilt.

A n=( ((((((((((((1-1 0 0 0...0 1

21-1 0 0...0

0 2

21-1 0...0

...0............ ...0 .........-1

0...0 (n-1)21)

))))))))))))10 Klausuraufgabe I.6 der Vorlesung Lineare Algebra I und II vom Frühjahr 2013. 6

Insbesondere erhalten wir

det(A1) =? 1? = 1 = 1!unddet(A2) =?1-1 1 1? = 1-(-1) = 2 = 2! dass für ein gewissesn?Ndie Aussagen det(An-2) = (n-2)!unddet(An-1) = (n-1)! gelten. Für den Induktionsschrittentwickeln wir nach der letzten Zeile und erhalten det(An) =-(n-1)2·det( ((((((((((((1-1 0 0 0...0 1

21-1 0 0...0

0 2

21-1 0...0

...0............ ...0 ......1 0

0...0 (n-2)21)

))))))))))))+ 1·det(An-1). Entwickeln wir die erste Determinante nun nach der letzten Spalte, so ergibt sich det(An) =-(n-1)2·(-1)·det( ((((((((((((1-1 0 0 0...0 1

21-1 0 0...0

0 2

21-1 0...0

...0............ ...0 ......1 0

0...0 (n-3)21)

=An-2+det(An-1). Einsetzen der Induktionsvoraussetzung liefert also det(An) = (n-1)2·(n-2)! + (n-1)! = (n-1)·(n-1)·(n-2)!???? =(n-1)!+(n-1)! = (n-1)!·(n-1) + (n-1)! = (n-1)!·((n-1) + 1) = (n-1)!·n=n!

Beispiel 7

11 Hier sollen wir die SummeSnder erstennungeraden Zahlen berechnen. Offensichtlich giltS1= 1,S2= 4undS3= 9. Folglich wollen wir beweisen, dassSn=n2für jedes11

Entnommen aus [3, S. 14].

7 natürlichengilt und wenden die drei oben genannten Schritte an.

Induktionsanfang:S

1= 1ist richtig.

Induktionsannahme:Es seiSk=k2.

Induktionsschritt:Dann istSk+1=Sk+ (2k+ 1) =k2+ 2k+ 1 = (k+ 1)2.

Somit ist die FormelSn=n2fürn=k+ 1bewiesen.

Beispiel 8

12 DerSatz von Moivrebezieht sich auf komplexe Zahlen und besagt, dass für jede natürli- che Zahlnund jede reelle Zahlxdie Beziehung(cosx+isinx)n= cosnx+isinnxgilt. Induktion beweisen und wenden wieder die drei oben genannten Schritte an: Induktionsanfang:Fürn= 1ist die Aussage offensichtlich richtig. Induktionsannahme:Angenommen, derSatz von Moivregelte fürn=k. Es sei also (cosx+isinx)k= coskx+isinkx. Induktionsschritt:Mit der Induktionsannahme und den trigonometrischen Additions- theoremen erhalten wir dann (cosx+isinx)k+1 = (cosx+isinx)k(cosx+isinx) = (coskx+isinkx)(cosx+isinx) = coskx·cosx-sinkx·sinx+isinkx·cosx+icoskx·sinx = cos(kx+x) +isin(kx+x) = cos((k+ 1)x) +isin((k+ 1)x)

Somit ist die Formel fürn=k+ 1bewiesen.

Beispiel 9

13 beispielsweise die BehauptungSn<12 -1n fürSn=11·2+12·3+···+1(n-1)·n. Dann funk- tioniert der Induktionsschritt vonn=kaufn=k+1. Jedoch ist der Induktionsanfang S

1=11·2<12

-11 offensichtlich falsch.

Literatur

[1] sophischen begriffe" von rudolf eisler edition, 2004. [2] Florian Mo dlerand Martin Kreh. Tutorium Analysis 1 und Lineare Algebra 1: Ma-

Berlin [u.a.], 3. aufl edition, 2014.

[3] furt, M., 2. aufl edition, 2011.12

Entnommen aus [3, S. 19].

13Entnommen aus [3, S. 13].

8quotesdbs_dbs26.pdfusesText_32

[PDF] bewell connect bw-px10

[PDF] Bewerberinnen und Bewerber aus Niedersachsen zur Europawahl

[PDF] bewerbung - Be.Ma.Data

[PDF] Bewerbung - NRW-Justiz: Startseite

[PDF] Bewerbung - Volontariat - Via medici online

[PDF] Bewerbung als AuPair Formulaire de demande d´un séjour AuPair - Téléphones

[PDF] Bewerbung als Mitarbeiter/in Botschaftsschutz

[PDF] Bewerbung als Polizeiaspirantin / Polizeiaspirant Postulation en tant - Téléphones

[PDF] Bewerbung als Tutor/in im Institut für Mathematik mit Personalien

[PDF] Bewerbung der Stadt Aulendorf für den Titel “FairtradeStadt” im

[PDF] Bewerbung Fachkraft für Lagerlogistik

[PDF] Bewerbung für BWL mit 180 CP

[PDF] Bewerbung für den Bundesfreiwilligendienst - DLRG Schacht

[PDF] Bewerbung für die - John F. Kennedy School Berlin

[PDF] Bewerbung für eine BWL