Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2017 / Logik und Diskrete Strukturen / Material / K01 Beweise


Inhaltsbereich

K01 Beweise

1. Teil der Vorlesungsnotizen zum Thema "Beweise"

Plain Text icon K01_Beweise.txt — Plain Text, 19 KB (19989 bytes)

Dateiinhalt

Vorwort:

Vorlesung hat 2 Teile:
 I  Diskrete Strukturen, folgt Buch "Diskrete Strukturen" von A.Steger
  - 0.1-4:     Beweise, Mengen, Relationen, Abbildungen 
  - 1.4:       Ordnungen, Verbände
  - 3.1-3:     Primzahlen, Modulare Arithmetik, Polynome
  - 5.1,5.3-4: Algebraische Strukturen, Gruppen, endliche Körper
  
 II Logik
  - Aussagenlogik   (Sequenzenkalkül & Resolution)    
  - Prädikatenlogik (Sequenzenkalkül & Resolution)


Vorlesungshomepage: https://www.tcs.ifi.lmu.de/lehre/ss-2017/lds
siehe dort Hinweise zum Übungsbetrieb, Klausurbonus, etc.



Junktoren
=========

Gegeben sei eine Menge A von mathematischen Aussagen A,B,C,D,...
Mathematische Aussagen werden durch die aussagenlogischen Junktoren zu
neuen Aussagen verbunden:

  ¬ Negation
  ∧ Konjunktion   ("und")
  ∨ Disjunktion   ("oder")
  ⇒ Implikation   ("wenn dann")
  ⇔ Biimplikation ("genau dann wenn")
  
Die Biimplikation versteht sich als Abkürzung für (A⇒B) ∧ (B⇒A)

Wer möchte, kann diese Formel auch ohne Klammern durch 
einen Syntaxbaum darstellen, dessen Blätter mathematische Aussagen sind:
        ∧
      /   \
     ⇒     ⇒ 
    / \   / \ 
    A B   B A
    
Um Klammern zu sparen gibt die Bindekraft der wie folgt vor:
  ¬, ∧, ∨, ⇒, ⇔ (¬ bindet am stärksten, ⇔ am schwächsten). 
Mehrere gleiche Junktoren ∧ oder ∨ werden nach links geklammert;
mehrerer gleiche Junktoren ⇒ oder ⇔ werden nach rechts geklammert.

Beispiel:
Daraus folgt, dass man z.B. die Formel
  (A∧B)v((C⇒D)∨(¬A))
auch einfach als 
   A∧B v (C⇒D)∨ ¬A
hinschreiben kann. 
Als Syntaxbaum:
      ∨
    /   \ 
   ∧     ∧
  / \   / \
  A B   ⇒  ¬
       / \ |
       C D A       
       
Umgekehrt liest man z.B. A⇒B⇒C⇒D als A⇒(B⇒(C⇒D)).
       
       
       
Beweise
=======

Während eines Beweises hat man immer einige Annahmen, die man
verwenden darf. Zu den Annahmen gehören natürlich die allgemein
bekannten und gelernten Sätze, aber auch lokale Annahmen, die erst im
Verlaufe des Beweises entstehen und auch wieder verschwinden. Es
besteht eine gewisse Analogie zu Funktions- und Prozedurparametern,
sowie lokalen Programmvariablen.


Beweisregeln für durch Junktoren verbundene Aussagen
-----------------------------------------------------


Konjunktion ("und")
-------------------

Ein Beweis von A ∧ B besteht aus einem Beweis für A und einem für B: 

Schema:
  Zeige A∧B
  Wir zeigen zunächst A.
    ⋮                   /* Eingerückt: Beweis für A */
  Nun zeigen wir B.
    ⋮                   /* Eingerückt: Beweis für B */
  Es gilt A∧B.


Disjunktion ("oder")
--------------------

Ein Beweis von A ∨ B besteht aus einem Beweis für A oder einem Beweis für B.

Schema:
  Zeige A∨B.
  Wir zeigen A.
    ⋮               /* Eingerückt: Beweis für A */
  Es gilt A∨B.
  
Alternativ: 

  Zeige A∨B.
  Wir zeigen B.
    ⋮               /* Eingerückt: Beweis für B */
  Es gilt A∨B.


Implikation ("wenn dann")
-------------------------

Ein Beweis von A⇒B besteht aus einem Beweis für B, wobei A als
Annahme benutzt werden kann.

Schema:
  Zeige A⇒B.
  Wir nehmen A an (H).
    Zeige B.
      ⋮      /* Eingerückt: Beweis für B, darf H verwenden */
  Es gilt A⇒B.                  

Hier ist (H) ein Marker für die gemachte Annahme (Hypothese). 
Man kann dann später darauf zugreifen.

Hat man eine Aussage A als Annahme und muss gerade genau diese zeigen,
dann kann man einfach sagen, dass das zu Zeigende mit der Annahme
folgt.

Durch Einrückung zeigen wir immer an, wie weit sich eine Annahme erstreckt. Manchmal auch um Teilabschnitte des Beweises zu hervorzuheben (wie z.B. die beiden Abschnitte bei dem Beweis einer Konjunktion).
Es gilt: 
 - Nächste Zeile beginnt weiter rechts:      
        neuer Unter-Abschnitt beginnt
 - Nächste Zeile beginnt in gleicher Spalte: 
        weiterer gleichartiger Abschnitt beginnt
 - Nächste Zeile beginnt weiter links:       
        vorher unterbrochener Abschnitt geht nun wieder weiter
 
Beispiel:
01  Zeige A∧B.
02  Wir zeigen A:
03    Abschnitt Beweis für A
04  Wir zeigen B:  
05    Abschnitt Beweis für B
  
 
Beispiel: Sei A eine beliebige Aussage. Man beweise A ⇒ A ∧ A
01  Zeige A ⇒ A ∧ A
02  Wir nehmen A an (H).
03   Zeige A ∧ A.
04     Wir zeigen zunächst (das erste) A.
05       Das gilt aber nach Annahme (H)
06     Nun zeigen wir (das zweite) A.
07       Das gilt ebenso nach Annahme (H).


Beispiel: Seien A,B beliebige Aussagen. Man beweise A ⇒ A ∨ B

Zeige A ⇒ A ∨ B
Wir nehmen A an (H).
  Zeige A ∨ B
    Wir zeigen A.
    Das ist aber Annahme (H)


Negation ("nicht")
------------------

Um eine Aussage der Form ¬A ("nicht-A") zu zeigen, nimmt man A an und
muss dann einen Widerspruch herleiten. Einen Widerspruch erhält man
immer dann, wenn man sowohl X, als auch ¬X für irgendeine Aussage
zeigen kann.

Schema:
  Zeige ¬A.
  Wir nehmen A an (H1). /* ein "¬" wird entfernt! */
    Zeige Widerspruch.
      ⋮
  Es gilt ¬A (H2). /* Ausgerückt: H1 gilt hier nicht mehr! */
       
Beispiel:
Zeige A ⇒ ¬¬A
Wir nehmen an A (H1).
  Zeige ¬¬A.
  Wir nehmen an ¬A (H2).
    Zeige Widerspruch.
    Aus H1 und H2 ergibt sich dieser.
□


Indirekter Beweis
-----------------

Anstatt eine beliebige Aussage A zu zeigen, kann man auch ¬¬A zeigen,
also versuchen, aus ¬A, der Annahme des Gegenteils, einen Widerspruch
herzuleiten. Das bezeichnet man als *indirekten Beweis*.

Beispiel: 

1 Zeige ¬¬A ⇒ A.
2 Wir nehmen an ¬¬A (H).
3   Zeige A.
4   Indirekter Beweis:
5   Wir nehmen an ¬A (H1).   /* "¬" hinzugefügt */
6     Zeige Widerspruch.
7     Aus H und H1 ergibt sich dieser.

Zeile 3-6 zeigen das Muster des indirekten Beweises:
Es ist A zu zeigen. Dies erreicht man, indem die 
Annahme von ¬A auf einen Widerspruch geführt wird.
Bemerke: Im Gegensatz zum Beweisschema für negierte Aussagen, wird hier also ein "¬" hinzugefügt in der Annahme.
           
    
Beispiel:
Zeige A ⇒ ¬A ⇒ B.  /* ex falso quodlibet */
Wir nehmen an A (H1) und ¬A (H2).
  Indirekter Beweis:
  Wir nehmen an ¬B (H3).
    Zeige Widerspruch.
    Aus H1 und H2 ergibt sich dieser. 
    
    
Zeige A ∧ ¬A ⇒ B. /* ex falso quodlibet */
Wir nehmen an A ∧ ¬A (H).
  Zeige B.
  Indirekter Beweis:
  Annahme ¬B.
    Zeige Widerspruch.
    Aus H folgt A  /* bzw. */  H.1 ist A
    H.2 ist ¬A.
    Widerspruch aus A und ¬A.


    
Verwendung von Annahmen mit Junktoren
=====================================


Verwendung einer Konjunktion
----------------------------

Hat man eine Annahme H der Form A ∧ B, so kann man neben A ∧ B
selbst auch A und B separat abrufen. Diese kann man als H.1 und H.2
bezeichnen.

Beispiel:

Zeige A∧B ⇒ B∧A   /* ∧ bindet stärker als ⇒ */
Wir nehmen an A∧B (H).
  Zeige B∧A.
  Wir zeigen zunächst B.
    Das ist H.2.
  Wir zeigen nun A.
    Das ist H.1.


Verwendung einer Disjunktion
----------------------------

Hat man eine Annahme der Form A∨B, so kann man das aktuell zu
Zeigende zweimal zeigen, einmal unter der zusätzlichen Annahme A und
dann noch einmal unter der Annahme B.

Beispiel:

Zeige (B∨C) ⇒ (A ⇒ A∧B ∨ A∧C)     /* Bindereihenfolge ¬,∧,∨,⇒ */
Wir nehmen an B∨C (H1).
  Zeige  (A ⇒ A∧B ∨ A∧C).
  Wir nehmen an A (H2).
    Zeige A∧B ∨ A∧C. 
    Für H1 ergeben sich zwei Fälle:
    1.Fall:  Wir nehmen an B (H3).
      Wir zeigen A∧B.
      Das ergibt sich aus H2 und H3.
    2.Fall: Wir nehmen an C (H4).  /* H2 ist nun nicht mehr gültig! */
      Wir zeigen A∧C.
      Das ergibt sich aus H2 und H4.
QED

Anmerkungen:
 * Verwendung einer Disjunktion A∨BvC∨D benötigt die Betrachtung von 4 Fällen:
   1.Fall:A, 2.Fall:B, 3.Fall:C, 4.Fall D
 * Der Beweis eines Falles ist auch dann beendet, wenn ein Widerspruch herleitbar 
   ist, denn dann kann dieser Fall einfach nicht eintreten. 
   Es muss aber mindestens einer der Fälle beweisbar sein!
  * Streng genommen müsste man A∨BvC∨D als ((A∨B)vC)∨D lesen und man hat also die 6 verschachtelten Fälle: 
  1=((A∨B)vC), 2=D, 1.1=A∨B, 1.2=C, 1.1.1=A, 1.1.2=B
  Letztendlich bleibt es also bei den Fällen A,B,C und D.


Verwendung einer Implikation
----------------------------

Hat man eine Annahme der Form A⇒B, so kann man zunächst einmal
A zeigen und darf dann wieder zum eigentlichen Ziel zurückkehren, diesmal
aber unter Einführung der Annahme B.

Schema: 
  ⋮
  Annahme A⇒B (H1) /* aus vorangegangenem Beweisteil */
  ⋮
  Verwende H1:
    Zunächst ist A zu zeigen.
    ⋮       /* Eingerückter Beweis von A*/
    Es gilt also A.
  Damit gilt auch B (H2).
  ⋮ /* H1 und H2 dürfen hier verwendet werden */

  
Beispiel:

Zeige (A⇒B) ⇒ (B⇒C) ⇒ A ⇒ C
Wir nehmen an A⇒B (H1) und B⇒C (H2) und A (H3).
  Zeige C.
  Wir verwenden dazu H2:
    Zunächst ist B zu zeigen. 
    Wir verwenden H1:
      Zunächst ist A zu zeigen.
      Das ergibt sich aus H3.
    Wir dürfen nunmehr B (H4) annehmen.
      Also ist B gezeigt (mit H4).
  Wir dürfen nunmehr C (H5) annehmen.
  Also ist C gezeigt (mit H5).
QED

Schnittregel: Man darf jederzeit eine Behauptung aufstellen, beweisen und dann benutzen.

Beispiel erneut mit Schnittregel:
Zeige (A⇒B)⇒(B⇒C)⇒(A⇒C)
Annahmen: 
A⇒B (H1)
B⇒C (H2)
A   (H3)
  Zeige C.
    Zeige zunächst B.
      Folgt aus (H1) und (H3).
    Annahme B (H5)
      C folgt nun aus (H2) und (H5).
  


Beispiel:

Zeige ((A⇒B)⇒A)⇒A /* Peirce'sche Formel */

Wir nehmen an (A⇒B)⇒A (H1).
  Zeige A.
  Indirekter Beweis: Wir nehmen an ¬A (H2).
    Zeige Widerspruch.
    Wir verwenden H1:
      Zunächst ist A⇒B zu zeigen.
      Wir nehmen an A (H3). 
        Indirekter Beweis: Wir nehmen an ¬B (H4).
          Zeige Widerspruch.
          Aus H2 und H3 ergibt sich dieser.
    Wir dürfen nunmehr A (H5) annehmen.
    Der gesuchte Widerspruch ergibt sich aus H2 und H5.
QED.


Verwendung einer Negation
-------------------------
Eine Negation verwendet man, um Widersprüche herzuleiten.


Beispiel Kontraposition:
01  Zeige (A⇒B)⇒(¬B⇒¬A)
02  Annahme A⇒B  (H1)
03  Annahme ¬B   (H2) 
04    Zeige ¬A.
05    Dazu nehmen wir nehmen A an (H3) 
06    und zeigen einen Widerspruch: 
07      Verwende H1.
08        Zeige A.
09        Folgt aus H3.
11      Wir dürfen nunmehr B (H4) annehmen.
12      Widerspruch aus H2,H4 
13    Damit gilt ¬A.
□  
  
Zeilen 01-04 folgen Schema für Beweise einer Implikation.
Zeilen 04-06 und 13 folgen Schema des Beweises einer negierten Aussage.
Zeilen 07-11 folgen Schema der Verwendung einer Implikation.
  
    
     

Schnittregel
============

Manchmal ist es auch sinnvoll, ein Zwischenergebnis "proaktiv"
herzuleiten, also nicht immer nur auf das aktuelle Ziel
hinzuarbeiten. Solch ein Zwischenergebnis kann dann benannt "(H)" und
im weiteren Verlauf wie eine Annahme verwendet werden. Man bezeichnet
die Anwendung dieses Prinzips als *Schnittregel*.

Schema:
  ⋮                /* vorangehender Teil des Beweises */
  Wir zeigen zunächst A:
    ⋮                    /* Eingerückter Beweis von A */
  Wir haben A gezeigt. (H)
  ⋮             /* Hier kann H jetzt verwendet werden */
    

Beispiel:

Zeige (A⇒B) ⇒ A ⇒ (B⇒C) ⇒ (C⇒D) ⇒ D.
Wir nehmen an A⇒B (H1), A (H2), C⇒C (H3), B⇒D (H4).
  Zeige D.
  Wir zeigen zunächst B:
    Das ergibt sich aus H1 und H2. 
  Wir haben also nunmehr B (H5).
    Aus H3 und H5 ergibt sich C.
  Wir haben also C (H6).
  Nun können wir H4 verwenden. 
    Wir haben bereits B. Also folgt D.
QED. 



Beispiel:

Zeige p,q in N teilerfremd ⇒ ¬((p/q)²=2)
Annahme p,q in N teilerfremd (H1)
  Indirekter Beweis: p²=2q² (H2)
    Zeige Widerspruch.
    Aus H1 ergibt sich 2|p (H3)
      Also 2²|p²
      Also 2²|2q²
      Also 2|q (H4)
      H3 und und H4 stehen im Widerspruch zu H1.

  
Spezialfall: Fallunterscheidung:

Wir zeigen zunächst für beliebige Aussage A die Aussage A ∨ ¬A 
(tertium non datur, Satz vom ausgeschlossenen Dritten)

Zeige A ∨ ¬A.
Indirekter Beweis: Annahme ¬(A ∨ ¬A) (H1)
Zeige Widerspruch.
  Schnittregel: wir zeigen zunächst A ∨ ¬A.
    Wir zeigen ¬A.
    Wir nehmen A (H2) an /* Beweisschema fur Negation */ 
      Zeige Widerspruch
        Aus H2 folgt mit Disjunktion: A ∨ ¬A (H3).
      Widerspruch aus H1 und H3.
    Damit gilt ¬A (H4)
  Aus H4 folgt mit Disjunktion: A ∨ ¬A (H5).
  /* Achtung: H3 gilt nur unter H2! H5 gilt dagegen direkt! */
  Widerspruch zwischen H5 und H1.
□
  

 
Nun kann man mit der Schnittregel jederzeit A ∨ ¬A annehmen und dann
darüber eine Fallunterscheidung machen, also das zu zeigende erst
unter Annahme A und dann noch einmal unter der Annahme ¬A zeigen.








Beispiel:

Zeige ¬(A ∧ B) ⇒ ¬A ∨ ¬B. (De Morgansches Gesetz).
Annahme ¬(A ∧ B) (H0).
  Zeige ¬A ∨ ¬B.
  Annahme A ∨ ¬A (H1) /* Zulässig wg Schnittregel */
  Verwende H1. /* Disjunktion durch Fallunterscheidung verwenden */
  Fall 1: Wir nehmen an A (H2).
    Annahme B ∨ ¬B (H3) /* Zulässig wg Schnittregel */
    Fall 1.1: Annahme B (H4).
      Widerspruch aus H4 und H0. /* Dieser Fall kann also nicht eintreten */
    Fall 1.2: Annahme ¬B (H5).
      Daraus ergibt sich ¬A ∨ ¬B.
  Fall 2: Wir nehmen an ¬A (H2).
    Daraus ergibt ich ¬A ∨ ¬B.
QED

In ähnlicher Weise zeigt man auch

A ∧ ¬(B ∨ C) ⇒ A ∧ ¬B ∨ A ∧ ¬C


     
Quantoren
=========

Eine Aussageform oder Prädikat ist eine Aussage, die einen oder
mehrere Parameter, auch Variablen, enthält und deren Wahrheitsgehalt
also von diesen abhängt. Zum Beispiel: "x ist gerade".

Aussageformen können mit den Quantoren ∀x∈M und ∃x∈M zu neuen
Aussagen und Aussageformen kombiniert werden.

Beispiel:

Ist n eine ungerade natürliche Zahl, dann ist auch n² ungerade.

In formaler Notation:

∀n∈ℕ. Ungerade(n) ⇒ Ungerade(n²)       /* Satz 0.5 */

Hier ist also Ungerade(n) eine Aussageform, die eben bezeichnen soll,
dass n ungerade ist.

Wir beachten, dass Satz 0.5 eine Aussage ist und keine Aussageform,
denn die Variable n ist durch den Allquantor *gebunden*. 
In einer Aussageform bezeichnet man einen ungebunden Parameter
auch als *frei*.

Wir beweisen jetzt Satz 0.5:

Sei n∈ℕ eine feste aber beliebige natürliche Zahl.
Wir nehmen an Ungerade(n) (H).
  Zeige Ungerade(n²).
  Wegen H können wir n in der Form n=2k+1 schreiben.
  Es ist nun n²=(2k+1)² = 2(2k²+2k)+1.
  Also gilt Ungerade(n²).
QED.


Wir haben hier folgende Beweisregel für den Allquantor benutzt:


Beweisregeln für den Allquantor
--------------------------------

Um zu zeigen, dass ∀x∈M.A(x) gilt, nimmt man einen festen aber
beliebigen Wert c∈M an und muss dann A(c) zeigen. Oft nennt man, wie
oben, den festen aber beliebigen Wert genauso wie die gebundene
Variable, hier x, man muss das aber nicht tun. Umbenennung empfiehlt
sich insbesondere dann, wenn schon ein anderer Wert dieses Namens in
Kraft ist.


Um eine Annahme der Form ∀x∈M.A(x) zu verwenden, darf man A(c) für
ein beliebiges, natürlich möglichst günstig gewähltes c∈M
verwenden.

Statt x∈M darf man auch einfach x schreiben, wenn der Bereich aus dem
Zusammenhang klar, oder unerheblich ist.

Dabei ist ∀x∈M.A(x) eine kurze Schreibweise für ∀x(x∈M⇒A(x)).
Der Punkt steht für eine sich öffnende Klammer, welche so spät wie syntaktisch möglich geschlossen wird. 

Hier ein allgemeines Beispiel:

Zeige (∀x.(A(x)∧B(x))) ⇒ (∀x.A(x)) ∧ (∀x.B(x))
Wir nehmen an ∀x.(A(x)∧B(x)) (H).
  Zeige (∀x.A(x)) ∧ (∀x.B(x)).
  Wir zeigen zunächst ∀x.A(x).
    Sei c fest aber beliebig.
    Zeige A(c).
    Aus H ergibt sich A(c)∧B(c) (H2).
      Das zu zeigende A(c) ist H2.1.
  Wir zeigen nun ∀x.B(x).
    Sei d fest aber beliebig.
    Zeige B(d).
    Aus H ergibt sich A(d)∧B(d) (H3).
      Das zu zeigende B(d) ist H3.2.
□
 
 
Beweisregeln für den Existenzquantor
-------------------------------------

Will man eine Aussage der Form ∃x∈M.A(x) zeigen, so muss man einen
geeigneten Wert c∈M (möglichst geschickt) wählen und dann A(c) zeigen.

Dabei ist ∃x∈M.A(x) eine kurze Schreibweise für ∃x(x∈M ∧ A(x)).

Beispiel:
Zeige ∃n.Ungerade(n).
  Wir wählen n=1:
  Zeige Ungerade(1).
  Es ist aber 1 = 2*0+1, also gilt Ungerade(1).

Hier haben wir "Expertenwissen" über das Prädikat "Ungerade"
einfließen lassen. Hier könnte man die Formalisierung noch 
etwas weiter treiben und definieren:

Ungerade(n) :<=> ∃k∈ℕ.n=2k+1

Hier steht ℕ für die Menge der natürlichen Zahlen.
Wir können nun den Satz 0.5 noch einmal beweisen, brauchen dafür aber noch
die Beweisregel für die Verwendung existenzquantifizierter Annahmen:

Will man eine Annahme der Form ∃x∈M.A(x) verwenden, so kann man
stattdessen eine Annahme der Form A(c), wobei c für einen festen aber
beliebigen Wert aus M steht. Man darf sich an dieser Stelle keinen
Wert aussuchen, sondern muss die Annahme eben so verwenden, dass der
Beweis für jeden Wert c, ganz gleich welchen, funktioniert.

Das Beispiel sollte dies illustrieren:

Zeige ∀n∈ℕ.Ungerade(n) ⇒ Ungerade(n²).
Sei n∈ℕ eine feste aber beliebige natürliche Zahl.
Zeige Ungerade(n) ⇒ Ungerade(n²).
Wir nehmen an Ungerade(n) (H).
  Zeige Ungerade(n²).
  Wir verwenden H                     /* H sagt ja ∃k∈ℕ.n=2k+1 */
  und nehmen daher an n=2k+1 (H1)     /* hier ist k fest aber beliebig */
    Es ist nun n²=(2k+1)² = 2(2k²+2k)+1.
    Wir schließen also ∃m∈ℕ.n²=2m+1  /* wobei m=2k+1 gewählt wurde */
    Das aber ist Ungerade(n²). 
QED.

An diesem Beispiel sehen wir auch eine weitere implizite Beweisregel.

Man darf jederzeit gleiches durch gleiches ersetzen (hier (2k+1)² =
2(2k²+2k)+1). Manchmal ergeben sich solche Gleichungen auch erst aus
dem Abrufen von Annahmen. 

Hier noch ein weiteres abstraktes Beispiel zum Existenzquantor:

Zeige (∃x∈M.A(x)∨C) ⇒ (∃x∈M.A(x)) ∨ C
Wir nehmen an ∃x∈M.A(x) ∨ C  (H).
  Zeige (∃x∈M.A(x)) ∨ C. 
  Sei c∈M fest aber beliebig gewählt.
  Unter Verwendung von H können wir also
  annehmen A(c) ∨ C  (H1).
    Wir verwenden H1:
    1.Fall: A(c) (H2).
        Wir zeigen ∃x∈M.A(x).
        Das aber folgt aus H2 mit x=c.
    2.Fall: C (H3).
        Wir zeigen C.
        Das aber ist gerade H3.


Komplizierteres Beispiel: sqrt(2) ist irrational
================================================

Satz: Die reelle Zahl sqrt(2) ist nicht rational, also nicht von der Form
p/q mit p und q aus ℕ und teilerfremd.
(geht auf Euklid zurück)

D.h. es gibt keine teilerfremden natürlichen Zahlen p,q mit sqrt(2)=p/q, bzw. 2=p²/q².

Zeige ¬∃p∈ℕ.∃q∈ℕ.(∀r∈ℕ.r|p ∧ r|q ⇒ r=1) ∧ p²=2*q².
Wir nehmen an
∃p∈ℕ.∃q∈ℕ.(∀r∈ℕ.r|p ∧ r|q ⇒ r=1) ∧ p² = 2 * q² (H)
Zeige Widerspruch.
  Wir fixieren f.a.b. p∈ℕ und q∈ℕ, so dass
  (∀r∈ℕ.r|p ∧ r|q ⇒ r=1) ∧ p² = 2 * q² (H1).
  Wegen H1.2 gilt 2|p² (H2).
  Da 2 eine Primzahl ist, gilt auch 2|p (H3).
  Also 4|p² (H4).
  Es folgt 2|q (H5).
  Aus H2.1 mit r=2 ergibt sich
  2|p ∧ 2|q ⇒ 2=1
  was mit H3 und H5 den gewünschten Widerspruch liefert. 
QED.

Hier wurde mit Gleichheit gearbeitet, z.B. wenn r|a und a=b, dann auch
r|q, und ausserdem einiges an Expertenwissen über die Teilbarkeit
verwendet, z.B.  2|ab ⇒ 2|a ∨ 2|b, weil 2 eine Primzahl ist. Wir
sehen hier, dass dieses Expertenwissen auch in Form logischer Aussagen
formuliert werden kann und es kann auch mit den hier beschriebenen
Methoden formal bewiesen werden. Allerdings braucht man gewisse
unbewiesene Grundannahmen, die Axiome, welche dann nicht mehr bewiesen
werden können. Diese sind erstaunlich einfach und wir werden auf ihre
Rolle später noch einmal zurückkommen.

Allerdings werden wir uns im Hauptteil dieses Kurses erlauben, aus
Schule und Vorlesung bekanntes Expertenwissen ohne weitere
Rechtfertigung in Beweisen zu verwenden, so wie hier geschehen.

Artikelaktionen


Funktionsleiste