Vad är egentligen skillnaden mellan proof by contradiction och proof by contrapositivity?

Ska men bevisa P-->Q med ett motsägelsebevis så antar man ~(P-->Q), inte ~Q-->P. I ett kontrapositivt bevis så skulle man inte anta ~Q-->~P utan bara ~Q och visa att ~P följer från det antagandet.

Russell skrev:

Ska men bevisa P-->Q med ett motsägelsebevis så antar man ~(P-->Q), inte ~Q-->P. I ett kontrapositivt bevis så skulle man inte anta ~Q-->~P utan bara ~Q och visa att ~P följer från det antagandet.

Ja, det har du rätt i. P-->icke Q ska nog påståendet vara

Jag brukar tänka att det finns tre huvudsakliga sätt att visa en implikation $P\Rightarrow Q$:

• Direkt bevis. Man antar $P$ för att sedan steg för steg resonera sig fram till att $Q$ följer.
• Kontrapositivt bevis. Man antar $\neg Q$ och visar att $\neg P$ följer (dvs. man visar implikationen $\neg Q\Rightarrow\neg P$).
• Motsägelsebevis. Man antar både $P$ och $\neg Q$ och visar att en motsägelse följer (dvs. man visar att $\neg(P\land\neg Q)$ gäller).

Några påpekanden om detta:

• Anledningen till att alla de här tre bevistyperna fungerar är att de tre utsagorna $P\Rightarrow Q$ respektive $\neg Q\Rightarrow \neg P$ respektive $\neg(P\land\neg Q)$ är logiskt ekvivalenta i bemärkelsen att de har identiska sanningstabeller*.
• Varje direkt bevis och varje kontrapositivt bevis skulle kunna formuleras om till ett motsägelsebevis. Om vi vet att vi kan härleda $Q$ från $P$, så kommer vi kunna härleda motsägelsen $Q\land\neg Q$ om vi även antar $\neg Q$ i början av beviset. Och om vi vet att vi kan härleda $\neg P$ från $\neg Q$ så kommer vi kunna härleda motsägelsen $P\land\neg P$ om vi även antar $P$ i början av beviset.
• Det omvända gäller inte. Om vi har ett motsägelsebevis så finns det inte nödvändigtvis något enkelt sätt att formulera om det till ett direkt bevis. Att anta både $P$ och $\neg Q$ är ju en starkare hypotes än att enbart anta $P$ eller att enbart anta $\neg Q$.
• Om man vill visa en implikation $P\Rightarrow Q$ så skulle man i princip kunna säga att det enklaste är att ha som rutin att alltid satsa på ett motsägelsebevis, dvs. att anta både $P$ och $\neg Q$ och sedan försöka härleda en motsägelse på ett eller annat sätt, eftersom det täcker in alla tre möjligheterna.
• Likväl föredrar de flesta matematiker att försöka hitta ett direkt eller kontrapositivt bevis, även om man redan har ett motsägelsebevis på plats. Det finns många skäl till detta, men ett av de tyngsta är att direkta och kontrapositiva bevis brukar leda till djupare matematiska insikter och fler användbara delresultat på vägen (som vi dessutom kan dubbelkolla mot vår intuition för att försäkra oss om att vi inte begår några misstag). Ett motsägelsebevis  å andra sidan bygger i grund och botten på att man har antagit något falskt, vilket innebär att man inte utan vidare kan lita på att att de delresultat som man visar på vägen mot motsägelsen är sanna. 

* Verifiera gärna detta genom att fylla i nedanstående sanningstabell:
      $\begin{array}{ccccc}\\\hline P & Q & \quad\quad P\!\Rightarrow\!Q\quad & \quad\neg Q\!\Rightarrow\!\neg P\quad & \quad\neg (P\land\neg Q) \\\hline \mathrm{T} & \mathrm{T}\\ \mathrm{T} & \mathrm{F}\\ \mathrm{F} & \mathrm{T}\\ \mathrm{F} & \mathrm{F}\end{array}$

Sidenote: Här är en väldigt bra liknelse från ett inlägg på Math Stackexchange som jag tycker fångar väl varför folk i allmänhet föredrar direkta och kontrapositiva bevis framför motsägelsebevis!

Det finns också djupare logikskillnader, i motsägelsebevis så vill man visa ett påstående X, antar icke X och visar att det är falskt. Då har vi att icke X inte kan vara sant. Och tack vare lagen om uteslutna tredje så måste då X vara sant (i princip ickeickeP=P). Man kan göra logik utan lagen om den uteslutna tredje (såkallad intuitiv logik), och då fungerar inte motsägelsebevis (men en del andra bevis är fortfarande ok).

Så ur den synvinkeln så är bevis som inte använder motsägelse "bättre" än motsägelsebevis (eftersom de fungerar i en vidare logik).

Ofta är motsägelsebevis mer av existenssatser (någonstans finns en lösning till alla tredjegradare, men vi vet inte vilken den är) medan direkta bevis säger mer (vi vet att det finns en lösning eftersom vi har en formel för den).