Archivo de la etiqueta: algebra superior

Nota 15. Relaciones de equivalencia y particiones.

Por Julio César Soria Ramírez

Deja un comentario

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota veremos cómo las relaciones de equivalencia dan lugar a particiones y finalmente concluiremos que toda relación de equivalencia tiene asociada una partición y viceversa, mostrando que dicha correspondencia es una biyección. Con esta nota concluiremos la primera unidad del presente trabajo.

Teorema

Sea $A$ un conjunto, $\mathcal R$ una relación de equivalencia en $A$, entonces $\set{\overline{x}\mid x\in A}$ es una partición de $A$.

Demostración

Sea $A$ un conjunto, $\mathcal R$ una relación de equivalencia en $A$

Por demostrar que:

$\set{\overline{x}\mid x\in A}$ es una partición de $A$.

Vamos a mostrar que el conjunto $\set{\overline{x}\mid x\in A}$ cumple la definición de partición.

i) Por demostrar que $\overline{x}\neq \emptyset$, $\forall x\in A$.

Sea $x\in A$, como $\mathcal R$ es reflexiva $x\sim x$, así $x\in \overline{x}$ y entonces $\overline{x}\neq \emptyset$.

ii) Por demostrar que si $x,y\in A$ son tales que $\overline{x}\neq \overline{y} $, entonces $\overline{x}\cap \overline{y}=\emptyset$.

En la nota anterior mostramos que: $x\sim y\Longrightarrow \overline{x}=\overline{y}$, que es equivalente a: $\overline{x}\neq \overline{y} \Longrightarrow x\nsim y $ (llamada la contrapositiva de la implicación). También mostramos que $x\nsim y \Longrightarrow \overline{x}\cap \overline{y}=\emptyset$. Así, tenemos que:

$ \overline{x}\neq \overline{y} \Longrightarrow x\nsim y $

y

$x\nsim y \Longrightarrow \overline{x}\cap \overline{y}=\emptyset$

Por lo tanto se sigue que:

$\overline{x}\neq \overline{y} \Longrightarrow \overline{x}\cap \overline{y}=\emptyset $.

Así, tenemos lo que queríamos mostrar.

iii) Por demostrar que $\bigcup\limits_{x\in A} \overline{x}=A$

Prueba por doble contención.

$\subseteq$ primera contención.

Sea $z\in \bigcup\limits_{x\in A} \overline{x}$, entonces $z\in \overline{x}=\set{y\in A\mid y\sim x}$ para alguna $x\in A$, en particular $z\in A$. Por lo tanto $ \bigcup\limits_{x\in A} \overline{x}\subseteq A$.

$\supseteq$ segunda contención.

Sea $z\in A$, como $\mathcal R$ es reflexiva $z\sim z$ así $z\in \overline{z}$, concluimos que $z\in \bigcup\limits_{x\in A} \overline{x}$. Por lo tanto $A \subseteq \bigcup\limits_{x\in A} \overline{x}$.

Como se cumplen las tres condiciones para que sea una partición entonces $\set{\overline{x}\mid x\in A}$ es una partición de $A$.

Ejemplos

1. $A=\set{1,2,3,4,5}$

$\mathcal R=\set{(1,1), (2,2), (3,3), (4,4), (5,5), (1,2), (2,1), (1,5), (5,1) (2,5), (5,2) , (3,4),(4,3)}$

$\overline{1}=\set{1,2,5}$

$\overline{3}=\set{3,4}$

$\set{ \overline{1}, \overline{3}}=\set{ \set{1,2,5}, \set{3,4}} $ es la partición inducida por $\mathcal R$.

2. $A=\set{1,2,3,4,5}$

$\mathcal R$ una relación de equivalencia en $A$. Si la partición en $A$ inducida por $\mathcal R$ es:

$ \set{ \set{3}, \set{2,4}, \set{1,5} } $

¿Quién es $\mathcal R$?

Observemos que

$\mathcal R=\set{ (3,3), (2,2), (2,4), (4,4), (4,2), (1,1), (1,5), (5,5), (5,1) }$

es una relación de equivalencia que induce la partición $\set{ \overline{3}, \overline{2}, \overline{1} }=\set{ \set{3}, \set{2,4}, \set{1,5} } $.

Teorema

Sea $A$ un conjunto, consideremos:

$\mathcal R_A=\set{r\mid r \, \,es \, \, una \, \, relación \, \, de \, \, equivalencia }$

$\mathcal P_A=\set{p\mid p \, \,es \, \, una \, \, partición \, \, de \, \, A }$

Existe una biyección entre $\mathcal R_A$ y $\mathcal P_A$.

Demostración

Sea $A$ un conjunto, consideremos:

$\mathcal R_A=\set{r\mid r \, \,es \, \, una \, \, relación \, \, de \, \, equivalencia }$

$\mathcal P_A=\set{p\mid p \, \,es \, \, una \, \, partición \, \, de \, \, A }$

Definimos:

$\psi: \mathcal R_A\to \mathcal P_A$ con

$\psi(r)=\set{\overline{x}^r\mid x\in A}\, \, \, \forall r\in \mathcal R_A$

donde $ \overline{x}^r =\set{y\in A\mid (y,x)\in r} $, es decir $\psi(r)$ es la colección de clases de equivalencia dadas por la relación $r$.

Veamos que $\psi$ es inyectiva.

Sean $r,\rho\in \mathcal R_A$ tales que $\psi(r)=\psi(\rho)$.

Por demostrar que $r=\rho$.

La prueba se hará por doble contención

$\subseteq$ primera contención.

Sea $(a,b)\in r$ entonces por simetría $(b,a)\in r$ y entonces $b\in \overline{a}^r$.

Por otro lado $ \overline{a}^r\in \set{ \overline{x}^r\mid x\in A }=\psi(r)$ que por hipótesis es igual $\psi(\rho)= \set{ \overline{x}^{\rho}\mid x\in A }$ , de manera que $ \overline{a}^r = \overline{c}^{\rho}$ para alguna $c\in A$. Como $b\in \overline{a}^r$, entonces $b\in \overline{c}^{\rho}$, así $(b,c)\in \rho$, y por simetría $(c,b)\in \rho$. También $a\in \overline{a}^r= \overline{c}^{\rho}$, así $(a,c)\in \rho$. Como $(a,c)\in \rho$ y $(c,b)\in \rho$, por transitividad $(a,b)\in \rho$. Por lo tanto $r\subseteq \rho$.

$\supseteq$ segunda contención. Es análoga y se deja como ejercicio al lector.

Concluimos finalmente que $r=\rho$ y así la función $\psi: \mathcal R_A\to \mathcal P_A$ es inyectiva.

Veamos ahora que $\psi$ es suprayectiva.

Sea $p=\set{A_i\mid i\in I}$ una partición de $A$.

Definimos $r$ una relación en $A$ como:

$(x,y)\in r$ si y sólo si existe $i\in I$ tal que $(x,y)\in A_i$.

Ésta es una relación de equivalencia (demuéstralo).

Por demostrar que $\psi(r)=p$, es decir que $\set{\overline{x}^r\mid x\in A}=p$

La prueba es por doble contención.

$\subseteq$ primera contención.

Sea $\overline{a}^r\in \set{ \overline{x}^r\mid x\in A }$.

Por demostrar que $\overline{a}^r\in p$.

Como $A= \bigcup\limits_{i\in I}A_i$ entonces $a\in A_j$ para alguna $j\in I$. De hecho como $p$ es una partición, $A_j$ es el único elemento de $p$ al que pertenece $a$.

Pero

$\overline{a}^r=\set{b\in A\mid (b,a)\in r}=\set{b\in A\mid \exists i\in I \,\, tal \,\, que \,\, b,a\in A_i}=\set{b\in A\mid b\in A_j}=A_j\in p,$ y por lo tanto $\overline{a}^r\in p,$ y así $\psi(r)\subseteq p$.

$\supseteq$ segunda contención.

Sea $A_j\in p$ con $j\in I$. Sabemos que $A_j\neq \emptyset$,entonces podemos considerar $a\in A_j$, y como acabamos de ver en la primera contención, $A_j=\overline{a}^r\in \set{\overline{x}^r\mid x\in A}=\psi(r)$. Así, $p\subseteq \psi(r)$.

Con estas dos contenciones hemos probado que $p=\psi(r)$. De esta forma, dada una partición $p$ existe una relación de equivalencia que bajo $\psi$ da por resultado $p$. Por lo tanto $\psi$ es suprayectiva.

Como $\psi$ es suprayectiva e inyectiva, entonces $\psi$ es biyectiva.

$\square$

Tarea Moral

  1. Encuentra todas las posibles particiones de $\set{3,6,7,9}$, y para cada una de ellas encuentra la relación de equivalencia asociada.
  2. Considera la relación $\mathcal R$ en $\mathbb Z$, dada por: $(a,b)\in \mathcal R$ si y sólo si $4$ divide a $b-a$. Verifica que las distintas clases de equivalencia forman una partición de $\mathbb Z$.
  3. Sea $A=\set{1,2,3,4,5}$ y considera la relación dada por:
    $R=\set{(1,1),(2,3),(3,3),(4,4),(5,5),(2,4),(4,2),(2,5),(5,2),(4,5),(5,4)}$
    Encuentra la partición asociada.

Más adelante

Con esta nota hemos terminado la unidad 1 del curso de Álgebra superior I. En las siguiente nota iniciaremos la unidad 2 donde haremos un estudio de los números naturales a partir de la definición conjuntista.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 14 Familias de conjuntos y particiones.

Nota siguiente. Nota 16. Los números naturales.

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

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

Esta entrada es parte de una serie de notas introductorias sobre técnicas de demostración. En esta entrada se habla sobre demostraciones de proposiciones con conectores. Cada entrada está ligeramente relacionada con las otras. Para entenderlas bien, usamos el siguiente diagrama que recopila cómo se comporta un mundo fantástico llamado Axios, en donde habitan creaturas llamadas Blorgs. Para leer más sobre ello, haz click aquí.

Hasta ahora hemos visto varias estrategias para demostrar: demostaciones directas, demostraciones indirectas y por contradicción. Ahora pensaremos en cómo realizar demostraciones de ciertas afirmaciones cuando hay conectores tanto en nuestras premisas, como en las conclusiones que queremos obtener. Veremos cómo es que se piensa al hacer estas demostraciones y algunas consideraciones que debemos tomar en cuenta.

Recordando conectores

Como breve recordatorio, tenemos los siguientes conectores lógicos:

  • Conjunción $P\land Q$, que es cierta si ambos $P$ y $Q$ lo son.
  • Disyunción $P\lor Q$, que es cierta si alguno de $P$ o $Q$ lo son.
  • Implicación $P\Rightarrow Q$, que es cierta si bien $P$ es falsa, o si $P$ y $Q$ son verdaderas simultáneamente.
  • Doble implicación $P\Leftrightarrow Q$, que es cierta si $P$ y $Q$ tienen el mismo valor de verdad.

En esta entrada veremos qué hacer con las demostraciones que tienen conjunciones y disyunciones. Más adelante hablaremos de las implicaciones y las dobles implicaciones. Los conectores lógicos pueden aparecer como las hipóteis, o como la conclusión de algo que queremos demostrar. Para realizar estas demostraciones, tomaremos en cuenta lo siguente.

  • Si una conjunción $P\land Q$ aparece como hipótesis, entonces podemos suponer tanto que $P$ como $Q$ son verdad.
  • Si una conjunción $P\land Q$ aparece como conclusión, entonces debemos mostrar, quizás por separado, que cada una de $P$ y $Q$ se siguen de las premisas.
  • Si una disyunción $P\lor Q$ aparece como hipótesis, sólo sabemos que $P\lor Q$ es cierta, no tenemos la garantía de que ninguna de ellas en específico sea cierta, solo que alguna lo es. Por ello, debemos separar en casos nuestra demostración, y argumentar por qué la conclusion se sigue tanto cuando $P$ es cierta, como cuando $Q$ es cierta. Esto típicamente llevará a dos o más subdemostraciones.
  • Si una disyunción $P\lor Q$ aparece como conclusión, entonces basta probar a partir de las hipótesis alguna de $P$ o $Q$, la que nos parezca más fácil, para concluir la demostración.

Ejemplos de demostraciones con conjunciones y disyunciones

Veamos algunos ejemplos.

Proposición: Si un Blorg es un Blarg o es un Blurg, entonces come peces.

Demostración: Aquí la disyunción está en la hipótesis. Un Blorg $x$ que cumple la hipótesis cumple que «$x$ es Blarg o $x$ es Blurg». Como no tenemos certeza de cuál de las proposiciones es cierta, debemos hacer casos.

  • Si $x$ es Blarg, entonces uno de los axiomas nos dice que $x$ come peces.
  • Si $x$ es Blurg, entonces otro de los axiomas nos dice que $x$ come peces.

En cualquier caso, concluimos que $x$ come peces.

$\square$

Veamos un ejemplo de la conjunción en la hipótesis.

Proposición. Si un Blorg que come en peces y es amigo de los delfines, entonces es un Blarg.

Demostración. Tomemos $x$ un Blorg que come peces y es amigo de los delfines. Entonces podemos usar la información de ambas proposiciones en la demostración. Como $x$ come peces, entonces $x$ es Blarg o $x$ es Blurg. Como tenemos una disyunción, hay dos posibilidades: que $x$ es Blarg o que $x$ es Blurg. Veremos que $x$ es Blarg. Para ello, procedemos por contradicción, y suponemos que $x$ no es Blarg. Como «$x$ es Blarg o $x$ es Blurg», entonces $x$ es Blurg. Pero entonces $x$ es Blurg y es amigo de los defines. Pero uno de los axiomas es que los Blurg son amigos sólo de los Blergs y los Blargs. ¡Esto es una contradicción! Así, el problema fue suponer que $x$ no es Blarg. Por lo tanto $x$ es Blarg.

$\square$

Veamos un ejemplo más, con una mezcla de conectores.

Proposición. Si un Blorg es Blerg o es Blarg, entonces come los lunes y es amigo de los Blurgs.

Demostración. Otra vez, en la hipótesis tenemos una disyunción. Tomemos un Blorg $x$ que cumple la hipótesis. Entonces «$x$ es Blerg o $x$ es Blarg». Se tienen que hacer casos.

  • Si $x$ es Blerg, entonces como axioma tenemos que $x$ come los lunes. También como axioma tenemos que $x$ es amigo de los Blurgs. Así, tenemos que «$x$ come los lunes y es amigo de los Blurgs.»
  • Si $x$ es Blarg, entonces como axioma tenemos que $x$ come los lunes. También como axioma tenemos que $x$ es amigo de los Blurgs. Así, tenemos que «$x$ come los lunes y es amigo de los Blurgs.»

En cualquier caso, ya mostramos las dos partes que conforman la conjunción de la conclusión. Por lo tanto, en cualquier caso $x$ come los lunes y es amigo de los Blurgs, como queríamos.

$\square$

Hagamos una demostración más.

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 también que demostrar que 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 otras combinaciones de conectores. Aunque al inicio parezca que se tienen enunciados complicados, basta con pensar la proposición en cada uno de sus componentes para pensar qué hacer.

Proposición: Si un Blorg no es verde, entonces come algún día entre jueves y domingo, 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 verde,

$ Q(x): x$ come algún día entre jueves y domingo,

$ 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 verde. 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 un día entre jueves y domingo. 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 conviene que platiquemos. ¿Cómo demostramos proposiciones en las que están involucrados condicionales y cuantificadores? En la siguiente entrada comenzaremos con el caso de los cuantificadores y posteriormente hablaremos sobre los condicionales.

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.

  1. Prueba que «Para cualquier Blorg $x$, si $x$ no es rojo y $x$ no es amigo de los delfines, entonces $x$ come los viernes».
  2. Prueba que «Para cualquier Blorg $x$, o bien $x$ es verde, o bien $x$ es amarillo, o bien $x$ es azul».
  3. Prueba que «Para cualquier Blorg $x$, o bien $x$ es amigo de los animales marinos, o bien $x$ come los viernes, o bien $x$ es rojo».
  4. 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».
  5. Demuestra que «Si un Blorg come los viernes entonces en su hábitat hay árboles y come animales marinos».

Entradas relacionadas

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 contradicción

Por Guillermo Oswaldo Cota Martínez

2 respuestas

Introducción

Esta entrada es parte de una serie de notas introductorias sobre técnicas de demostración. En esta entrada se habla sobre demostraciones por contradicción. Cada entrada está ligeramente relacionada con las otras. Para entenderlas bien, usamos el siguiente diagrama que recopila cómo se comporta un mundo fantástico llamado Axios, en donde habitan creaturas llamadas Blorgs. Para leer más sobre ello, haz click aquí.

Ya hemos empezado a ver algunas estrategias para empezar a demostrar cosas. Ahora veremos una siguiente que es muy común de encontrar: las demostraciones por contradicción. Comenzando con una proposición que queremos demostrar, 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 fórmula proposicional en la cual sin importar la asignación de verdad de las variables proposicionales, siempre se obtiene algo falso.

Un ejemplo muy sencillo es la fórmula proposicional $(P \land \neg P)$. Si $P$ es falso, entonces la conjunción es falsa. Y si $P$ es verdadero, entonces $\neg P$ es falso y entonces también la conjunción es falsa.

Ahora observa la siguiente regla de inferencia:

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

Se puede probar que esta es una inferencia válida (es uno de los ejercicios al final de la entrada). Analiza un poco la regla y piensa: ¿esto qué significa? Observa que en ningún momento aparece el término $Q$ en las premisas y sin embargo es una conclusión. La parte de las premisas de la regla de inferencia sería $P\land \neg P$. En pocas palabras, esto nos quiere decir que «de una contradicción se puede deducir lo que sea». Es decir, si en algún momento llegamos a una contradicción, ya nada tiene sentido, pues cualquier cosa sería cierta. Si cambiamos $Q$ 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án las demostraciones por contradicción.

Demostraciones por contradicción

Hablemos ahora sí de la estrategia de hacer demostraciones por contradicción. Como platicamos en la sección anterior, de una contradicción podemos concluir cualquier cosa. En particular, podemos concluir lo que queremos demostrar. Esto, ¿cómo se ve en pasos específicos que tenemos que hacer? La estrategia general es la siguiente.

  1. Pensemos que de ciertas premisas $Q_1, Q_2, \ldots, Q_n$ queremos llegar a la conclusión $P$.
  2. Supongamos que además de dichas premisas, también tenemos a $\neg P$ como premisa.
  3. A partir de $Q_1,\ldots,Q_n,\neg P$, obtengamos todas las cosas ciertas que podamos, con el objetivo de simultáneamente probar que tanto cierta proposición $R$ como cierta proposición $\neg R$ son ciertas.
  4. Como ya tendremos $R$ y $\neg R$ en nuestras premisas, podremos concluir lo que sea, en particular, $P$.
  5. Otra manera de pensarlo es que en el momento en que hemos encontrado tanto $R$ como $\neg R$. 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). Así, habremos encontrado un problema lógico. Entonces nuestra suposición de que $\neg P$ es verdadera es imposible. Por lo tanto, $P$ es verdadera.

Otra manera en la que en que te puedas imaginar la reducción al absurdo es mediante la validez de la siguiente regla de inferencia (también tendrás que justificarla como uno de los ejercicios):

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

Esto nos dice que si $P$ es falso (es decir, que $\neg P$ es verdad) implica tanto cierta proposición $Q$, como su negación $\neg Q$, entonces en realidad $P$ no puede ser falso, y por lo tanto es verdadero. Piénsalo como mejor te acomodes.

Ejemplo de demostración por contradicción

Hagamos una prueba en el mundo Axios.

Proposición. Para todo Blurg $x$, si $x$ come un cierto día, entonces pasan como mínimo tres días antes de que $x$ vuelva a comer.

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í se ven las consecuencias y se intenta llegar a una contradicción. Ahora veamos la traducción de esto a nuestra proposición.

$P$ = Para todo Blurg $x$, si $x$ come un cierto día, entonces pasan como mínimo tres días antes de que $x$ vuelva a comer.

La negación es (recuerda que la negación de $\forall x: A(x)\Rightarrow B(x)$ es $\exists x: A\land \neg B$):

$\neg P$ = Existe un Blurg $x$ que comió cierto día, y no pasaron como mínimo tres días antes que de $x$ volviera a comer.

Otra manera de escribir esto es

$\neg P$ = Existe un Blurg $x$ que comió cierto día, y pasaron máximo dos días antes que de $x$ volviera a comer.

Entonces empecemos con $ \neg P$ y veamos qué obtenemos. Tomemos dicho Blurg $x$ que existe. Uno de nuestros axiomas dice que $Q =\text {Para todo Blurg $x$, se tiene que $x$ come exactamente los lunes y los viernes}$. Así, la primera vez que $x$ comió fue o lunes, o viernes.

  • Si comió el lunes, entonces como estamos suponiendo $\neg P$, tenemos que $x$ comió máximo el martes o el jueves. Pero esto es $\neg Q$, pues existió un Blurg que no comió exactamente los lunes o viernes. Así, tendríamos $Q$ y $\neg Q$, una contradicción.
  • Si comió el viernes, entonces como estamos suponiendo $\neg P$, tenemos que $x$ comió máximo el sábado, o el domingo. Pero esto es $\neg Q$ también, pues existió un Blurg que no comió exactamente los lunes o viernes. Una vez más tenemos $Q$ y $\neg Q$, una contradicción.

En cualquiera de los casos, llegamos a una contradicción. 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 en Axios y seguiremos en él. Pero para acercárte un poco más a cómo se usa esta estrategia en matemáticas, aquí te compartimos unos ejemplos de demostraciones por contradicción. 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 al suponer que no es único, se llega a una contradicción. 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 LAL que nos dice que si dos triángulos tienen dos lados que miden lo mismo y comparten el ángulo entre esos lados, entonces son congruentes. Una técnica para demostrar esto es con reducción a lo absurdo y supone que dos lados y el ángulo entre ellos son iguales, pero que el lado restante es distinto. De ahí se puede llegar a una contradicción. Puedes checar la demostración aquí.
  • En el estudio de los tipos de números, se usa una prueba por contradicción para mostrar que el número $\sqrt{2}$ es irracional. Si fuera racional, se podría escribir como $\sqrt{2}=\frac{a}{b}$ con $a$ y $b$ enteros positivos que no comparten factores en común. Pero de esa igualdad se llega a $2b^2=a^2$, de donde se puede justificar con algunos pasos que tanto $a$ como $b$ son pares. Así, ¡simultáneamente $a$ y $b$ deberían y no deberían tener factores en común! Esa contradicción muestra la irracionalidad de $\sqrt{2}$.
  • También puedes ver una colección de videos con pruebas por contradicción en el siguiente enlace: Busca una contradicción.

Más adelante…

En las siguientes entradas seguiremos hablando de cómo hacer demostraciones. Más que estrategias generales, serán una guía sobre cómo demostrar proposiciones que involucran conectores lógicos o cuantificadores. 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.

  1. Usa tablas de verdad para ver que $(P\Rightarrow Q) \land (Q\Rightarrow P) \land P \land \neg Q$ es una contradicción.
  2. Prueba que $$ \begin{array}{rl} & P \Rightarrow (R \land \neg R) \\ \hline \therefore & \neg P \end{array}$$ es una regla de inferencia válida.
  3. Prueba que
    \begin{array}{rl}
    P \\
    \neg P \\
    \hline
    \therefore R
    \end{array}
    es una regla de inferencia válida.
  4. Prueba por contradicción que «Para todo Blorg $x$, si $x$ no come fresas, ni come los viernes, entonces $x$ es un Blarg». Como ayuda, la negación es «Existe un Blorg $x$ tal que ni come fresas, ni come los viernes, ni es Blarg». Si no es Blarg, ¿qué casos hay y cómo llegas a una contradicción en cada uno de ellos?
  5. El viernes pasado iba caminando y encontré un Blorg $A$ que estaba platicando con un amigo suyo, un Blorg $B$ el cual estaba comiendo. Luego, el Blorg $B$ se encontró a un amigo suyo que estaba comiendo lo mismo. ¿Tiene sentido mi historia? ¿Qué sucedería si toda mi historia es verdadera?

Entradas relacionadas

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 matemáticas (El mundo de los Blorg)

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

Esta entrada es parte de una serie de notas sobre demostraciones matemáticas. Sin embargo, para llegar a la importancia de demostrar, hablaremos previamente de un pequeño mundo en donde habitan seres fantásticos a quienes les interesa mucho la lógica y para quienes es fundamental poder deducir únicamente verdades. Este lugar lo vistaremos a lo largo de varias entradas y lo que acordemos a partir de ahora será cierto más adelante. Así que presta atención.

El mundo de los Blorgs

Antes de que pienses que te equivocaste de entrada debido al cuento que está por comenzar, déjame decirte que todo está relacionado con la teoría que hemos estado platicando. Sin embargo, antes de comenzar a aplicarla, vamos a conocer a los Blorgs.

Imagina el mundo de los Blorgs. Es un mundo paralelo al nuestro que se puede encontrar en aquel mundo que existe más allá de lo que la esquina del espejo deja ver. Es un lugar que se parece un poco al piso sobre el que estamos, despierta con casi los mismos tonos del alba por la mañana pero con algunas cosas distintas.

Para empezar estamos hablando de un mundo en el que habitan mayoritariamente criaturas llamadas Blorgs. Aquellos que alguna vez los vieron, comentan que curiosamente son pequeñas criaturas parecidas a los conejos. Y con algunas otras descripciones en mente, podríamos empezar a clasificar los Blorgs de acuerdo a distintas características como por ejemplo su dieta, su rutina, dónde viven, etc. Pero se decidió que era mejor clasificarlos según su color, y aquí es donde las cosas se ponen interesantes.

Por un lado están los Blergs, estos son las criaturas rojas que viven por las montañas. Después podemos considerar a los Blargs que son aquellos Blorgs verdes y viven debajo del mar, no son muy sociales pero es lo que hay. Finalmente están los Blurgs que son azules y prefieren vivir en el bosque. Entonces, podemos dividir a los Blorgs en sus razas: Blergs, Blargs y Blurgs. Algo importante que tenemos que decir también: ningún Blorg tiene más de un color.

Quizá sean de color distinto y vivan en lugares diferentes, pero esto no les impide tener algunas cosas en común. Por ejemplo, todos los Blurgs comen pescados, pues tienen un lago cerca de su bosque, y al ser los Blargs marinos, también comen pescados. El hecho de haber vivido tanto tiempo en terreno alto, hizo que los Blergs prefieran cultivar sus cosechas: frutos dulces y verduras siempre comen. Por alguna razón, será costumbre o creencia, todos los Blorgs comen los lunes, es decir, que cada criatura come una vez a la semana. Eso les ha ayudado a no depender tanto de la comida en el día a día. Aunque aquí es donde los Blurgs no coinciden: ellos no esperan tanto y también comen algo los viernes.

La vida siendo Blorg

Tristemente, los Blargs no pueden salir del mar, pues a pesar de ser Blorgs, el salir del agua les despinta lo verde y les quita fuerza. Es por esto que casi no hablan con sus contrapartes terrestres. Por otro lado los Blerg y los Blurg se llevan muy bien. Los Blurgs comparten la madera que tienen con los Blergs y los Blergs comparten los cultivos que hacen con los Blurgs (aunque no para comer, los Blurgs más bien usan los lindos colores de los frutos rojos para pintar).

No está de más decir que todos los Blergs son amigos de todos los Blurgs. Esto hace que los Blargs se sientan más ajenos a ellos, pues aunque sí se llevan con los Blurgs, prefieren juntarse con los delfines que viven junto a ellos. Los blurgs son amistosos con los Blargs y Blergs, y siempre están dispuestos a negociar peces a cambio de paseos a lo largo del mar. Pero nadie se queja, así es la vida siendo un Blorg.

De esta manera, podemos resumir la información que sabemos de los Blorgs en el siguiente diagrama:

Sobre Axios y demostraciones matemáticas

Una cualidad que podemos saber de los Blorgs es que ellos le llaman al lugar en donde viven «Axios» y dentro de ella, no hacen diferencia entre lo que es una característica o costumbre, ellos no tienen una palabra para cada una de ellas. En su lugar usan la palabra «Axioma«* (¿recuerdas qué significa esta palabra?). Esto quiere decir que para los Blargs, ser verdes es un axioma, al igual que para ellos hablar con delfines o comer peces es un axioma.

Así que es natural poder hacer conclusiones a partir de estos Axiomas. Por ejemplo: ¿Qué opinarías si te digo que todos los Blorgs comen peces? ¿O si te digo que todos los Blorgs que viven en montañas comen los lunes? Pues quizá puedas dar respuesta a estas preguntas intuitivamente. Pero, ¿cómo es que nos aseguramos que la respuesta es correcta o no?

En Axios no basta con decir que todos los Blorgs que viven en las montañas comen los lunes. Los Blorgs no entienden la intuición, pero nosotros sí. A ellos hay que convencerlos con demostraciones, a ellos tenemos que explicarles mediante lógica el porqué una proposición sucede. Es decir que si queremos afirmar que todos los Blorgs que viven en las montañas comen los lunes, tenemos que decir paso a paso el porqué es así. Y esto lo lograremos sólo mediante reglas de inferencia válidas. Vamos a anotar esto que acabamos de decir como una definición (¿recuerdas qué era una definición?):

Definición. Una demostración matemática es el uso de pasos lógicos usando reglas de inferencia válidas para llegar de la veracidad de ciertas hipótesis a la veracidad de una conclusión.

La intuición con inferencia

Para introducir un poco más qué van a ser las demostraciones en las matemáticas, vamos a pensar en Legos, aquellos pequeños bloques que encajan unos con otros con los que se pueden armar lo que se te ocurra. Y piensa a las reglas de inferencia como las instrucciones para armar algo.

Imagina que queremos armar un cuarto con una mesa, cama y lámpara con estas piezas. Primero, tendríamos que armar una mesa, para lo cual necesitamos armar las patas y después la superfice. Las reglas de inferencia nos van a ayudar diciéndonos: las patas hay que acomodarlas de cierta manera junto a la superficie para que se haga una mesa. Y una vez construida la mesa, ahora podemos usar otras reglas de inferencia para crear la cama y otras para la lámpara, juntando las tres partes (mesa, cama y lámpara) tendríamos hecho un cuarto.

Así, si quisiéramos «demostrar» cómo se hace un cuarto con estas piezas de Lego, tendríamos que explicar cómo se hace la lámpara, cómo se hace la cama y cómo la mesa. Esto es lo que haremos en matemáticas: construir cosas dando las instrucciones adecuadas. Incluso podríamos ir más allá: Una vez que sabemos cómo construir un cuarto, podríamos también demostrar cómo se hace una cocina y un baño. Entonces si tuviéramos ese conocimiento de cómo se hacen estos tres, podríamos construir una casa. Y después sabiendo cómo se construyen casas, podríamos crear ciudades y países enteros. Pero como todo: un paso a la vez.

Armando piezas con los Blorgs

Nuestras piezas de Lego con los Blorgs van a ser los axiomas. Ahora si le dijeramos a un Blorg que los Blorgs verdes comen peces, no nos creería. Debemos darle una demostración de esto:

Proposición. Los Blorgs verdes comen peces.

Demostración. Para empezar, vamos a notar que es una proposición del tipo «Si $x$ es un Blorg verde, entonces $x$ come peces». Esto es lo que queremos demostrar. Para ello, vamos a ir armando poco a poco el argumento con las piezas que sí conocemos:

  • Usaremos que todos los Blorgs verdes son Blargs. Es decir «si $x$ es un Blorg verde, entonces $x$ es un Blarg»
  • Usaremos que todos los Blargs comen peces. Es decir «si $x$ es un Blarg, entonces $x$ come peces»

En las demostraciones vamos a ir usando cosas que ya conocemos (en este caso los axiomas) para poder ir aplicando pasos lógicos y reglas de inferencia para llegar a la conclusión deseada. Entonces como queremos ver que todos los Blorgs verdes comen peces, entonces resulta natural «agarrar» o «elegir» un Blorg verde y ver que ese Blorg come peces (si pasa con un Blorg verde, pasará para todos los Blorgs verdes pues todos nuestros pasos lógicos aplicarán para todos los Blorgs verdes). Así que empecemos considerando a $x$ un Blorg verde . Sabemos que «si $x$ es un Blorg verde, entonces $x$ es un Blarg» entonces como nuestro $x$ es un Blorg verde, entonces es un Blarg.

Ahora, sabemos que nuestro $x$ es un Blarg, pero además sabemos que «si $x$ es un Blarg, entonces $x$ come peces» entonces también nuestro Blarg come peces. Por lo tanto los Blorgs verdes comen peces.

$\square$

¿Viste cómo es que hicimos la demostración? Si consideramos

  • $ P(x) : x$ es blorg verde,
  • $ Q(x) : x$ es blarg,
  • $ R(x) : x$ come peces,

entonces realmente lo que hicimos fue usar la siguiente regla de inferencia válida:

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

La razón por la que $P\Rightarrow Q$ y $Q\Rightarrow R$ los tomamos como premisas, es porque acordamos que son axiomas. Recuerda que los axiomas los tomamos como verdaderos.

En este caso solo usamos una regla de inferencia. Más veremos cómo se pueden usar varias reglas de inferencia en una misma demostración. Apenas estamos empezando este tema, así que si aún tienes muchas dudas, no te preocupes y vuelve a leer la demostración si es necesario.

Notas

Estas son algunas anotaciones del artículo y no es necesario que las sepas, únicamente son curiosidades o temas por aparte que forman parte de cultura matemática

* Esta palabra viene del griego ἀξίωμα que significa «lo que se considera justo» y de hecho viene de la palabra ἄξιος (áxios) que significa «valioso» y en la antigua grecia se consideraban aquellas cosas que parecían evidentes y no hacía falta justificar.

Más adelante…

Apenas estamos empezando a explicar qué son estas «demostraciones matemáticas». En el mundo de la matemática no hay algo como el recetario de las demostraciones, pero hay ideas o formas de pensar los problemas que te servirán para tener una idea de por dónde empezar a pensar a la hora de demostrar. Así que en las siguientes entradas vamos a ver algunas de estas «formas» de pensar los problemas y lo haremos con ayuda de los Blorgs.

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.

  1. ¿Qué color necesita tener un Blorg para ser amigo de los delfines?
  2. ¿Es cierto que existe un Blorg que coma frutos rojos en viernes?
  3. ¿Qué argumentos lógicos podrías usar para demostrar que todo Blorg rojo come los lunes? ¿Y qué argumentos usarías para demostrar que si un Blorg vive en el mar, entonces no come los viernes? Finalmente, ¿puedes argumentar por que si un Blorg no es Blurg, entonces sus Blorg amigos comen los viernes?
  4. Verifica que

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

es una regla de inferencia válida.

Entradas relacionadas

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»