Archivo de la etiqueta: demostraciones

Álgebra Superior I: Demostración de condicionales y dobles condicionales

Por Guillermo Oswaldo Cota Martínez

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

Para terminar nuestra sección de demostraciones (no significa que terminamos de demostrar, para nada, apenas es el comienzo), vamos a ver el caso en donde tengamos la doble implicación. Esto no va a ser difícil, pues hemos desarrollado suficientes estrategias para ello, y solo verás que la forma de demostrar estas proposiciones, es ver la doble implicación de otra manera.

La suficiencia y necesidad

Es común ver proposiciones matemáticas de la forma

$$\forall x (P(x) \Leftrightarrow Q(x)) $$

Como por ejemplo

Proposición. Un blorg come dos veces a la semana si y solo si tiene amigos amarillos y rojos.

Para este tipo de demostraciones, lo que haremos será demostrar dos cosas: la suficiencia y la necesidad. Recordemos que la doble implicación puede escribirse de la siguiente manera:

$$\forall x (P(x) \Leftrightarrow Q(x)) = \forall x ((P(x) \Rightarrow Q(x)) \land (Q(x) \Rightarrow P(x) )) $$

Es decir, para demostrar la condición, es necesario demostrar que si un blorg come dos veces a la semana entonces tiene amigos amarillos y rojos, y también será necesario mostrar que si un blorg tiene amigos amarillos y rojos come dos veces a la semana. Esto es, demostrar que las condiciones son equivalentes: un blorg solo tiene amigos amarillos y rojos si y solo si come dos veces por semana.

Demostración. Para esto, consideremos primero a un blorg $x$, para demostrar la doble implicación, es común dividir el problema en dos partes que podrás encontrar como «la ida» y «el regreso», esto hace referencia a que al demostrar la ida, demostraras que $P(x) \Rightarrow Q(x)$ y el regreso demuestra que $P(x) \Leftarrow Q(x)$. No dejes que te confunda la dirección de la flecha, simplemente es otra forma de demostrar que $Q(x) \Rightarrow P(x)$ (mira la dirección de la flecha).

Y comúnmente encontrarás en las demostraciones las notaciones de $\Rightarrow$ y $\Leftarrow$ haciendo referencia a si demostrarán la ida o el regreso, justo como lo haremos a continuación.

$\Rightarrow$

Primero demostraremos que si un $x$ come dos veces a la semana, entonces tiene amigos rojos y amarillos.

Como $x$ come dos veces a la semana, entonces es un blurg, pues es la única especie que come los Lunes y Viernes, mientras que los Blargs y Blergs comen solo los Lunes. Ahora, notemos que un blurg es amigo de los Blergs y los Blargs, cuyos respectivos colores son rojos y amarillos. Así hemos demostrado que si un $x$ come dos veces a la semana, entonces tiene amigos rojos y amarillos.

$\Leftarrow$

Ahora, para demostrar el regreso, supongamos que $x$ tiene amigos rojos y amarillos y lleguemos a la conclusión de que come dos veces a la semana.

Notemos a los amigos de cada especie de blorg. Los Blargs son amigos de los Blurgs y de los delfines, los cuales son azules, entonces no tienes amigos amarillos y rojos, por otro lado los Blergs son amigos de los Blurgs, que son azules, por lo que tampoco cumplen la condición. Mientras que los Blurgs son amigos de los Blergs y Blargs, que cumplen con ser rojos y amarillos. Entonces $x$ tiene que se un blurg. A continuación, notemos que los Blurgs comen los Lunes y Viernes, esto es, que comen dos veces por la semana, cumpliendo la proposición.

De esta forma hemos demostrado que un blorg come dos veces a la semana si y solo si tiene amigos amarillos y rojos.

Otro vistazo a la doble implicación

Para que te des una idea mejor sobre el poder de este tipo de proposiciones, recuerda lo siguiente: «La doble implicación es la forma de decir que dos cosas son equivalentes». Esto no es algo nuevo, pues ya hemos mencionado esto antes. La diferencia es que ahora ya tenemos aplicaciones prácticas de esto, ve el siguiente ejemplo:

Proposición. Un blorg come dos veces por semana si y solo si tiene un amigo de otra especie que puede comer fresas.

Demostración. Ahora, no solo vamos a usar la doble implicación para la demostración, sino que juntaremos proposiciones que hemos demostrado anteriormente. Primero que nada, notemos que la proposición se parece en parte a la pasada. Usaremos lo que sabemos de la proposición pasada. Como un blorg come dos veces por semana si y solo si tiene amigos amarillos y rojos. Ahora veamos cómo podemos usarla para demostrar esto.

Considera las proposiciones:

$$ P(x) = \text{ x come dos veces por semana},$$

$$ Q(x) = \text{ x tiene amigos rojos y amarillos},$$

$$ R(x) = \text{ x tiene un amigo de otra especie que puede comer fresas}.$$

Lo que nos pide demostrar la proposición es que

$$\forall x (P(x) \Leftrightarrow R(x)). $$

Pero sabemos que

$$\forall x (P(x) \Leftrightarrow Q(x)). $$

Y notemos que la siguiente regla de inferencia es válida

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

Entonces podemos reducir esta proposición a demostrar «Un blorg tiene amigos amarillos y rojos si y solo si uno de sus amigos de otra especie puede comer fresas». Entonces demostremos esto.

Afirmación. Un blorg tiene amigos amarillos y rojos si y solo si uno de sus amigos de otra especie puede comer fresas.

Demostración de la afirmación.

$\Rightarrow$

Sea $y$ un blorg con amigos amarillos y rojos. Basta exhibir a algún amigo que pueda comer fresas, así que ingeniosamente decimos: sea $x$ un amigo rojo de $y$ (esto lo podemos hacer, ya que suponemos que el blorg tiene amigos amarillos y rojos). Como $x$ es rojo, entonces es un blerg. Además, sabemos por una proposición de la entrada anterior que existe una única raza de Blorgs que pueden comer fresas, y son precesiamente los Blergs. De esta manera $x$ puede comer fresas.

Por lo tanto $y$ tiene un amigo que puede comer fresas. Como además tiene amigos de dos colores, y la única especie que puede tener amigos amarillos y rojos son los Blurgs, entonces $y$ es un blurg. Así, $y$ tiene un amigo de otra especie que puede comer fresas.

$\Leftarrow$

Ahora supongamos que $y$ es un blorg y tiene un amigo $x$ de otra especie que puede comer fresas. Como la única especie vegetariana son los Blergs, entonces $x$ es un Blerg (supongamos que esto es cierto por ahora, más adelante lo demostrarás). De esta manera, $y$ es un blarg o blurg (pues recordemos que $x$ y $y$ son de diferentes especies). Veamos que si $y$ fuera un blarg, tendría únicamente amigos Blurgs y delfines, y no de Blergs, mientras que los Blurgs sí son amigos de los Blergs, por lo tanto $y$ es blurg.

Finalmente, nota que los Blurgs tienen amigos Blargs y Blergs, los cuales son amarillos y rojos.

De esta manera, hemos demostrado que un blorg tiene amigos amarillos y rojos si y solo si uno de sus amigos de otra especie puede comer fresas.

$\square$

Habiendo demostrado la afirmación, y sabiendo que $$ \begin{array}{rl} & P \Leftrightarrow Q \\ & P \Leftrightarrow R \\ \hline \therefore & Q \Leftrightarrow R\end{array}.$$ Entonces se cumple que Un blorg come dos veces por semana si y solo si tiene un amigo de otra especie que puede comer fresas.

$\square$

Más adelante…

El mundo de los Blorgs nos ayudó a poner un paso dentro del pensamiento matemático. Nos acompañarán solo un poco más, pero ya no estaremos enfocados en las demostraciones. Daremos pasos hacia un camino que puede resultar un poco distinto, pero verás que se parece mucho a la lógica proposicional. Algunos dicen que no puede haber una sin otra. Y este tema es la teoría de conjuntos. Si pudiéramos poner las matemáticas como un edificio, algunos dirían que la estructura estaría hecha de lógica y conjuntos. Así que exploraremos este otro «ingrediente» de las matemáticas.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Prueba que la siguiente regla de inferencia es válida: $$ \begin{array}{rl} & P \Leftrightarrow Q \\ & P \Leftrightarrow R \\ \hline \therefore & Q \Leftrightarrow R\end{array}.$$
Demuestra que un blorg es vegetariano si y solo si es un blerg.
Usando la última proposición de la entrada, demuestra que Un blorg come dos veces por semana si y solo si tiene un amigo que puede comer alimentos con semillas.
Demuestra que un blorg no es amigo de los Blergs si y solo si come los mismos días que los Blergs y es amigo de un animal marino.

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Problemas de demostraciones con conectores y cuantificadores
Siguiente entrada del curso: Problemas de demostraciones de condicionales y dobles condicionales.

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Superior I: Demostración de proposiciones con cuantificadores

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

En esta entrada revisaremos más a fondo cómo es que los cuantificadores que repasamos antes se usan dentro de las proposiciones y cómo demostrar estas. Veremos ejemplos con estos y algunos ejemplos famosos.

Los cuantificadores en las demostraciones

Ya hemos trabajado antes con los cuantificadores, aunque quizá no lo hayas notado, ya hemos trabajado con ellos. Por ejemplo, cuando hicimos la demostración de «Los Blorgs amarillos comen peces», lo que hicimos fue considerar cualquier blorg amarillo e hicimos una serie de pasos lógicos para demostrarlo. En ningún lugar dice que solo algunos Blorgs amarillos comen peces, en general dice que Los Blorgs amarillos comen peces, es decir todos los Blorgs amarillos cumplen la condición de comer peces. ¿La palabra resaltada te recuerda algo? Pues regresando a lo que antes vimos como los cuantificadores, recordarás que usabamos algunos cuantificadores para hacer énfasis en cómo eran las proposiciones. Pues, por ejemplo si consideramos el universo de discurso de los Blorgs y decimos $P(x) = \text{ x come los viernes}$, sería incorrecto:

$$\forall x P(x) .$$

Pues los únicos que comen los viernes son los Blurgs. En cambio existe al menos una especie que sí come esos días, así que sería correcto decir:

$$\exists x P(x), $$

ya que si $x$ es un blurg, entonces $P(x)$ es verdadero.

Así que podríamos demostrar la siguiente afirmación:

Proposición. Existen Blorgs que comen los viernes.

Demostración. Para ello, notemos que un blorg puede ser blarg, blerg y blurgs. A continuación vamos a considerar a $x$ un blorg que es blurg (podemos hacer esto, pues dentro del «conjunto» de los Blorgs, hay Blurgs). Y como sabemos, todos los Blurgs comen los Lunes y Viernes. En particular, comen los viernes, por lo que hemos demostrado la proposición.

$\square$

Diferencias entre cuantificadores

Vamos a detenernos y analizar cómo se diferenció la última demostración con lo que hemos estado haciendo antes. Analiza la demostración anterior con la siguiente:

Proposición. Los Blorgs comen un día antes de los Martes.

Demostración. Consideremos $x$ un blorg. Como es un blorg puede que sea un blarg, blerg o blurg.

Caso 1. $x$ es un blarg.

Como $x$ es blarg, entonces come los Lunes, que resulta ser un día antes de los Martes.

Caso 2. $x$ es un blerg.

Igual que en el caso anterior, si $x$ es blerg, entonces come los días antes de los Martes.

Caso 3. $x$ es un blurg.

Sabemos que los Blurgs comen los Lunes y los Viernes. Si $x$ es un blurg, entonces en particular come los lunes, y así, come los días antes de los Martes.

En cualquiera de los casos, $x$ cumple la proposición.

$\square$

Esta es una demostración que bien pudimos haber escrito como «Todos los Blorgs comen los días antes de los Martes». Sin embargo, en la práctica no es muy común ver escrito explícitamente la palabra «todos/todas», pues al hablar de «Los Blorgs», se infiere que hablamos de todos los Blorgs. Así podemos hacer notar las siguientes diferencias entre las dos demostraciones, la primera en donde usamos el cuantificador existe y en la que usamos todos.

Existen Blorgs que comen los viernes.	(todos) Los Blorgs comen un día antes de los Martes.
Se puede reescribir como $$\exists x P(x) $$	Se puede reescribir como $$\forall x P(x) $$
Consideramos un blorg «mañoso». Es decir, dentro del «conjunto» de los Blorgs, consideramos a uno estratégicamente que nos ayudara a demostrar que al menos un blorg cumplía la condición, en este caso un blurg.	Consideramos un blorg arbitrario (tuvimos que considerar distintos casos en los que el blorg fuera blarg, blerg o blurg)
Exhibimos el ejemplo de un blorg, que comía los viernes. Y con eso demostramso que la proposición se cumplía.	Llegamos a la conclusión de que sin importar cómo fuera el blorg, comía un dia antes de los Martes.

Esto nos quiere decir que cuando estemos hablando del cuantificador $\exists$, no necesitamos generalizar el caso, solo necesitamos exhibir un ejemplo donde la proposición se cumpla. Mientras que cuando hablamos de $\forall$, tenemos que generalizar, es decir, tenemos que considerar todos los casos posibles para probar que una afirmación sea verdadera o no.

Tratando con la unicidad.

Vamos a ver ahora un pequeño mapa de cómo viven los Blorgs en el mundo Blorg:

Este mapa muestra cómo se dividen los Blorgs, así que cuando estuvimos haciendo la demostración de existencia de los Blorgs que comen los Viernes, elegimos alguno de estos:

Mientras que cuando hablamos de $\forall$, tuvimos que comprobar que se cumplía para cualquiera de los Blorgs, ya fueran Blergs, Blargs o Blurgs. Pero aún falta otro cuantificador, que es el $\exists !$.

Ahora lee la siguiente proposición:

Proposición. Existe una única raza de Blorgs que dentro de su dieta puede haber fresas.

Nota que ahora no estamos hablando de los Blorgs como criaturas, sino de sus especies, y solo existen tres especies de blorg: Blargs, Blergs y Blurgs. Es decir, nos piden demostrar que entre estas tres, solo existe una que come fresas.

Nuestra proposición no nos habla de los Blorgs como criaturas individuales, sino que ahora nos habla de las **especies de los Blorgs**. Nota que ahora la flecha señala a las especies (círculos).

Entonces para demostrar que se cumple la proposición, tendremos que primero exhibir una especie que coma fresas y después demostrar que es única.

Demostración. Solo existen tres especies de Blorgs, notemos que dentro de estas, se encuentran los Blergs que comen frutos, por lo que son los Blergs quienes pueden incluir fresas en sus dietas.

(Hasta aquí hemos probado que existe una especie que puede comer fresas)

Ahora, para demostrar que es única, veamos que las otras dos razas solo comen peces, los cuales evidentemente no pueden incluir las fresas, por tanto esta especie es única.

(Así demostramos la unicidad)

$\square$

Esta es una proposición que se puede escribir como

$$\exists ! x P(x) $$

Entonces para demostrar el cuantificador $\exists ! x P(x)$, primero debemos demostrar $\exists x P(x)$ y después que es única. Nota que demostrar la unicidad, equivale a demostrar lo siguiente:

$$\exists! x P(x) = \exists x (P(x) \land \forall y \neq x (\neg P(y))) $$

Es decir «Existe $x$ que cumple $P(x)$ y todo elemento $y$ distinto a $x$, no cumple $P(y)$»

En nuestra demostración la primera parte antes del primer paréntesis, demostramos que existe $x$ (Blergs) que cumple $P(x)$. Mientras que en la segunda parte mostramos que todo elemento $y$ distinto a $x$(Blargs y Blurgs) , no cumple $P(y)$. Para la segunda parte, vimos que si $y$ no eran los Blergs, entonces no podían comer fresas.

Nos saltamos un conector, que es el $\nexists$, para demostrar estos casos, es suficiente notar que

$$\nexists x P(x) = \forall x (\neg P(x)) $$

Por ejemplo, para demostrar que «No existen especies de Blorgs que coman los miércoles», solo basta demostrar que todas las especies de Blorgs no comen los miércoles.

Algunos ejemplos de demostraciones con los cuantificadores que utilizan

A continuación mostramos algunos ejemplos de proposiciones y de qué cuantificador hablan ayudados de su escritura como lógica proposicional. No es necesario que entiendas a qué se refiere cada uno, pero sus cuantificadores.

Proposición	Proposición en lógica proposicional
: Para todo $a$ número real, $a \leq \|a\|$ y $-a \leq \|a\|$	Sea $P(a)$ = $a \leq \|a\|$ y $-a \leq \|a\|$: $$\forall a \text{ número real } P(a)$$
El neutro aditivo es único en los números reales .	Sea $P(x)$ = $x$ es neutro aditivo: $$\exists ! x \text{ número real } P(x)$$
Para todo binomio con coeficientes reales (es de la forma $ax^2+b^x+c$ donde $a,b,c$ son números reales), existe solución compleja. *	Sea $P(p,x)$ = $p$ tiene solución compleja $x$: $$\forall p \text{ binomio con coeficientes reales } \exists x (P(p,x)) $$

Notas

*: Esta es una consecuencia de algo que se conoce como el «Teorema fundamental del álgebra», que se usa en un segundo curso de álgebra superior (la continuación de este curso). Solo se utiliza, más no se demuestra, la herramienta necesaria para su demostración, normalmente se puede ver en cursos de hasta el tercer año de una licenciatura en matemáticas.

Más adelante…

Antes de terminar de estudiar estas «formas» de demostrar, vamos a terminar viendo el último conector que intencionalmente nos saltamos, este es la «doble implicación», y hay un motivo para ello, pues comúnmente te vas a encontrar este tipo de demostraciones y verás la técnica que se empleará.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Demuestra que existen Blorgs que no viven dentro del agua.
Demuestra que todos los Blorgs comen al menos una vez a la semana.
Demuestra que existe una única especie de Blorgs que habla con animales con aletas.
Demuestra que no existe una especie de Blorgs que coman los miércoles.

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Demostración de proposiciones con conectores
Siguiente entrada del curso: Problemas de demostraciones con conectores y cuantificadores

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Superior I: Demostración de proposiciones con conectores

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

Hasta ahora hemos visto estrategias directas e indirectas para demostrar proposiciones, pero ahora vamos a pensar qué pasan con aquellas proposiciones que tienen conectores, cómo es que se piensan y las consideraciones que deberemos de tener al momento de hacer alguna de estas.

Pensando en conectores

Hasta ahora hemos pensado en las proposiciones que son del estilo $P \Rightarrow Q$ en donde empezamos con una hipótesis $P$ y mediante una sucesión de deducciones lógicas, llegamos hasta $Q$. Sin embargo en la tarea matemática, no se limita el trabajo a solo proposiciones de este estilo. En esta entrada veremos otros ejemplos de proposiciones a demostrar con otros conectores lógicos.

Recordando conectores

Antes de comenzar, vamos a recordar brevemente los conectores lógicos que hemos visto para entender cómo podríamos demostrar proposiciones que contengan estos. Para empezar, recordemos que la conjunción $P \lor Q$ se cumple siempre que alguna de las dos sean verdaderas.

Por ejemplo,

Proposición: Los blorgs comen frutas o peces.

Demostración: Como dijimos anteriormente, bastará con que cualquier blorg que consideres, coma peces o coma frutas. Pero para esto tenemos que recordar que hay tres tipos de Blorgs: Blargs, Blergs y Blurgs. Entonces tenemos que ver que en cada caso, la afirmación es correcta. Para ello consideremos a un Blorg $x$.

En primer lugar, si $x$ es Blerg, entonces come frutas, por lo que la afirmación se cumple.

Enseguida, si $x$ es un Blarg, también es cierta, pues come peces.

Finalmente, si $x$ es Blurg, también come peces, por lo que la afirmación es correcta.

En cualquiera de los casos, la proposición se cumple.

$\square$

De forma similar, podemos demostrar las proposiciones con una conjunción $P \land Q$ demostrando que se cumplen las dos al mismo tiempo. Por ejemplo,

Proposición: Los Blargs comen animales marinos y comen entre semana.

Demostración: Para probar la proposición, será necesario probar dos cosas: Que los Blargs comen animales marinos, y que los Blargs comen entre semana, es decir que no comen el fin de semana.

Ahora notemos que todos los Blargs comen peces, y estos son animales marinos, entonces se cumple la afirmación de que los Blargs comen animales marinos.

Como es una conjunción, ahora tenemos que demostrar que igual comen entre semana. Para esto, recuerda que cada Blarg come los lunes, y como podrás imaginar, esto significa que comen entre semana, por lo que ya demostramos que «Los Blargs comen animales marinos y comen entre semana».

$\square$

Conectando conectores

Ahora, podemos ir más allá y hacer combinaciones con los conectores, aunque en las proposiciones a veces parezcan un poco complicadas, será necesario analizar detenidamente qué dice la proposición para poder demostrarla. Por ejemplo, piensa en la siguiente proposición:

Proposición: Si un blorg no es amarillo, entonces come los días antes del sábado o tiene amigos de color azul.

Antes de continuar con la demostración, vamos a desmenuzar la oración en sus partes escribiéndola con lógica proposicional. Si consideramos:

$ P(x): x$ no es amarillo,

$ Q(x): x$ no come los días antes del sábado,

$ R(x): x$ tiene amigos de color azul,

entonces la proposición es de la forma

$\forall x (P(x) \Rightarrow (Q(x) \lor R(x))).$

De esta forma ya tenemos un poco más claro qué queremos demostrar. Empezaremos con un Blorg $x$ para el cual la proposición $P(x)$ sea válida y demostraremos que sucede $Q(x)$ o sucede $R(x)$.

Demostración: Sea $x$ un Blorg que no es amarillo. Esto significa que no es un Blarg, entonces tenemos dos casos:

Caso 1: $x$ es un Blerg.

Si $x$ es un Blerg, entonces es amigo de los Blurgs. Y como recordarás, los Blurgs son azules, de esta manera se cumple la proposición.

Caso 2: $x$ es un Blurg.

Si nuestro Blorg es un Blurg, entonces come los viernes, que resulta que son los días antes del sábado. De esta manera la proposición también se cumple.

En cualquiera de los casos, la proposición es válida.

$\square$

Más adelante…

Ya hemos recorrido algunas de las formas de demostraciones que te encontrarás a lo largo de tu viaje matemático, sin embargo aún hay algunas cosas que tendrás que saber antes, como el caso específico de las dobles condicionales y cómo afectan los cuantificadores. Esta última es la que revisaremos en la siguiente entrada. ¿Qué pasa cuando usamos los cuantificadores «existe» o «para todo» dentro de una proposición que queramos demostrar? Esto revisaremos en la siguiente entrada.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Prueba que «Los Blergs no comen los jueves o comen frutas».
Prueba que «Los Blorgs es amarillo, rojo o azul».
Prueba que «Los Blorgs comen los lunes y comen animales marinos o son vegetarianos». Para esto, recuerda que una dieta vegetariana solo excluye alimentos de origen animal.
Escribe con lógica proposicional la proposición: «Si un Blorg come los viernes entonces en su hábitat hay árboles y come animales marinos».
Demuestra que «Si un Blorg come los viernes entonces en su hábitat hay árboles y come animales marinos».

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Problemas introductorios a demostraciones
Siguiente entrada del curso: Demostración de proposiciones con cuantificadores

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Superior I: Demostraciones por reducción al absurdo

Por Guillermo Oswaldo Cota Martínez

2 respuestas

Introducción

Ya hemos empezado a ver algunas estrategias para empezar a demostrar cosas. Ahora veremos una siguiente que es muy común de encontrar, en esta vamos a empezar con una proposición que queremos demostrar, y para hacerlo, supondremos que no es cierta. Puede sonarte que es un poco extraño, pero en esta entrada revisaremos de qué forma esta suposición nos ayudará.

La contradicción

Puede que en tu vida hayas escuchado la palabra contradicción usada en alguno u otro contexto. Podemos decir por ejemplo que una persona se contradice a sí misma cuando dice que es alérgica al camarón después de haberse comido un coctél de camarón. Esto suena poco convincente, ¿no? Pues al decir que alguien es alérgico al camarón sabemos que no puede comer camarón, al mismo tiempo que vemos a la persona haciéndolo. Esta idea va a ser similar en las matemáticas. Pero recuerda que aquí estamos en el lenguaje de las proposiciones.

Definición. Una contradicción es una proposición matemática de la forma $(Q \land \neg Q)$.

Ahora observa la siguiente regla de inferencia:

\begin{array}{rl}
Q \\
\neg Q \\
\hline
\therefore R.
\end{array}

Se puede probar que esta es una inferencia válida. Analiza un poco la regla y piensa: ¿Esto qué significa? Pues observa que en ningún momento aparece el término $R$ en las premisas y sin embargo es una conclusión. En pocas palabras, esto nos quiere decir «De una contradicción puede suceder lo que sea». Es decir, si llegamos a una contradicción, ya nada tiene sentido, pues cualquier cosa sería cierta. Si cambiamos $R$ por «La luna es de queso», podemos concluirlo de una contradicción, y esto no tiene sentido. Es por eso que si en algún momento en las matemáticas llegamos a una contradicción, es que algo está raro. Bajo esta idea funcionará la reducción al absurdo.

Demostración por contradicción

Como hemos dicho en el párrafo anterior, para esta estrategia usaremos la contradicción. Como de esta podríamos llegar a la conclusión de que cualquier proposición es cierta, lo cual no pasa. Entonces la estrategia general en probar una proposición $P$ por reducción al absurdo (o contradicción) es la siguiente:

Suponemos que $P$ es falsa.
Mediante una serie de pasos lógicos exploramos las consecuencias de que $P$ sea falsa.
Llegamos a una contradicción.

En matemáticas las contradicciones nos dicen que hay algo raro, pues sabemos que una proposición no puede ser verdadera y falsa a la vez (recuerda que esto es una contradicción). Entonces el error que hicimos fue suponer que $P$ era falsa, y como no es falsa, tiene que ser verdadera. Veamos un ejemplo para que quede más claro.

Otra forma en que te puedas imaginar la reducción al absurdo es la siguiente:

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

Pues esto nos dice que suponiendo primero que $P$ es verdad y llegando mediante una serie de pasos lógicos que pasa $Q$ y $\neg Q$, entonces es porque en primer lugar $P$ no es verdadera. Piénsalo como mejor te acomodes.

Proposición. Los Blurgs comen a lo más con cuatro días de diferencia.

Demostración. Vamos a hacer esta prueba por contradicción. Como dijimos antes, las pruebas por contradicción se basan en que para demostrar una proposición $P$, se empieza suponiendo $\neg P$, y a partir de ahí ver las consecuencias de este hecho para llegar a una contradicción. Ahora veamos la traducción de esto a nuestra proposición.

$$P = \text{Los Blurgs comen a lo más con cuatro días de diferencia,}$$

$$\neg P = \text{Los Blurgs comen con cinco o más días de diferencia}$$.

Entonces empecemos con $ \neg P$ y veamos qué obtenemos. Ahora, sabemos que $Q =\text {Los blurgs comen los lunes}$ y que $S = \text {Los blurgs comen los viernes}$. Estamos suponiendo que los Blurgs comen con al menos cinco días de diferencia, entonces como $Q$ es verdad, los Blurgs comen los lunes, y eso significaría que no comen los cuatro días siguientes: martes, miércoles jueves y viernes. Lo que significa que $R = \text {Los Blurgs no comen los viernes}$. ¿Eso no es una contradicción? Pues resulta que sí, ya que $\neg S = T$. Lo que quiere decir que a partir de suponer $\neg P$ llegamos a que $S$ es verdad (es un Axioma o costumbre que tienen los Blorgs) ya que estamos diciendo que los Blurgs comen y no comen los viernes. Nuestro error fue suponer que $P$ no era cierta, por lo tanto tiene que ser cierta $P$.

$\square$

Algunos ejemplos famosos de demostraciones por contradicción.

Ahorita estamos y seguiremos hablando del mundo de los blorgs, pero para acercárte un poco más a los ejemplos de estrategias usadas, aquí unos ejemplos en las matemáticas que usan la contradicción para demostrar proposiciones, para fines de este curso no necesitas saber demostrar estas proposiciones, únicamente son ejemplos que podrías checar para entender mejor cómo se utiliza esta estrategia:

La demostración de que el $0$ es el único neutro aditivo en los números reales (es el único número que al sumarlo a otro número resulta el mismo otro número) utiliza esta estrategia, pues supone que el $0$ no es único. Puedes checar la demostración aquí.
En geometría euclideana, existen criterios para decir si dos triángulos son congruentes (son el «mismo» triángulo salvo quizá la reflexión y rotación, es decir hay una forma de rotarlo o reflejarlo para notar que se trata del «mismo» triángulo). Uno de estos se llama el criterio LLA que nos dice que si dos triángulos tienen dos lados que miden lo mismo y comparten un ángulo entonces son congruentes. Una técnica para demostrar esto es con reducción a lo absurdo y supone que el dos lados son iguales junto a un ángulo pero los lados restantes de cada triángulo son distintos. Puedes checar la demostración aquí.

Más adelante…

La siguiente más que estrategia, caso de demostración va a ser cuando tengamos conectores. Estas son las que en las proposiciones a demostrar hay conectores lógicos. Ya hemos visto algunos de estos ejemplos y ahora profundizaremos un poco más en su estructura.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Prueba que $$ \begin{array}{rl} & P \Rightarrow (Q \land \neg Q) \\ \hline \therefore & \neg P \end{array}$$ es una regla de inferencia válida.
Prueba que
\begin{array}{rl}
Q \\
\neg Q \\
\hline
\therefore R
\end{array}.
Es una regla de inferencia válida.
Prueba por contradicción que los blargs no respiran aire.
Prueba por contradicción que los blergs son vegetarianos.

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Demostraciones directas e indirectas
Siguiente entrada del curso: Problemas introductorios a demostraciones

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Superior I: Demostraciones directas e indirectas

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

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, P1\Rightarrow P_2, P_2 \Rightarrow \dots, P_{n-1} \Rightarrow P_{n} $

De donde concluimos 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 algunas observaciones sobre la forma en que demostramos nuestras proposiciones.

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.
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.
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.

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.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

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

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Demostraciones matemáticas (el mundo de los Blorg).
Siguiente entrada del curso: Demostraciones por reducción al absurdo.

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»