Álgebra Superior I: Demostraciones directas e indirectas

Esta entrada es parte de una serie de notas introductorias sobre técnicas de demostración. Cada una es independiente de la otra, y para su explicación, se usa el siguiente diagrama de un mundo imaginario llamado el mundo de los Blorgs. Para leer más sobre ello, haz click aquí.

Introducción

Hasta ahora hemos introducido algunos conceptos introductorios de lo que es una demostración matemática, pero apenas estamos por iniciar este recorrido hacia lo que son estas. Ahora, empezaremos por ver dos formas de pensar al demostrar que son las demostraciones directas e indirectas.

La demostración directa

Ahora vamos a explorar un poco más esto de las demostraciones, qué son y cómo nos ayudan. ¿Recuerdas nuestro ejemplo de que todos los blorgs amarillos comían peces? Este es un ejemplo de una demostración directa. Este nombre viene del hecho de que partimos de una secuencia de proposiciones válidas y vamos conectando las proposiciones una tras una hasta que tenemos la conclusión deseada. En general este tipo de demostraciones van a ser cadenas de puras implicaciones. Por ejemplo

$P_0 \Rightarrow P_1, P_1 \Rightarrow P_2, \dots, P_{n-1} \Rightarrow P_{n} $

De donde concluímos que $P_0 \Rightarrow P_{n}$. Esto en términos sencillos quiere decir: Las demostraciones directas van a ser aquellas que podemos dar «el paso claro» por ejemplo si sabemos que con madera podemos construir las patas y el asiento, y con patas y el asiento podemos construir una silla, entonces ya sabríamos que con madera podemos construir una silla, pues decimos: «Primero con la madera construimos las patas y el asiento, y después con las patas y el asiento construimos la silla». Cuando veamos otros tipos de demostraciones, verás más fácilmente porqué tienen este nombre. Mientras tanto veamos otro ejemplo.

Proposición. Un blorg que vive en las montañas come los lunes.

Demostración. Recordemos cómo empezamos la demostración de la entrada pasada, empezamos con un blorg que vive en las montañas y veremos poco a poco que come los lunes. Para empezar, nota que con las siguientes proposiciones:

$P(x) = x \text{ vive en las montañas} $

$Q(x) = x \text{ es un blerg},$

se cumple que:

$$P(x) \Rightarrow Q(x).$$

Además, sabemos que todos los blergs comen los lunes, es decir, suponiendo que $R(x) = x \text{ come los lunes}$ entonces:

$$Q(x) \Rightarrow R(x).$$

Y la siguiente regla de inferencia es válida:

\begin{array}{rl}
& P \Rightarrow Q \\
& Q \Rightarrow R \\
\hline
\therefore & P \Rightarrow R
\end{array}.

Entonces podemos aplicar esta regla de inferencia a nuestro problema, dando como resultado que

$$P(x) \Rightarrow R(x) $$

Ahora recuerda que en las demostraciones nuestro objetivo va a ser «generalizar». No basta con que un blorg en las montañas coma los lunes, si no quisieramos que siempre que veamos a un blorg en las montañas, sepamos que come los lunes.

Para esto, empezaremos con un blorg a quien le llamaremos $x$ y lo único que sabemos de este blorg es que vive en las montañas, es decir $P(x)$. Ahora, aplicando las reglas de inferencia, sabemos que si $P(x)$ entonces también $R(x)$. Esto quiere decir que sabiendo que un blorg vive en las montañas, ya sabemos que también come los lunes. Recuerda que para hacer este paso aplicamos las reglas de inferencia. De esta manera, $x$ come los lunes.

Por lo tanto, los blorgs que viven en las montañas comen los lunes.


$\square$

Demostraciones indirectas

Otra estrategia para demostrar cosas va a ser mediante lo que se conoce como la demostración indirecta. Y esta forma de demostrar proposiciones va a usar la siguiente regla de inferencia:

\begin{array}{rl}
& P \Rightarrow Q \\
\hline
\therefore &(\neg Q) \Rightarrow (\neg P)
\end{array}.

¿Recuerdas que la premisa es equivalente a la conclusión? Pues el que sea equivalente es suficiente para que sea una regla de inferencia válida. Hay ocasiones en la que no es tan sencillo hacer la demostración directa, pues al hacer la demostración indirecta, no probamos que una proposición $P$ implique $Q$, sino que en vez de eso, probamos que $\neg Q$ implica $\neg P$. Esta herramienta nos va a ser útil, pues resultará que en ocasiones es mejor trabajar con las negaciones que con las proposiciones sin negar, veamos un ejemplo.

Proposición. Si un blorg es amigo de los delfines, entonces es amarillo.

Demostración. Como estamos dando un ejemplo de la demostración indirecta, entonces pensémosle como tal. Primero tomemos nuestras proposiciones.

$P(x) = x \text{ es amigo de los delfines}$

$Q(x) = x \text{ es amarillo}.$

Y tenemos la proposición $P(x) \Rightarrow Q(x)$. Lo que nos dice la regla de inferencia es que habremos demostrado esta proposición si demostramos que $\neg Q \Rightarrow \neg P$. Ahora notemos que

$\neg Q(x) = x \text{ no es amarillo} = x \text{ es azul o rojo}$
$\neg P(x) = x \text{ no es amigo de los delfines}.$

Nota que si un blorg no es amarillo, entonces solo puede ser azul o rojo (pues los blorgs solo pueden ser de tres colores). De esta manera, en vez de demostrar que $P(x) \Rightarrow Q(x)$ demostraremos que $\neg Q \Rightarrow \neg P$. Para ello, es suficiente tomar a un blorg $x$ que sea azul o rojo. A continuación vamos a dividir esta demostración en casos. Como tenemos dos colores posibles para los blorgs, vamos a ver primero qué pasa si nuestro blorg es rojo y después qué pasa si es azul. Veamos cómo se ve esto.

Caso 1. $x$ es rojo.

Como nuestro blorg es rojo, entonces es un blerg, y sabemos que los blergs solo son amigos de los blurgs. Entonces no es amigo de los delfines.

¿Notas cómo probamos la conclusión? Ahora ya sabemos que la proposición es cierta siempre que nuestra $x$ sea rojo entonces no será amigo de los delfines. Con esto solo nos queda un caso.

Caso 2. $x$ es azul.

El caso que falta es que el blorg sea azul, es decir que sea un blurg. Pero aún así se cumple que $x$ no sea amigo de delfines, pues es amigo de los blargs y blergs.

Entonces lo que acabamos de hacer fue demostrar que en cualquier caso, el blorg $x$ no es amigo de los delfines. Así que podemos concluir que $\neg Q \Rightarrow \neg P$

$\square$

Sobre la demostración

Vamos a hacer algujnas observaciones sobre la forma en que demostramos nuestras proposiciones.

  1. Hasta ahora tenemos dos formas de demostrar: la directa y la indirecta. En pocas palabras la directa usa sucesiones de proposiciones que ya sabemos para llegar a una conclusión, mientras que la indirecta no empieza por lo que quiere demostrar, sino que nota que si la conclusión no es cierta, entonces la premisa no lo es.
  2. En nuestra segunda demostración dividimos nuestro problema en casos, esto es, notamos que si nuestro blorg no era amarillo, solo podía ser azul o rojo. Entonces lo que hicimos en ese punto fue irnos por los dos caminos: el camino en donde el blorg es rojo y el camino en donde es azul. Y notamos que en cualquiera de los caminos, no se cumplía la premisa. Habrá ocasiones en las que notes que para demostrar una proposición deberás considerar todos los casos, entonces tendrás que dividir tu problema en los distintos casos para hacer la demostración.
  3. Algo más que mencionar de nuestra última demostración es que no siempre vamos a dividir una demostración indirecta en casos, pues fue una coincidencia que en nuestra demostración necesitásemos del uso de los distintos casos. Entonces una demostración indirecta no siempre va a usar casos, pero hay ocasiones en las que serán necesarios.

Tarea moral

  1. Demuestra directamente que los blorgs rojos comen frutas.
  2. Demuestra directamente que los blorgs rojos comen frutas los lunes.
  3. Demuestra indirectamente que si un blorg no come peces, entonces es un blerg.

Más adelante…

Continuando con nuestras estrategias, la siguiente consistirá en la contradicción. En pocas palabras para demostrar que una proposición es verdadera, supondremos que no lo es. Y en una serie de pasos lógicos, veremos que habrá proposiciones que son falsas y verdaderas a la vez (esto no puede pasar), llamándose esto una contradicción.

Entradas relacionadas

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.