1.12 Demostracions

Molts teoremes tenen la forma $A\Longrightarrow B$. El camí més senzill per provar $A\Longrightarrow B$ és fer-ho directament: suposem que $A$ és vertadera i hem d’arribar a deduïr $B$ mitjançant una seqüència de passos que comença en $A$ i acaba en $B$. Aquest tipus de prova es diu prova directa per distinguir-la d’altres mètodes de demostració.

Solució:  (1) Si $C(r)=$“$C$ és un cercle del pla de radi $r$” i $A(x)=$“ àrea de la figura $x$”, aleshores es té $\forall r\left(C(r)\longrightarrow A(C(r))=\pi r^{2}\right)$. De fet, si $r>0$, aleshores $C(r)=\left\{\left(x,y\right)\in\mathbb{R}^{2}:x^{2}+y^{2}=r^{2}\right\}\,$.

(2) Si $R(x)=$“és una recta del pla”, $P(x)=$“és un punt del pla” i $x\parallel y=$“x és paral·lel a y”, aleshores

(3) Si $T(x,y,z)=$“$T$ és un triangle del pla de costats $x,y,z$” i $A(x)=$“angle oposat al costat $x$ del triangle $T$”. Aleshores

De fet, $T(x,y,z)=\left\{(x,y,z)\in\mathbb{R}^{3}:x\leq y+z\right\}$.

(4) $\forall x,y\left(x,y\in\mathbb{R}\longrightarrow e^{x}\cdot e^{y}=e^{x+y}\right)$.   $\square$

Solució:  Primer observem que a l’enunciat hi apareix un predicat "$x$ divideix $y$", que simbolitzem per $x\mid y$. La seva definició és: $x\mid y$ sii (abreujatura de "si i només si") existeix $k\in\mathbb{Z}$ tal que $kx=y$. Ara hem d’escollir una estrategia per la prova. En aquest cas escollim la prova directa: suposem que $a\mid b$ i $b\mid c$ (hipotèsis) i tenim que veure que $a\mid c$ (tesi).

Si $a\mid b$ i $b\mid c$, llavors existeixen $k_{1},k_{2}\in\mathbb{Z}$ tals que $k_{1}a=b$ i $k_{2}b=c$. D’aquí, per substitució es té: $k_{2}\left(k_{1}a\right)=\left(k_{1}k_{2}\right)a=c$. Per tant, existeix $k=k_{1}k_{2}\in\mathbb{Z}$ tal que $ka=c$ i, com a conseqüència, $a\mid c$.   $\square$

Solució:  Primer observem que a l’enunciat hi apareixen dos conceptes: mitja aritmètica i geomètrica de dos nombres positius. La mitja aritmètica i geomètrica de $x$ i $y$ són respectivament: $\sqrt{xy}$ i $\dfrac{x+y}{2}$. Escollim una prova directa: com hipòtesi suposem $x,y\geq 0$, tenim que veure $\sqrt{xy}\leq\dfrac{x+y}{2}$ (tesi).

Si $x,y\geq 0$ aleshores $\sqrt{x}$ i $\sqrt{y}$ existeixen. És evident que $(\sqrt{x}-\sqrt{y})^{2}\geq 0$. Desemvolupant aquesta última expressió i passant l’arrel quadrada a l’altre costat de la desigualtat, es té

Finalment, dividind tots dos costats per $2$, es té el resultat que voliem:

$\square$

Un altre mètode de construir una demostració és treballant mentalment des de la tesi cap a les hipòtesis. Es diu prova pensada cap enrere per distingir-la de les demés. Tot i això, la prova finalment es construeix de forma directa. Mirem-ho construïnt la prova cap enrere de la següent proposició:

Solució:  L’hipòtesi és $x,y\in\mathbb{R}$ i $x<y$, i la tesi, $4xy<(x+y)^{2}$. La prova cap enrere surt de la tesi, i, per tant, podem fer es següent:

De la última desigüaltat, s’obté $x-y\neq 0$ i, per tant, $x\neq y$. En particular, $x<y$. De fet, això que hem escrit s’havia d’haver pensat mentalment perquè la demostració real és una prova directa: Si $x<y$, llavors $x\neq y$ i, per tant, $x-y\neq 0$. D’aquí, es té $(x-y)^{2}>0$ i, per tant, $x^{2}-2xy+y^{2}>0$. Sumant a tots dos costats $4xy$ es té: $x^{2}+2xy+y^{2}>4xy$ i, per tant, $(x+y)^{2}>4xy$, com voliem demostrar.   $\square$

Recordem que el contrarecíproc de $A\longrightarrow B$ és $\lnot B\longrightarrow\lnot A$, i també l’equivalència lògica $\left(A\longrightarrow B\right)\Longleftrightarrow\left(\lnot B\longrightarrow\lnot A\right)$, anomenada llei del contrarecíproc. Per això, si volem provar $A\longrightarrow B$, podem fer-ho de manera equivalent, construïnt una prova directa de $\lnot B\longrightarrow\lnot A$. L’estratègia és doncs pendre com hipòtesi que $B$ és falsa i hem d’arribar a que $A$ és també falsa (tesi). Aquest tipus de demostració es diu prova per contrarecíproc. Veiem-ho amb un exemple:

Solució:  Volem constuir una prova per contrarecíproc. Aleshores, les hipòtesis són que $n\in\mathbb{Z}$ i $n$ no és parell. La tesi és que $n^{2}$ no és parell. Si $n$ no és parell, $n$ és senar i, per tant, existeix $k\in\mathbb{Z}$ i $n=2k+1$. Hem de veure que $n^{2}$ també és senar. En efecte, com $n=2k+1$, aleshores $n^{2}=\left(2k+1\right)^{2}=4k^{2}+4k+1=2\left(2k^{2}+2k\right)+1$ i com $2k^{2}+2k\in\mathbb{Z}$, s’obté que $n^{2}$ és senar, com voliem demostrar.   $\square$

El principi del tercer exclòs permet afirmar que una proposició o es vertadera o bé falsa. Aquest principi és la base del següent mètode de demostració. En concret, si volem demostrar que una proposició $p$ és certa, aquest mètode proposar suposar el contrari, o sigui que $\lnot p$ és certa, i llavors per regles d’inferència hem d’arribar a una contradicció com per exemple $q\wedge\lnot q$, on $q$ és una proposició qualsevol, per poder concluir que la suposició que $A$ és falsa no és possible i, en conseqüència, $A$ és certa.

A matemàtiques els teoremes tenen la forma $A\longrightarrow B$ i, per tant, hem d’adaptar el raonament anterior a aquest cas. Recordem l’equivalència lògica $\lnot\left(A\longrightarrow B\right)\Longleftrightarrow A\wedge\lnot B$. Per tant, si volem construir una demostració de $A\longrightarrow B$, hem de suposar que $\lnot\left(A\longrightarrow B\right)$ és certa. Això és equivalent a suposar que $A\wedge\lnot B$ és certa, o sigui que $A$ és certa i $B$ és falsa i d’aquí hem de provar que s’arriba a una contradicció. Una vegada s’ha arribat a la contradicció, concluïm que $A\wedge\lnot B$ és falsa i, per tant, $A\longrightarrow B$ és vertadera.

Aquest mètode de demostració es coneix com a prova per reducció a l’absurd. L’hipòtesi és $A\wedge\lnot B$ i la tesi és una contradicció o absurd.

Solució:  En primer lloc observem que l’enunciat no és un condicional. Però, recordem la definició de un nombre racional diferent de zero: $a\neq 0$ és racional sii existeixen enters no nuls $m,n$ tals que $a=\dfrac{m}{n}$. Llavors, podem reformular l’enunciat com volem. En efecte, l’enunciat "$\sqrt{2}$ és un nombre irracional"és equivalent a la proposició següent escrita simbòlicament

Per demostrar aquesta proposició universal, considerem dos nombre enters no nuls $m,n$. Hem demostrar que no és possible que $\dfrac{m}{n}=\sqrt{2}$. L’estratègia serà fer la prova per reducció a l’absurd: suposem $m$ i $n$ són enters no nuls i que $\dfrac{m}{n}=\sqrt{2}$ (hipòtesi), hem de trobar un contradicció (tesi). No és restrictiu suposar que la fracció $\dfrac{m}{n}$ és irreductible; cas contrari, escriuríem la fracció irreductible equivalent. Si $\dfrac{m}{n}=\sqrt{2}$, aleshores $m=\sqrt{2}n$ i, per tant, $m^{2}=2n^{2}$. D’aquí, deduïm que $m^{2}$ és un enter parell. Llavors $m$ és parell com hem provat en l’exemple 1.15. Llavors, $m=2k$, on $k\in\mathbb{Z}$. D’aquí, $m^{2}=4k^{2}=2n^{2}$ i, per tant, $n^{2}=2k^{2}$. Deduïm que $n^{2}$ és parell i, per tant, $n$ també. Però, això és una contradicció perquè aleshores la fracció $\dfrac{m}{n}$ és reductible. En conseqüència, no és possible que $\dfrac{m}{n}=\sqrt{2}$, i, com $m$ i $n$ son arbitraris, $\sqrt{2}$ no és racional.

Aquí volem fer èmfasi en el fet següent: Hem pogut reformular l’enunciat pensant lògicament i això a part d’entendre millor l’enunciat ens ha permès fer una demostració per reducció a l’absurd.   $\square$

Solució:  Primer, escribim simbòlicament l’enunciat: $\lnot\left(\exists x\in\mathbb{R}\right)\left(x^{2}+1=0\right)$. Veiem que és la negació d’una proposició existencial. Fent ús de la següent equivalència lògica

i de la regla d’inferència IQU:

llavors només cal provar que prenent un nombre real qualsevol $b$, es compleix que $b^{2}+1\neq 0$. Però, això és immediat perquè $b^{2}\geq 0$ i, per tant, $b^{2}+1\geq 1$; en particular, $b^{2}+1\neq 0$.   $\square$

A matemàtiques també trobem enunciats amb quantificadors que rebutjant propietats. Però, de fet rebutjar una propietat enunciada per una proposició ‘$p$’ és el mateix que provar ‘$\lnot p$’. Per exemple, per demostrar que no és el cas que $\left(\forall x\in U\right)P(x)$, primer cal pensar en la següent equivalència lògica:

i després recordar la regla d’inferencia IQE:

Llavors, només cal trobar un exemple pel qual $P(x)$ és fals. Aquesta manera de fer la demostració és coneix com prova per contraexemple.

Solució:  Per buscar una estratègia, primer haurem de reformular l’enunciat lògicament: si $\mathbb{I}=\mathbb{R}\smallsetminus\mathbb{Q}$ és el conjunt dels nombres irracionals, aleshores

Hem vist que aquest enunciat és equivalent al següent:

Per tant, per demostrar l’enunciat només cal trobar dos nombres irracionals la suma dels quals no és irracional.   $\square$

A vegades trobem enunciats que són de la forma $\left(C\vee D\right)\longrightarrow B$, és a dir, que inclouen una disjunció en l’antecedent. En aquests casos, la següent equivalència

proporciona l’estratègia que hem de seguir. En efecte, per demostrar que $\left(C\vee D\right)\longrightarrow B$ és certa és suficient demostrar que $C\longrightarrow B$ i $D\longrightarrow B$ són ambdues certes. De fet, la demostració la construïm per casos (en aquest cas, n’hi ha dos casos) segons la forma que tingui l’antecedent. La demostració de cadascun dels casos seguirà l’estratègia que faci falta. Aquest mètode de demostració es coneix com prova per casos.

Solució:  Sabem que tot nombre enter $n$ és o parell o bé senar. Aquesta idea proporciona l’estratègia de la demostració: construïr una prova per casos. Volem provar que (1) si $n$ és parell, aleshores $n^{2}+n$ és parell, i (2) si $n$ és senar, aleshores $n^{2}+n$ és senar.

Cas 1:

Si $n$ és parell, llavors per definició existeix $k\in\mathbb{Z}$ tal que $n=2k$. Aleshores es té:

$$n^{2}+n=4k^{2}+2k=2\left(2k^{2}+k\right)\text{,}$$

i, per tant, $n^{2}+n$ és parell perquè $2k^{2}+k\in\mathbb{Z}$.

Cas 2:

Si $n$ és senar, llavors per definició existeix $m\in\mathbb{Z}$ tal que $n=2m+1$. Aleshores es té:

	$\displaystyle n^{2}+n$	$\displaystyle=\left(2m+1\right)^{2}+2m+1$
		$\displaystyle=4m^{2}+6m+2=2\left(2m^{2}+3m+1\right)\text{,}$

i, per tant, $n^{2}+n$ és parell perquè $2m^{2}+3m+1\in\mathbb{Z}$.

$\square$

Ara passem als teoremes de la forma $A\longrightarrow\left(C\vee D\right)$ on hi trobem una disjuntiva en el conseqüent. Una estratègia per a fer la demostració és fent ús primer de la llei del contrarecíproc i després una de les lleis de De Morgan:

A partir d’aquí, construïm la prova directa o per reducció al absurd. Veiem-ho en un exemple.

Solució:  Segons el que hem vist anteriorment, aquest enunciat és equivalent al següent: Si $x$ és racional i $y$ també ho és, llavors $xy$ és racional. Però això és evident perquè sabem que la multiplicació és una operación interna del cos dels racionals.   $\square$

Després d’haver discutit sobre l’aparició de la connectiva $\vee$, anem ara a tractar els casos quan aprareix la connectiva $\wedge$ en els teoremes de la forma $A\longrightarrow B$. Per demostar un enunciat de la forma $A\longrightarrow\left(C\wedge D\right)$ fem ús de l’equivalència següent:

A partir d’aquí, la demostració consisteix en provar que  $A\longrightarrow C$ i $A\longrightarrow D$ són certes.

Si l’enunciat és de la forma $\left(C\wedge D\right)\longrightarrow B$, llavors l’estratègia és prendre com hipòtesis que $C$ i $D$ són certes i com a tesi que $B$ és certa. La prova pot ser directe o per reducció a l’aburd.

Finalment, volem tractar una altra forma lògica que presenten molts teoremes. Són els teoremes de la forma $A\longleftrightarrow B$ i que ens donen condicions necessàries i suficients. La llei del bicondicional ens dona la resposta per construir proves d’aquest teoremes:

Per tant, és suficient provar $A\longrightarrow B$ i $B\longrightarrow A$, cadascun dels quals es pot demostrar mitjançant qualsevol dels mètodes que hem vist fins ara.

Solució:  L’enunciat expressat formalment és:

Per tant, si $x,y$ són nombres reals arbitraris, hem de demostrar $xy=0\longleftrightarrow x=0\vee y=0$. Segons hem dit abans, això és equivalent a demostrar cadascun del teoremes següents: (1) $xy=0\longrightarrow x=0\vee y=0$ i (2) $x=0\vee y=0\longrightarrow xy=0$.

(1) Demostrem que la condició necessària perquè  $xy=0$ és $x=0$ o $y=0$. Això és equivalent a provar que si $x\neq 0$ i $y\neq 0$ aleshores $xy\neq 0\,$. No és restrictiu suposar que $x\leq y$; cas contrari, faríem que $x>y$ i la prova es contrueix de forma anàloga. Ara l’estratègia és fer la demostració per casos: si $x\neq 0$, llavors o $x>0$ o bé $x<0$.

Cas 1:

Si $0<x\leq y$, llavors $xy>0$ i, per tant, $xy\neq 0$.

Cas 2:

Si $x<0$ i $y\geq x$, llavors apareixen dos subcasos: (2.1) $x<0$ i $y>0$ (2.2) $x<0$ i $y<0$ i $y\geq x$.

Subcas 2.1:

Si $x<0$ i $y>0$, llavors $xy<0$ i, per tant, $xy\neq 0$.

Subcas 2.2:

Si $x<0$ i $y<0$ i $y\geq x$, llavors $xy>0$ i, per tant, $xy\neq 0$.

Com a conseqüència, concluïm el que volíem demostrar.

(2) Demostrem que la condició suficient perquè $xy=0$ és que $x=0$ o $y=0$. Això és evident perquè si $x=0$ aleshores $0\cdot y=0$ i si $y=0$, $x\cdot 0=0$.   $\square$

És molt freqüent trobar demostracions que impliquin l’existència d’un objecte que compleix una determinada propietat i també la seva unicitat. Quant a la prova d’existència només cal trobar l’objecte en concret que compleix la propietat. Quant a la unicitat, l’estratègia més comuna és suposar que $x$ i $y$ són dos objectes que satisfan la propietat donada, llavors hem de demostrar que $x=y$.

Solució:  Primer hem de provar l’existència, buscant aquest nombre que representa la proporció donada. Suposem que existeix, aleshores es compleix

Fent que $\dfrac{a}{b}=x$, llavors tenim

i, resolent l’equació de segon grau i sabent que $x>0$, es té la solució

Ara, hem de veure que $\Phi$ és irracional. Considerem el conjunt $A=\left\{a\in\mathbb{N}\text{: }\exists b\in\mathbb{N}\text{ i }a>b>0\text{ i }\Phi=\dfrac{a}{b}\right\}$.Si $A=\emptyset$, llavors $\Phi$ és irracional. Suposem ara que no és el vuit. Aleshores, com $A$ és un subconjunt de $\mathbb{N}$, $A$ té primer element, que denotem per $m$. Llavors es té $\Phi=\dfrac{m}{b}$ i $m>b>0$, per tant, $m+b>m$ i

però, això és una contradicció perquè

Deduïm que $\Phi$ és irracional.

Finalment, hem de demostrar la unicitat. Suposem que $\Phi_{1}$ i $\Phi_{2}$ compleixen la propietat. Llavors, de (1.12.8) es té

i, per tant, $\Phi_{1}-\Phi_{2}=0$ o $\Phi_{1}+\Phi_{2}-1=0$ però, $\Phi_{1}+\Phi_{2}>1$ perquè $a>b>0$. Per tant, $\Phi_{1}=\Phi_{2}$.   $\square$

La inducció matemàtica és una tècnica útil per demostrar enunciats sobre nombres naturals. Considerem, per exemple, l’enunciat següent: "Si $n$ és parell, llavors $n^{2}$ és divisible per 4". Volem provar que aquest enunciat és correcte. Com ho fem? Aplicant inducció sobre $n$, que vol dir provar els dos passos següents:

1. 1.
   ​

   Primer hem de provar que la propietat és vertadera pel primer element. En aquest cas el primer element és $2$ perquè tractem amb nombres naturals parells. La propietat es certa perquè $2^{2}=4$ que és divisible per 4.

2. 2.
   ​

   Per a tot nombre natural $n$ (no sabem quin és), si la propietat és certa per $n$, llavors hem de provar que també ho és per el següent element: Suposem  $n$ és parell i que $n^{2}$ és divisible per 4, aleshores hem de provar que el següent parell $(n+2)^{2}$ és divisible per 4. En efecte, $(n+2)^{2}=n^{2}+4n+4=4k+4n+4=4(k+n+1)$, on $n^{2}=4k$ i $k\in\mathbb{N}$.

Concluïm que la propietat és vàlida per a tot nombre natural parell.

Intuïtivament, aquestes dues condicions permeten assegurar que la propietat es compleix per tots els naturals. En efecte, $P(2)$ és vertadera, $P(2)\longrightarrow P(4)$ és vertadera i, per tant, $P(4)$ també ho és; $P(4)\longrightarrow P(6)$ és certa i, per tant, $P(6)$ també. I així succesivament.

La base d’aquest mètode de demostració és el principi d’inducció que, de fet és un dels axiomes que defineixen els nombres naturals. Aquest principi diu: Si $P(n)$ és un enunciat sobre els naturals i es compleixen les dues condicions següents: A la primera part, anomenada cas base, mostrem que $P(1)$ és es compleix (el primer element no necessàriament és 1, depèn de cada cas). A la segona part, anomenada pas inductiu, suposem que $n$ és un natural tal que $P(n)$ és certa, tot i que no sabem què és $n$, i hem de deduïr que $P(n+1)$ és certa. La suposició que $P(n)$ és vertadera es diu hipòtesi d’inducció. La conclusió d’aquest raonament és que $P(n)$ és vàlida per a tot $n$ natural. Aquest mètode de demostració es coneix com prova per inducció sobre $n$.

Veiem en detall aquest mètode en un exemple:

Solució:  Construïm una prova d’inducció sobre $n$, sent $P(n)=$ ‘$1+2+\cdots+n=\dfrac{n(n+1)}{2}$’.

Cas base:

$P(1)$ és $1=\frac{1(1+1)}{2}$ i, evidentment és veritat.

Hipòtesi d’inducció:

Suposem que $P(n)$ és certa, o sigui que $1+2+\cdots+n=\dfrac{n(n+1)}{2}$.

Tesi:

Hem de demostrar que $P(n+1)=$‘$1+2+\cdots+n=\dfrac{(n+1)(n+2)}{2}$’ és certa.

En efecte, aplicant l’hipòtesi d’inducció, es té

que és el que volíem veure.

Conclusió:

Pel principi d’inducció sobre $n$, deduïm que $P(n)$ és certa per a tot $n\in\mathbb{N}$.

$\square$

Solució:  El cas base és per $n=1$: $8-3=5$ que és divisible per $5$. Suposem ara que per a tot nombre natural $n$ es té que $8^{n}-3^{n}$ és divisible per 5 (hipòtesi d’inducció), hem de demostrar que $8^{n+1}-3^{n+1}$ també és divisible per 5. En efecte, tenim

però, per hipòtesi d’inducció, $8^{n}-3^{n}=5k$, sent $k\in\mathbb{N}$. Per tant,

i, d’aquí, s’obté que $8^{n+1}-3^{n+1}$ és divisible per 5 perquè $8k+3^{n}\in\mathbb{N}$. Com a conseqüència, $8^{n}-3^{n}$ és divisible per 5 per a tot nombre natural $n$.   $\square$

Les definicions inductives estan implícites en les definicions de diverses funcions molt comuns que impliquen nombres enters no negatius. Per exemple, el factorial d’un nombre enter no negatiu $n$, designat per $n!$, es defineix inductivament d’aquesta manera:

• •
  ​

  $0!=1;$

• •
  ​

  $\left(n+1\right)!=\left(n+1\right)\cdot n!$.

Un altre exemple son les definicions per recursió. La successió de Fibonacci és un bon exemple: $1,1,2,3,5,8,13,...$, que podem definir per recursió d’aquesta manera:

• •
  ​

  $u_{1}=1$,

• •
  ​

  $u_{2}=1$,

• •
  ​

  $u_{k+1}=u_{k-1}+u_{k}$ per $k\in\mathbb{N}$ i $k\geq 2$.