Bewijsoefeningen
Opgave
Geef een informeel bewijs van het volgende theorema (uit tentamen 2003):
- sqrt(2) is een rationeel getal
Je mag is je bewijs gebruik maken van de volgende feiten:
- (a) [sqrt(n)]2 = n
- (b) Elk rationeel getal n kan geschreven worden als p/q, waar p en q gehele getallen zijn (dus, waar p en q elementen zijn van de verzameling {...,-3,-2,-1,0,1,2,3,...}) die geen gemene delere hebben, en waar q≠0
- (c) Twee gehele getallen p en q die geen gemene deler hebben kunnen niet allebei even zijn - anders zou 2 immers een gemene deler zijn.
- (d) Voor elk geheel getal n is 2n even.
- (e) Voor elk geheel getal n, als n2 even is, dan is n even.
- (f) Voor elk geheel getal n, als n even is, dan n=2r voor een geheel getal r.
(Hint: n=p/q ⇒ n2=p2/q2)
Welke bewijsmethode heb je gebruikt om het bovenstaande theorema te bewijzen? Rechtvaardig het gebruik van deze bewijsmethode door de formele structuur van deze bewijsmethode te geven.
Antwoord
Het informele bewijs volgt, ingebed in de formele structuur van reductio ad absurdum. Gekleurde regels zijn deel van de formele bewijsstructuur.
1. | sqrt(2) is rationeel | (AD) |
2. | sqrt(2) = p/q | (1; b) |
3. | [sqrt(2)]2 = p2/q2 | (2; hint) |
4. | 2 = p2 / q2 | (3; a) |
5. | p2 = 2 q2 | (4) |
6. | p2 is even | (5) |
7. | p is even | (6; e) |
8. | p = 2 r | (6; f) |
9. | (2r)2 = 2 q2 | (8,5) |
10. | 2 r2 = q2 | (9) |
11. | q2 is even | (10; f) |
12. | q is even | (11; e) |
13. | p is even en q is even | (7,12; Conj) |
14. | p en q hebben een gemene deler | (13; c) |
15. | sqrt(2) is niet rationeel | (2,14; b) |
16. | sqrt(2) is rationeel → sqrt(2) is niet rationeel | (1,15;AD) |
17. | sqrt(2) is niet rationeel ∨ sqrt(2) is niet rationeel | (16; Impl) |
18. | sqrt(2) is niet rationeel | (17; Taut) |