2.3: Técnicas para Demostrar Proposiciones Condicionales

Cada uno de los teoremas que probamos en la Sección 2.1 son ejemplos de proposiciones condicionales. No obstante, algunas de las declaraciones fueron disfrazadas como tales. Por ejemplo, el Teorema 2.3 afirma, “La suma de dos enteros consecutivos es impar”. Podemos redefinir este teorema como, “Si n ∈ Z, entonces n + (n + 1) es impar”.

Problema 2.47. Reword Teorema 2.7 para que se lea explícitamente como una proposición condicional.

Cada una de las pruebas que usted produjo en la Sección 2.1 tenía el mismo formato, al que nos referimos como prueba directa.

Prueba de Esqueleto 2.48 (Prueba de A =⇒ B por prueba directa). Si quieres probar la implicación A =⇒ B a través de una prueba directa, entonces la estructura de la prueba es la siguiente.

Comprobante. [Exponga cualquier suposición inicial.] Supongamos que A.

... [Utilizar definiciones y resultados conocidos para derivar B]...

Por lo tanto, B.

Tómate unos minutos para revisar las pruebas que escribiste en la Sección 2.1 y ver si puedes presenciar la estructura de Prueba Esqueleto 2.48 en tus pruebas.

El resultado del Teorema 2.39 es que si quieres probar una proposición condicional, puedes probar su contrapositiva en su lugar. A este enfoque se le llama prueba por contraposición.

Prueba de Esqueleto 2.49 (Prueba de A =⇒ B por contraposición). Si quieres probar la implicación A =⇒ B demostrando su contrapositivo ¬B =⇒ ¬A en su lugar, entonces la estructura de la prueba es la siguiente.

Comprobante. [Exponga cualquier suposición inicial.] Utilizaremos una prueba por contraposición.

Supongamos ¬B.

... [Utilizar definiciones y resultados conocidos para derivar ¬A]...

Por lo tanto, ¬A. hemos demostrado lo contrapositivo, y de ahí si A, entonces B.

Se han introducido los símbolos lógicos ¬,, ⇒, y ⇒, ya que proporciona una manera conveniente de discutir la formalidad de la lógica. Sin embargo, al escribir pruebas matemáticas, debes evitar usar estos símbolos.

Problema 2.50. Considera la siguiente declaración:

Si x ∈ Z tal que x2 es impar, entonces x es impar.

Los artículos a continuación se pueden ensamblar para formar una prueba de esta declaración, pero actualmente están fuera de servicio. Póngalos en el orden adecuado.

1. Supongamos que x es un número entero par.
2. Utilizaremos una prueba por contraposición.
3. Así, x ² es dos veces un número entero.
4. Desde x = 2k, tenemos ese x ² = (2k) ² = 4k ².
5. Dado que k es un número entero, 2k ² también es un número entero.
6. Por la definición de par, hay un entero k tal que x = 2k.
7. Hemos demostrado lo contrapositivo, y de ahí la afirmación deseada es cierta.
8. Supongamos x ∈ Z.
9. Por la definición de entero par, x ² es un entero par.
10. Observe que x2 = 2 (2k ²).

Demostrar los dos teoremas siguientes demostrando el contrapositivo de la declaración dada.

Teorema 2.51. Si n ∈ Z tal que n ² es par, entonces n es par.

Teorema 2.52. Si n, m ∈ Z tal que nm es par, entonces n es par o m es par.

Supongamos que queremos probar alguna proposición P (que podría ser algo así como A =⇒ B o incluso más complicada). Un enfoque, llamado prueba por contradicción, es asumir ¬P y luego deducir lógicamente una contradicción de la forma Q¬Q, donde Q es alguna proposición. Como esto es absurdo, la suposición ¬P debió haber sido falsa, entonces P es verdad. La parte complicada de una prueba por contradicción es que no suele ser obvio cuál debería ser la afirmación Q.

Prueba Esqueleto 2.53 (Prueba de P por contradicción). Así es como se ve la estructura general para una prueba por contradicción si estamos tratando de probar la proposición P.

Comprobante. [Exponga cualquier suposición inicial.] En aras de una contradicción, asuma ¬P.

... [Utilizar definiciones y resultados conocidos para derivar alguna Q y su negación ¬Q.]...

Esto es una contradicción. Por lo tanto, P.

La prueba por contradicción puede ser útil para probar declaraciones de la forma A =⇒ B, donde ¬B es más fácil de “tener en tus manos”, porque ¬ (A =⇒ B) es lógicamente equivalente a A ¬B (ver Corolario 2.41).

Prueba Esqueleto 2.54 (Prueba de A =⇒ B por contradicción). Si quieres probar la implicación A =⇒ B a través de una prueba por contradicción, entonces la estructura de la prueba es la siguiente.

Comprobante. [Exponga cualquier suposición inicial.] En aras de una contradicción, asumamos A y ¬B.

... [Utilizar definiciones y resultados conocidos para derivar alguna Q y su negación ¬Q.]...

Esto es una contradicción. Por lo tanto, si A, entonces B.

Problema 2.55. Supongamos que x ∈ Z. Considere la siguiente proposición: Si x es impar, entonces 2 no divide x.

a) Demostrar el contrapositivo de esta afirmación.

b) Demostrar la declaración utilizando una prueba por contradicción.

Demostrar el siguiente teorema a través de una prueba por contradicción. Después, considere las dificultades que uno podría encontrar al tratar de probar el resultado de manera más directa. La afirmación dada no es cierta si reemplazamos N por Z. ¿Ves por qué?

Teorema 2.56. Supongamos que x, y ∈ N. Si x divide y, entonces x ≤ y.

A menudo, una proposición condicional puede probarse a través de una prueba directa y mediante el uso de una prueba por contradicción. La mayoría de los matemáticos consideran que una prueba directa es más elegante que una prueba por contradicción. Al acercarse a la prueba de una proposición condicional, debe esforzarse por obtener una prueba directa. En general, si estás intentando probar A =⇒ B usando una prueba por contradicción y terminas con ¬B y B (lo que produce una contradicción), entonces esto es evidencia de que una prueba por contradicción era innecesaria. Por otro lado, si

terminas con ¬Q y Q, donde Q no es lo mismo que B, entonces una prueba por contradicción es un enfoque razonable. necesitamos probar ambos

A la luz del Teorema 2.29, si queremos probar un bicondicional de la forma A ⇒ B, A =⇒ B y B =⇒ A. Siempre debes dejar claro al lector cuando estés probando cada implicación. Un enfoque es etiquetar cada subprueba con “(=⇒)” y “(=)” (incluyendo los paréntesis), respectivamente. Ocasionalmente, descubrirá que la prueba de una implicación es exactamente la inversa de la prueba de la otra implicación. Si este sucede, puede omitir escribir dos subpruebas y simplemente escribir una sola prueba que encadene cada paso usando bicondicionales. Tales pruebas casi siempre serán más cortas, pero puede ser difícil escribir de manera elocuente. Siempre es una apuesta segura escribir una subprueba separada para cada implicación.

Al probar cada implicación de un bicondicional, puede optar por utilizar una prueba directa, una prueba por contraposición o una prueba por contradicción. Por ejemplo, podrías probar la primera implicación usando una prueba por contradicción y una prueba directa para la segunda implicación.

El siguiente teorema brinda la oportunidad de adquirir cierta experiencia con la redacción de pruebas de declaraciones bicondicionales.

Teorema 2.57. Dejar n ∈ Z. Entonces n es par si y solo si 4 divide n ².