matematikk.net

Hallois, jeg får ikke til dette her:




Er ikke vanligvis max(x,y) lik den største av x og y?

Morsom oppgave.

Problemet er muligens at hvis x = 1, så er ikke x-1 et positivt heltall. Samme for y = 1.

Poenget er vel at hele "teoremet" de forsøker bevise er feil, f.eks.: om den største av 2 og 3 er 3, så er ikke 2=3...

Dvs. hvis k=2, kan x og y være enten (2,2) eller (1,2).

Hvis k=3, kan x og y være (1,3), (2,3) eller (3,3).

osv.

Altså feil i steg 2...

Tenker jeg i hvert fall...

Ja, påstanden/teoremet er absurd nettopp på grunn av det du nevner, men det er vel å finne hvor "beviset" feiler som er poenget med oppgaven. Hvis beviset hadde vært helt riktig så måtte man jo akseptert påstanden . (Som JoddEHaa påpeker så fungerer ikke dette når x = 1 og y = 1.)

Absurd er vel stikkordet

Takk for hjelpen, da ble svaret slik:



Eller bør jeg endre formulering i siste avsnitt?

Teorem: P(k) = [max(x,y) = k <==> x = y] for alle k. (x,y,k naturlige tall.)

Stemmer for P(k = 1) = [max(x,y) = 1 <==> x = 1 og y = 1] = sant.

Induksjonssteget: Gitt P(k) = sann, bevis P(k+1). Det er her det bryter sammen. For hvis P(k+1) = sann, så får vi en logisk selvmotsigelse:

Av P(k) har vi max(p,q) = k med p = q. Ser nå på P(k+1). Vi har at k+1 = max(p+1, q) ==> p+1 = q, hvis P(k+1) er sann. Dette er en selvmotsigelse siden vi ikke kan ha p = q og p+1 = q samtidig. Ergo kan ikke både P(k) og P(k+1) være sanne, så beviset bryter sammen. (Siden hele "poenget" med induksjonsbevis er at P(k) ==> P(k+1).)

Det var bra forklart, lurt med slike boolske variabler.