Wiskundige bewijsmethoden

Hier volgt een overzicht van wiskundige bewijsmethoden. Voor het tentamen moet je de formele structuur kennen. In de wiskunde is het goed het volgende in het hoofd te houden:

• Px wordt geschreven als P(x)
• UG en UC worden zelden expliciet gebruikt, dus P(a), ..., P(a)→Q(a) ipv ∀x[P(x)], ..., P(a), ..., P(a)→Q(a), ∀x[P(x)→Q(x)].
• met "stel dat P waar is" wordt bedoeld "we voegen P toe aan de premissen".

Verder maken we gebruik van de volgende termen: achtergrondkennis (=axioma's en reeds bewezen theorema's), formeel en informeel. Een formeel bewijs wordt steeds gegeven. Een informeel bewijs zou niet de axioma's en theorema's bevatten, en eindigen bij de propositie waarachter een sterretje (*) staat.

Directe bewijzen - standaard

Propositie

• De propositie Pi achtergrondkennis is

• (P0&P1&...&Pi-1) => Pi

Implicatie

• De propositie Pi achtergrondkennis is

• (P0&P1&...&Pi-1) => Pi

Directe bewijzen - variaties

Contrapositief

Gebaseerd op de logische equivalentie p→q =_δf ¬q→¬p (Trans).

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 n+m+1. ¬Q      (AD)
 :
 r.     ¬P
 r+1.   ¬Q→¬P  ((n+m+1-r;AD) *
 r+2.   P→Q    (r+1; Trans)

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 n+m+1. ¬Q(a)          (AD)
 :
 r.     ¬P(a)
 r+1.   ¬Q(a)→¬P(a)   ((n+m+1-r;AD) *
 r+2.   P(a)→Q(a)     (r+1; Trans)
 r+3.   ∀x[P(x)→Q(x)] (r+2; UG)

Contradictie

Neem aan dat theorema onwaar is - laat zien dat dit tot onware consequenties (meestal een contradictie P&¬P) leidt - dus is theorema waar.

Gebaseerd op de logische equivalentie ¬p→p ≡ ¬¬p∨p ≡ p∨p ≡ p (Impl, DN en Taut).

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 n+m+1. ¬T       (AD)
 :
 r.     R
 :
 s.     ¬R       *
 s+1.   R∨T      (r; Add)
 s+2.   T        (s,s+1; DS)
 s+3.   ¬T→T    ((n+m+1)-(s+2); AD)
 s+4.   ¬¬T∨T    (s+3; Impl)
 s+5.   T∨T      (s+4; DN)
 s+6.   T        (s+5; Taut)

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 n+m+1. ¬T(a)       (AD)
 :
 r.     R
 :
 s.     ¬R          *
 s+1.   R∨T(a)      (r; Add)
 s+2.   T(a)        (s,s+1; DS)
 s+3.   ¬T(a)→T(a) ((n+m+1)-(s+2); AD)
 s+4.   ¬¬T(a)∨T(a) (s+3; Impl)
 s+5.   T(a)∨T(a)   (s+4; DN)
 s+6.   T(a)        (s+5; Taut)
 s+7.   ∀x[T(x)]    (s+6; UG)

G.H. Hardy (1877-1947):

[This method of proof is] one of a mathematician's finest weapons. [...] It is a far finer gambit that any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but the mathematician offers the game.

Equivalentie

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 :
 r.     P→Q
 :
 s.     Q→P
 s+1.   (P→Q)&(Q→P) (r,s; Conj)
 s+2.   P↔Q         (s+1; Equiv)

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 :
 r.     P(a)→Q(a)
 :
 s.     Q(a)→P(a)
 s+1.   (P(a)→Q(a))&(Q(a)→P(a)) (r,s; Conj)
 s+2.   P(a)↔Q(a)               (s+1; Equiv)
 s+3.   ∀x[P(x)↔Q(x)]           (s+2; UG)

In informele bewijzen wordt <=>, => en <= gebruikt. Dit is geen probleem, want XXX afmaken.

Existentiebewijzen

• Sommige priemgetallen hebben de vorm 32n+1, waar n een geheel getal is.
• Er zijn niet-abelische groepen.
• Niet alle gehele getallen zijn groter dan 0.

Voldoende om te bewijzen dat er 1 zulk object bestaat.

Constructief

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 :
 r.     P(a)
 r+1.   ∃x[P(x)]  (r; EG)

Niet constructief

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 n+m+1. ∃x(¬P(x))    (AD)
 n+m+2. ¬P(a)        (UC)
 :
 r.     Q
 :
 s.     ¬Q
 s+1.   ¬∀x[¬P(x)]   ((n+m+1)-s; Contradictie)
 s+2.   ¬¬∃x[P(x)]   (s+1; KN)
 s+3.   ∃x[P(x)]     (s+2; DN)

(regel n+m+1: want ¬∃x[P(x)] ≡ ∀x[¬P(x)].)

De details van het contradictiebewijs zijn weggelaten. Vul ze zelf in! (zie eerder deze pagina)

Tegenvoorbeeld(en)

• Fermat, 1640: "Voor alle niet negatieve gehele getallen n, het gehele getal F_n=2^{2^n}+1 is een priemgetal."
• Euler, 1732: "F_s = 4294967297 = 641*6700417 - niet priem."

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 :
 r.     ¬P(a)    } specifieke a in domein
 r+1.   ∃x[¬P(x)]     (r; EG)
 r+2.   ¬∀x[P(x)]     (r+1; KN)  } wel een theorema!

Wat moet je nu doen in de praktijk, bewijzen of een tegenvoorbeeld zoeken? Ervaring, instinct, intuitie, etc.

Probeer altijd zo simpel mogelijke tegenvoorbeelden te vinden, dat is duidelijker en vaak informatiever.

Het is mogelijk dat er geen bewijs of tegenvoorbeeld gevonden kan worden! (zie Brown) Dus ∀x[P(x)] kan niet bewezen worden van de axioma's en ¬∀x[P(x)] kan niet bewezen worden van de axioma's. We zeggen dan dat ∀x[P(x)] onbeslisbaar is van de axioma's. Een voorbeeld is de Continuum hypothesis. Het is mogelijk dat zulke proposities wel op niet formele wijze bewezen kunnen worden dmv. methodes die niet in het systeem geformaliseerd kunnen worden.

Uniciteitsbewijzen

1. Het bewijzen dat er een object met bepaalde eigenschappen bestaat (existentiebewijs).
2. Het bewijzen dat er slechts 1 zo'n object bestaat.

 1.     A1  }
 :          } Axioma's
 n.     An  }
 n+1.   T1  ))
 :          )) Theorema's
 n+m.   Tm  ))
 n+m+1. P(a)&P(b)                  (AD)  } a en b arbitrair in domein
 :
 r.     a = b
 r+1.   (P(a)&P(b) → (a=b)        ((n+m+1)-r; AD)
 r+2.   ∀x∀y[(P(x)&P(y)) → (x=y)] (r+1; UG)

Andere bewijzen

De speciale theorema's die wij zullen behandelen hebben de vorm ∀x[P(x)→Q(x)]. De te bewijzen theorema's zullen de vorm ∀x[Q(x)] hebben.

Domeinen kiezen kan hier lastig zijn. Het universum van verzamelingen is vaak een goede keuze daar wiskundige problemen neergeschreven kunnen worden in de taal van de verzamelingenleer.

XXX to be continued ...