WINAK

Ik opende mijn terminal nog eens en ik kreeg dit bewijs voorgeschoteld door fortune:

• Theorem: All positive integers are equal.
• Proof:
  Sufficient to show that for any two positive integers, A and B, A = B. Further, it is sufficient to show that for all N > 0, if A and B (positive integers) satisfy (MAX(A, B) = N) then A = B.
  
  Proceed by induction: If N = 1, then A and B, being positive integers, must both be 1. So A = B.
  
  Assume that the theorem is true for some value k. Take A and B with MAX(A, B) = k+1. Then MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1). Consequently, A = B.

Robbe wrote:... MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1).

Deze gevolgtrekking klopt niet. Kan enkel als MAX gedefinieerd zou zijn als EQUAL. Maar dan zoudt ge aan het bewijzen zijn dat elk getal gelijk is aan zichzelf.

Of zoiets...

is idd een nogal foutieve gevolgtrekking, nice try though

Foundation wrote:

Robbe wrote:... MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1).

Deze gevolgtrekking klopt niet. Kan enkel als MAX gedefinieerd zou zijn als EQUAL. Maar dan zoudt ge aan het bewijzen zijn dat elk getal gelijk is aan zichzelf.

Of zoiets...

Het zit iets subtieler in elkaar, we hadden namelijk voor k al bewezen dat als MAX(A, B) = k dat A = B.
Nu zeggen we:
MAX(A, B) = k + 1 <=> MAX(A-1, B-1) = k => A-1 = B-1
(Want MAX(A, B)-1 = MAX(A-1, B-1) )

Maar het is natuurlijk niet omdat A en B positieve getallen zijn dat A-1 en B-1 positieve getallen zijn, dat is de eerste reden dat het misgaat. De andere (verwante) reden is makkelijk te illustreren:
MAX(3, 5) = 5
MAX(2, 4) = 4
MAX(1, 3) = 3
MAX(0, 2) = 2
MAX(-1, 1) = 1
Kortom, het basisgeval MAX(1, 1) = 1 wordt nooit bereikt.

Ik was eerder aan het denken aan een foutief gebruik van inductie. Er is namelijk een basisgeval te weinig: N=2.

Robbe wrote:Ik was eerder aan het denken aan een foutief gebruik van inductie. Er is namelijk een basisgeval te weinig: N=2.

Misschien een domme vraag hoor, maar waarom zoudt ge twee basisgevallen nodig hebben?

omdat 1 basisgeval niet alles dekt? neem bijvoorbeeld het optellen van alle even of oneven getallen. Je trekt van het gegeven getal 2 af en telt dat bij het totaal. Je kan zo op 1 of op 0 komen, hence 2 basisgevallen

Of zoals de Van Steen het al wel eens heeft aangehaald: als 1 vrouw blond is, zijn alle vrouwen blond. Neem een groep van 1 vrouw, dan zijn ze allemaal blond. Neem nu een populatie van n vrouwen, en neem daar een groep van n-1 vrouwen uit. Als 1 vrouw hiervan blond is, dan zijn ze allemaal blond. Neem een andere groep uit dezelfde populatie, nu met de vrouw die je daarnet niet had. Omdat n-2 vrouwen uit die groep al blond zijn, is die ene vrouw die we er net bij hebben genomen ook blond. Hier zijn we dus het basisgeval van een populatie van 2 vrouwen vergeten.

Get my point?

tstaat gewoon vol fouten Da van joeri vink wel mooi uitgelegd.

Shinta wrote:tstaat gewoon vol fouten Da van joeri vink wel mooi uitgelegd.

Idd, kben zelf te lui om het uit te werken :p
En een tegenvoorbeeldje is genoeg om de foutiviteit van de stelling aan te tonen.

Robbe wrote:Further, it is sufficient to show that for all N > 0, if A and B (positive integers) satisfy (MAX(A, B) = N) then A = B.

Dit klopt niet of is fout geformuleerd.

Robbe wrote:Assume that the theorem is true for some value k. Take A and B with MAX(A, B) = k+1. Then MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1). Consequently, A = B.
[/list]

Dit klopt eveneens niet. Als B=1 (dit kan) dan B-1 = 0 (hier verlaat je de ruimte waarover je werkt en bijgevolg heb je geen eis gesteld hierop.)