A.7: Prueba por contradicción

En primera instancia, la prueba por contradicción es un patrón de inferencia que se utiliza para probar afirmaciones negativas. Supongamos que quieres demostrar que alguna afirmación\(p\) es falsa, es decir, quieres mostrar\(\lnot p\). La estrategia más prometedora es (a) suponer que eso\(p\) es cierto, y (b) demostrar que esta suposición lleva a que algo que sabes sea falso. “Algo que se sabe que es falso” puede ser un resultado que entra en conflicto con —contradice—\(p\) sí mismo, o alguna otra hipótesis de la afirmación general que estás considerando. Por ejemplo, una prueba de “si\(q\) entonces\(\lnot p\)” implica asumir que eso\(q\) es cierto y probar\(\lnot p\) de ello. Si pruebas\(\lnot p\) por contradicción, eso significa asumir\(p\) además de\(q\). Si puedes probar\(\lnot q\) a partir de\(p\), has demostrado que la suposición\(p\) lleva a algo que contradice tu otra suposición\(q\), ya que\(q\) y\(\lnot q\) no puede ser ambas verdaderas. Por supuesto, hay que usar otros patrones de inferencia en su prueba de la contradicción, así como desempaquetar definiciones. Consideremos un ejemplo.

Proposición\(\PageIndex{1}\)

Si\(A \subseteq B\) y\(B = \emptyset\), entonces no\(A\) tiene elementos.

Comprobante. Supongamos\(A \subseteq B\) y\(B = \emptyset\). Queremos demostrar que no\(A\) tiene elementos.

Al tratarse de un reclamo condicional, asumimos el antecedente y queremos probar lo consecuente. El consecuente es: no\(A\) tiene elementos. Podemos hacerlo un poco más explícito: no es el caso de que haya un\(x \in A\).

\(A\)no tiene elementos iff no es el caso de que haya\(x\) tal que\(x \in A\).

Entonces hemos determinado que lo que queremos probar es realmente una afirmación negativa\(\lnot p\), es decir: no es el caso de que haya una\(x \in A\). Para usar la prueba por contradicción, tenemos que asumir la afirmación positiva correspondiente\(p\), es decir, hay una\(x \in A\), y probar una contradicción a partir de ella. Indicamos que estamos haciendo una prueba por contradicción escribiendo “a modo de contradicción, asuma” o incluso simplemente “supongamos que no”, y luego exponer la suposición\(p\).

Supongamos que no: hay un\(x \in A\).

Esta es ahora la nueva suposición que usaremos para obtener una contradicción. Tenemos dos supuestos más: eso\(A \subseteq B\) y aquello\(B = \emptyset\). El primero nos da que\(x \in B\):

Ya que\(A \subseteq B\),\(x \in B\).

Pero ya que\(B = \emptyset\), cada elemento de\(B\) (e.g.,\(x\)) también debe ser un elemento de\(\emptyset\).

Ya que\(B = \emptyset\),\(x \in \emptyset\). Esto es una contradicción, ya que por definición no\(\emptyset\) tiene elementos.

Esto ya completa la prueba: hemos llegado a lo que necesitamos (una contradicción) a partir de los supuestos que hemos establecido, y esto significa que los supuestos no pueden ser todos ciertos. Dado que los dos primeros supuestos (\(A \subseteq B\)y\(B = \emptyset\)) no son impugnados, debe ser el último supuesto introducido (hay un\(x \in A\)) que debe ser falso. Pero si queremos ser minuciosos, podemos deletrear esto.

Así, nuestra suposición de que hay un\(x \in A\) debe ser falso, por lo tanto, no\(A\) tiene elementos por prueba por contradicción. ◻

Toda afirmación positiva equivale trivialmente a una afirmación negativa:\(p\) iff\(\lnot\lnot p\). Por lo que las pruebas por contradicción también pueden utilizarse para establecer afirmaciones positivas “indirectamente”, de la siguiente manera: Para probar\(p\), léelo como la afirmación negativa\(\lnot\lnot p\). Si podemos probar una contradicción a partir de\(\lnot p\), hemos establecido\(\lnot\lnot p\) por prueba por contradicción, y por lo tanto\(p\).

En el último ejemplo, pretendíamos probar una afirmación negativa, es decir, que no\(A\) tiene elementos, y así la suposición que hicimos a efectos de prueba por contradicción (es decir, que hay una\(x \in A\)) fue una afirmación positiva. Nos dio algo con lo que trabajar, es decir, la hipotética\(x \in A\) sobre la que seguimos razonando hasta que llegamos a\(x \in \emptyset\).

Al probar indirectamente una afirmación positiva, la suposición que harías a efectos de prueba por contradicción sería negativa. Pero muy a menudo se puede reformular fácilmente un reclamo positivo como un reclamo negativo, y un reclamo negativo como un reclamo positivo. Nuestra prueba anterior habría sido esencialmente la misma si hubiéramos probado “\(A = \emptyset\)” en lugar de lo negativo consecuente “no\(A\) tiene elementos”. (Por definición de\(=\), “\(A = \emptyset\)” es un reclamo general, ya que desempaqueta a “cada elemento de\(A\) es un elemento de\(\emptyset\) y viceversa”.) Pero se ve fácilmente que es equivalente a la afirmación negativa “no: hay una”\(x \in A\).

Por lo que a veces es más fácil trabajar con ella\(\lnot p\) como suposición que demostrar\(p\) directamente. Incluso cuando una prueba directa es igual de simple o incluso más simple (como en el siguiente ejemplo), algunas personas prefieren proceder indirectamente. Si la doble negación te confunde, piensa en una prueba por contradicción de alguna afirmación como prueba de una contradicción de la afirmación opuesta. Entonces, una prueba por contradicción de\(\lnot p\) es una prueba de una contradicción desde el supuesto\(p\); y la prueba por contradicción de\(p\) es una prueba de una contradicción de\(\lnot p\).

Proposición\(\PageIndex{2}\)

\(A \subseteq A \cup B\).

Comprobante. Eso queremos demostrarlo\(A \subseteq A \cup B\).

De cara a ello, esta es una afirmación positiva: cada también\(x \in A\) está adentro\(A \cup B\). La negación de eso es: algunos\(x \in A\) lo son\(\notin A \cup B\). Por lo que podemos probar la afirmación indirectamente asumiendo esta afirmación negada, y demostrando que lleva a una contradicción.

Supongamos que no, es decir,\(A \nsubseteq A \cup B\).

Tenemos una definición de\(A \subseteq A \cup B\): cada\(x \in A\) es también\(\in A \cup B\). Para entender lo que\(A \nsubseteq A \cup B\) significa, tenemos que usar alguna manipulación lógica elemental en la definición desempaquetada: es falso que cada\(x \in A\)\(\in A \cup B\) es también si hay algo\(x \in A\) que es\(\notin C\). (Este es un lugar donde se quiere tener mucho cuidado: las pruebas intentadas por muchos estudiantes por contradicción fallan porque analizan la negación de una afirmación como “todas las\(A\) s son\(B\) s” incorrectamente). En otras palabras\(A \nsubseteq A \cup B\), si hay\(x\) tal que\(x \in A\) y\(x \notin A \cup B\). A partir de entonces, es fácil.

Entonces, hay\(x \in A\) tal que\(x \notin A \cup B\). Por definición de\(\cup\),\(x \in A \cup B\) iff\(x \in A\) o\(x \in B\). Ya que\(x \in A\), tenemos\(x \in A \cup B\). Esto contradice la suposición de que\(x \notin A \cup B\). ◻

Problema\(\PageIndex{1}\)

Demostrar indirectamente eso\(A \cap B \subseteq A\).

Proposición\(\PageIndex{3}\)

Si\(A \subseteq B\) y\(B \subseteq C\) entonces\(A \subseteq C\).

Comprobante. Supongamos\(A \subseteq B\) y\(B \subseteq C\). Queremos mostrar\(A \subseteq C\).

Procedamos indirectamente: asumimos la negación de lo que queremos etablish.

Supongamos que no, es decir,\(A \nsubseteq C\).

Como antes, razonamos que\(A \nsubseteq C\) iff no todos\(x \in A\) son también\(\in C\), es decir, algunos\(x \in A\) lo son\(\notin C\). No te preocupes, con la práctica ya no tendrás que pensar mucho para desempacar negaciones como esta.

En otras palabras, hay\(x\) tal que\(x \in A\) y\(x \notin C\).

Ahora podemos usar esto para llegar a nuestra contradicción. Por supuesto, tendremos que usar los otros dos supuestos para hacerlo.

Ya que\(A \subseteq B\),\(x \in B\). Ya que\(B \subseteq C\),\(x \in C\). Pero esto contradice\(x \notin C\). ◻

Proposición\(\PageIndex{4}\)

Si\(A \cup B = A \cap B\) entonces\(A = B\).

Comprobante. Supongamos\(A \cup B = A \cap B\). Eso queremos demostrarlo\(A = B\).

El comienzo ahora es rutina:

Asumir, a modo de contradicción, eso\(A \neq B\).

Nuestra suposición para la prueba por contradicción es esa\(A \neq B\). Desde\(A = B\) iff\(A \subseteq B\) an\(B \subseteq A\), obtenemos ese\(A \neq B\) iff\(A \nsubseteq B\) o\(B \nsubseteq A\). (¡Tenga en cuenta lo importante que es tener cuidado al manipular las negaciones!) Para probar una contradicción a partir de esta disyunción, utilizamos una prueba por casos y demostramos que en cada caso, sigue una contradicción.

\(A \neq B\)iff\(A \nsubseteq B\) o\(B \nsubseteq A\). Distinguimos casos.

En el primer caso, asumimos\(A \nsubseteq B\), es decir, para algunos\(x\),\(x \in A\) pero\(\notin B\). \(A \cap B\)se define como aquellos elementos que\(A\) y\(B\) tienen en común, así que si algo no está en uno de ellos, no está en la intersección. \(A \cup B\)está\(A\) junto con\(B\), así que cualquier cosa en cualquiera está también en la unión. Esto nos dice eso\(x \in A \cup B\) pero\(x \notin A \cap B\), y de ahí eso\(A \cap B \neq B \cap A\).

Caso 1:\(A \nsubseteq B\). Entonces para algunos\(x\),\(x \in A\) pero\(x \notin B\). Desde\(x \notin B\) entonces\(x \notin A \cap B\). Ya que\(x \in A\),\(x \in A \cup B\). Entonces,\(A \cap B \neq B \cap A\), contradiciendo la suposición de que\(A \cap B = A \cup B\).

Caso 2:\(B \nsubseteq A\). Entonces para algunos\(y\),\(y \in B\) pero\(y \notin A\). Como antes, tenemos\(y \in A \cup B\) pero\(y \notin A \cap B\), y así\(A \cap B \neq A \cup B\), otra vez contradictorios\(A \cap B = A \cup B\). ◻