Principis de demostració: directa, contraposició, contradicció i inducció

⏱ 7 min de lecturaUniversitat

Vols practicar? Aquest tema té 109 exercicis interactius de 3 tipus, de deu en deu, amb correcció immediata i explicació pas a pas.

A batxillerat es calcula; a la universitat es demostra. El canvi costa perquè ningú no sol explicar què compta com a demostració i què no. Aquesta pàgina és aquesta explicació: quins mètodes hi ha, quan toca cadascun, i quines coses semblen arguments però no ho són.

Es pot llegir abans que la resta del bloc, perquè tot el que hi ha aquí es fa servir als altres temes.

Prova directa

Parteixes de les hipòtesis i apliques definicions i resultats coneguts fins a arribar a la conclusió. Dues regles de redacció que valen molts punts:

Les hipòtesis no es demostren, s'assumeixen. En una implicació, suposar l'antecedent és el que has de fer, no una trampa.
Tot objecte auxiliar s'ha de declarar i justificar. Si dius «sigui $r$ tal que...», has d'haver explicat per què existeix.

El producte de dos senars és senar

Siguin $a$ i $b$ senars. Per definició existeixen enters $r$ i $s$ amb $a = 2r+1$ i $b = 2s+1$ . Aleshores

ab = (2r+1)(2s+1) = 4rs + 2r + 2s + 1 = 2(2rs + r + s) + 1,

que és de la forma «parell més u», és a dir senar.

Dos detalls de qualitat. Primer, l'argument cobreix tots els enters senars, inclosos els negatius, perquè $r$ i $s$ poden ser negatius. Segon, no s'ha comprovat cap cas particular: s'ha treballat amb senars arbitraris, i això és el que fa que la conclusió sigui universal.

Contraposició

Per demostrar que $P$ implica $Q$ , pots demostrar que la negació de $Q$ implica la negació de $P$ . Les dues afirmacions són lògicament equivalents, com veus a la taula de veritat, de manera que no és cap truc: és la mateixa proposició escrita d'una altra manera.

Serveix quan la negació de la conclusió és més manejable que la hipòtesi. L'exemple estàndard: per demostrar que si $n^{2}$ és parell aleshores $n$ és parell, la prova directa és incòmoda (de $n^2 = 2k$ no se'n treu res fàcilment), però la contraposada és immediata: si $n$ és senar, pel resultat anterior $n^{2}$ és senar.

Contradicció

Assumeixes les hipòtesis i la negació de la conclusió, i en dedueixes una impossibilitat. És potent però s'abusa: si la teva prova per contradicció no fa servir mai la hipòtesi negada, en realitat tenies una prova directa i queda més clara escrita així.

L'arrel de dos no és racional

Suposem que ho fos. Aleshores es podria escriure com un quocient $p/q$ amb $p$ i $q$ enters coprimers i $q$ no nul. Elevant al quadrat,

p^{2} = 2q^{2},

de manera que $p^{2}$ és parell i, pel resultat de la contraposició, $p$ també ho és. Posant $p = 2r$ i substituint surt $4r^{2} = 2q^{2}$ , és a dir $q^{2} = 2r^{2}$ , i pel mateix argument $q$ és parell.

Però llavors $p$ i $q$ tenen el factor $2$ en comú, cosa que contradiu que fossin coprimers.

El pas que no es pot ometre. Triar la fracció irreductible no és una comoditat: és la part de l'argument que genera la contradicció. Sense aquesta hipòtesi, que $p$ i $q$ siguin parells no té res d'impossible. Tota prova per contradicció necessita identificar amb precisió quina afirmació queda violada.

Inducció

Per demostrar una propietat per a tot $n$ a partir d'un valor inicial, cal el cas base i el pas inductiu, que consisteix a provar que la propietat per a un $n$ arbitrari implica la propietat per a $n+1$ .

La hipòtesi d'inducció no és suposar el que vols demostrar

Aquesta objecció és molt comuna i és infundada. No estàs suposant que la propietat val per a tot $n$ : estàs suposant que val per a un valor concret i demostrant que llavors val per al següent. Combinat amb el cas base, això encadena tots els valors.

L'error real que sí que es comet és ometre el cas base. Sense ell, la cadena no arrenca i es poden «demostrar» coses falses: el pas inductiu sol de «tots els cavalls són del mateix color» és correcte a partir de dos cavalls; el que falla és la base.

La suma dels n primers enters

Demostrem que la suma de $1$ fins a $n$ val $n(n+1)/2$ .

Cas base. Amb $n = 1$ , el membre esquerre és $1$ i el dret és $1\cdot 2/2 = 1$ . Coincideixen.

Pas inductiu. Suposem que val per a un $n$ concret. Aleshores per a $n+1$ :

\left(1 + \cdots + n\right) + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2} + 1\right) = \frac{(n+1)(n+2)}{2},

que és exactament la fórmula amb $n+1$ al lloc de $n$ .

Com que el cas base val i el pas es pot repetir indefinidament, la fórmula val per a tot $n\geq 1$ .

On es fa servir la hipòtesi. A la primera igualtat, i només allà. Si en una prova per inducció no saps assenyalar el punt exacte on has aplicat la hipòtesi, probablement no l'has feta servir i l'argument no és inductiu.

La inducció forta permet assumir la propietat per a tots els valors anteriors, no només l'immediatament previ. És el que cal quan la descomposició del cas $n+1$ et porta a valors que no són consecutius. L'exemple canònic: tot enter a partir de $2$ és producte de primers, perquè o bé és primer, o bé es descompon en dos factors estrictament menors als quals s'aplica la hipòtesi forta.

Existència, unicitat i contraexemples

Una existència es demostra construint un testimoni explícit, aplicant un teorema amb totes les hipòtesis comprovades, o amb un argument indirecte. Per a la unicitat, se suposen dues solucions i es prova que coincideixen: trobar-ne una no demostra mai que sigui l'única.

Per refutar una afirmació universal n'hi ha prou amb un contraexemple que compleixi les hipòtesis i incompleixi la conclusió. Però el recíproc no val: cent exemples favorables no demostren res. El polinomi $n^{2}+n+41$ dona primers per a tots els valors de $0$ a $39$ i falla a $40$ .

Llista de comprovació abans d'entregar una demostració

Has fet servir totes les hipòtesis? Si en sobra una, o la prova és incompleta o el teorema és més fort del que diu.
Una prova per casos cobreix tot el domini? Els casos han de ser exhaustius.
Has dividit per alguna cosa que podria ser zero? És l'error silenciós més car.
Per a una equivalència, has fet els dos sentits? Només et pots estalviar un si tots els passos són explícitament reversibles.
Per a una inducció, hi ha cas base i has assenyalat on s'aplica la hipòtesi?

Exercici resolt: divisibilitat per 6

Demostra que $n^{3}-n$ és divisible per $6$ per a tot enter $n$ .

Factoritzem primer, que sempre és més barat que induir:

n^{3}-n = n(n^{2}-1) = (n-1)\,n\,(n+1).

És un producte de tres enters consecutius.

Divisible per 3. Entre tres consecutius n'hi ha exactament un que és múltiple de $3$ , perquè els residus mòdul $3$ recorren els tres valors possibles.

Divisible per 2. Entre tres consecutius n'hi ha almenys un de parell (de fet, un o dos).

Conclusió. El producte és divisible per $2$ i per $3$ , i com que són coprimers, ho és pel seu producte $6$ .

El pas que no es pot saltar. La coprimalitat és essencial: de ser divisible per $2$ i per $4$ no se'n dedueix ser divisible per $8$ . Sempre que ajuntis dues divisibilitats, comprova que els divisors no comparteixen factors.

Exercici resolt: on falla una inducció mal feta

Algú «demostra» que tots els elements d'un conjunt finit no buit de números són iguals, per inducció sobre la mida. On és l'error?

L'argument sol ser: per a mida $1$ és obvi. Per al pas, donat un conjunt de $n+1$ elements, en treus un i pels $n$ restants la hipòtesi diu que són iguals; en treus un altre i passa el mateix; per tant tots són iguals.

L'error és al pas de $n=1$ a $n=2$ . Amb dos elements, els dos subconjunts de mida $1$ que obtens no es toquen: no comparteixen cap element, i per tant no hi ha res que permeti enganxar les dues conclusions. L'argument necessita que els subconjunts s'encavalquin, cosa que només passa a partir de tres elements.

La lliçó general. El pas inductiu ha de valer per a tot $n$ a partir de la base, sense excepcions. Un sol valor on l'argument no s'aplica trenca tota la cadena, per molt que funcioni per a tots els altres.

Ara prova-ho tu. 109 exercicis d'aquest tema, de 3 tipus diferents, per resoldre en línia, de deu en deu: escrius la resposta, te la corregeix a l'instant i, si falles, t'explica com es fa pas a pas. Quan acabis una tanda, en tens deu més, amb dades noves.

Fer els exercicis Simulacre d'examen