Siguiente: Inducción matemática Un nivel arriba: Conceptos básicos Anterior: Conceptos básicos

Pruebas por contradicción

La función $p:n\mapsto n^2-n+41$ define números primos al inicio.

$$\begin{array}{\vert\vert r\vert r\vert\vert r\vert r\vert\ver... ... & 20 & 421 & 30 & 911 & 40 & 1601 \\ \hline\hline \end{array}$$

Sin embargo,

$$n=41\Rightarrow p(n)= 1681=41^2.$$

¡De la repetición de un patrón no necesariamente se sigue una regla general! Es necesario presentar pruebas de enunciados que se quieran probar en general. En las pruebas por contradicción para demostrar que una tesis $\phi$ se sigue de una secuencia de hipótesis $\Phi$, en símbolos $\Phi\vdash \phi$, se niega la tesis y junto con las hipótesis se deriva una contradicción, en símbolos $\Phi\cup\{\neg\phi\}\vdash \perp$. La aceptación de este tipo de razonamiento conlleva la aceptación del Principio del tercero excluído y del Principio de consistencia de las matemáticas, los cuales rezan:

Principio del tercero excluído.

Para toda sentencia $\phi$, es decir, para fórmula cerrada bien formada, y para toda interpretación M de los símbolos de $\phi$, se ha de tener que $\phi$ se cumple en M, en símbolos $M\models \phi$, o bien que la negación de $\phi$ se cumple en M, en símbolos $M\models \neg\phi$.

Principio de consistencia de las matemáticas.

En toda teoría matemática T (digna de estudio), se tiene que no existe una sentencia $\phi$ formulada en el lenguaje de la teoría T tal que ambas $\phi$ y $\neg\phi$ sean demostrables en T, es decir, tal que $T\vdash\phi$ y $T\vdash\neg\phi$.

Aunque de mucho sentido común, ambos principios son cuestionables desde diversos supuestos formales. Como meras ilustraciones de estos cuestionamientos mencionamos dos de ellos:

1.

El principio del tercero excluído permite demostrar existencia de objetos de manera no constructiva. En efecto, veamos que existen dos números irracionales tales que uno elevado al otro da un racional. Sea $r=\left(\sqrt{2}\right)^{\sqrt{2}}$. Si r fuera racional, considérese $p=\sqrt{2}$ y $q=\sqrt{2}$. En otro caso, considérese p=r y $q=\sqrt{2}$. En cualquier caso se tiene que ambos p y q son irracionales y p^q es racional. Tenemos pues demostrada así la afirmación formulada. Sin embargo, esta demostración no da ejemplos de irracionales cuya potencia de uno al otro da un racional.

2.

La aritmética de Peano se realiza naturalmente en el conjunto de los números naturales. Estos conforman el modelo estándar de la aritmética. Sin embargo, de acuerdo con el Segundo Teorema de Incompletitud de Gödel, la misma aritmética de Peano no puede demostrar su propia consistencia.

Los siguientes teoremas se prueban por contradicción y los citamos como ejemplos de este tipo de demostraciones.

Teorema 1.1 (Pitágoras, 582-500 AC)   $\sqrt{2}$ no es un número racional.

En efecto, si $p,q\in Z\!\!\!Z$ fuesen dos enteros tales que $\sqrt{2}=\frac{p}{q}$, entonces

$$p^2=2q^2,\eqno(*)$$

consecuentemente p² es un múltiplo de 2, y por esto mismo p=2p₁ también lo es. En la ec. (*) vemos un 2 a la derecha. Falta al menos uno más, pues $p^2=p\cdot p$ es al menos divisible por 4. Luego hemos de tener necesariamente que q² es un múltiplo de 2, y por esto mismo q=2q₁ también lo es. Hemos pues encontrado $p_1,q_1\in Z\!\!\!Z$ tales que

$$p=2p_1\hspace{1cm},\hspace{1cm} q=2q_1\hspace{1cm},\hspace{1cm} \sqrt{2}=\frac{p_1}{q_1}.\eqno(**)$$

Reiterando las relaciones (**) tenemos que para cualquier $n\geq 0$ existen $p_n,q_n\in Z\!\!\!Z$ tales que

$$p=2^np_n\hspace{1cm},\hspace{1cm} q=2^nq_n\hspace{1cm},\hspace{1cm} \sqrt{2}=\frac{p_n}{q_n}.$$

p y q serían pues divisibles por potencias arbitrariamente grandes de 2. Esto no es posible, dado que esos números son enteros (estándares). Por tanto, no pueden existir p y q.

Teorema 1.2 (Euclides, tex2html_wrap_inline$$300 AC)   Hay una infinidad de números primos.

En efecto, si ése no fuera el caso, denotemos por $P=\{p_0,p_1,\ldots,p_{n-1}\}$ al conjunto finito de, digamos que n, números primos. Consideremos el número entero $q_n=\prod_{i=0}^{n-1} p_i + 1$. Es evidente que ningún primo $p_i\in P$ puede dividir a q_n, pero, de acuerdo con el Teorema Fundamental de la Aritmética, q_n ha de ser divisible por algún número primo p_n, que acaso puede ser tal que p_n=q_n. El primo p_n no está en P y esto contradice que P comprendía a todos los primos.

Teorema 1.3   Si $a\in \Sigma$ y $x\in \Sigma^*$ son tales que ax=xa entonces $\exists n: x=a^n.$

En efecto, supongamos que ése no fuera el caso y que $\exists b\in\Sigma-\{a\}$ que aparezca en x. Sea k la mínima posición, contada desde la izquierda de x donde aparezca un símbolo distinto a a, digamos b. Entonces en la palabra ax hasta antes de la posición k+1 sólo hay a-es, en tanto que en la palabra xa hay una b exactamente en la posición k. Por tanto no puede ocurrir que ax=xa.
Siguiente: Inducción matemática Un nivel arriba: Conceptos básicos Anterior: Conceptos básicos