3.5: Estrategias de prueba

Hay dos formas lógicas elementales que ocurren tan comúnmente en las afirmaciones matemáticas que justifican alguna discusión general.

3.5.1. Declaraciones Universales.

Una forma lógica que es probable que encuentre muy a menudo es\[(\forall x)[H(x) \Rightarrow P(x)] \text {, }\] dónde\(H(x)\) y\(P(x)\) son fórmulas en una variable. Las declaraciones en esta forma se denominan declaraciones universales. Las fórmulas\(H\) y\(P\) se utilizan para caracterizar las propiedades de los objetos matemáticos, de manera que las reivindicaciones en esta forma puedan ser pensadas como declarando:

Si un objeto matemático tiene propiedad\(H\), entonces\(P\) también tiene propiedad.

Esto es particularmente útil si sabemos mucho sobre objetos matemáticos que tienen propiedad\(P\). Debido a que la afirmación que estamos tratando de probar es universal, los ejemplos no bastan para probar tales afirmaciones; el ejemplo que cita podría tener accidentalmente propiedades\(H\) y\(P\). Más bien, las afirmaciones universales deben probarse abstractamente, argumentando que satisfacer una definición o conjunto de propiedades implica la satisfacción de otras propiedades. Esto generalmente requiere evaluar cuidadosamente las definiciones. En la práctica, a menudo lo hacemos asumiendo que tenemos un elemento arbitrario que satisface una definición o supuestos explícitos, y lógicamente derivamos conclusiones adicionales sobre este objeto. Por arbitrario queremos decir que no se nos permite hacer ninguna afirmación sobre el elemento excepto aquellas que se deriven inmediatamente de definiciones, suposiciones explícitas, o que se deriven lógicamente de definiciones y suposiciones explícitas. Dado que el objeto era arbitrario (a excepción de las suposiciones explícitas que hagas al inicio del argumento), las conclusiones que derives sobre el objeto serán verdaderas universalmente para todos los objetos que satisfagan los supuestos.

EJEMPLO 3.15. Supongamos que\(F(x)\) es la fórmula:\[\text { " } x \in \mathbb{N} \text { and } x \text { is a multiple of } 4 . "\] Let\(E(x)\) be the formula:\[\text { " } x \text { is even." }\] Entonces No\[(\forall x)[F(x) \Rightarrow E(x)] .\] basta con observar que 4,8 y 12 son todos parejos. Para argumentar directamente a favor de la afirmación, se argumentaría abstractamente que cualquier objeto que satisfaga\(F(x)\) necesariamente satisface\(E(x)\).

Hay un par de enfoques que uno suele considerar a la hora de probar declaraciones condicionales. Elegir un enfoque es elegir una estrategia para la prueba. Normalmente, se puede hacer funcionar más de una estrategia, pero a menudo una puede ser más simple que las otras.

Las reclamaciones de la forma (3.14) generalmente se abordan de una de las siguientes maneras:

(1) Prueba Directa. Dejar\(x\) ser un objeto para el que se\(H\) sostiene. Al decodificar la propiedad\(H\), es posible que también pueda mostrar directamente esa\(P\) propiedad.\(x\) Al\(x\) ser un objeto arbitrario satisfactorio\(P\), se probará la reivindicación universal.

EJEMPLO 3.17. Probar (3.16) directamente.

Let\(x \in \mathbb{N}\) (tratamos\(x\) como un elemento fijo pero arbitrario de los números naturales). Si\(x=4 n\), entonces\[x=2 \cdot(2 n),\] y por lo tanto es parejo.

EJEMPLO 3.18. Demostrar que cualquier 3 puntos en el plano son colineales o se encuentran en un círculo.

Prueba. Etiquetar los puntos\(A, B, C\). Dejar\(L\) ser la bisectriz perpendicular de\(A B\). Cada punto en\(L\) es equidistante de\(A\) y\(B\).

Dejar\(M\) ser la bisectriz perpendicular de\(B C\). Cada punto en\(M\) es equidistante de\(B\) y\(C\).

Si\(A, B\) y no\(C\) son colineales, las líneas\(L\) y no\(M\) son paralelas, por lo que se cruzan en algún momento\(D\). El punto\(D\) es equidistante de\(A, B\) y\(C\), por lo que estos puntos se encuentran en un círculo centrado en\(D\).

EJEMPLO 3.19. El teorema de Pitágoras se puede afirmar en la forma (3.14). (¿Qué son\(H\) y\(P\) en este caso?) La prueba de Euclides del teorema de Pitágoras es una prueba directa (Elementos I.47 de Euclides).

(2) Prueba Contrapositiva.

A veces es más fácil demostrar que el fracaso de\(P\) implica el fracaso de\(H\). Supongamos que tiene un objeto para el cual\(P\) falla (es decir, asumir\(\neg P\) retenciones del objeto). Derivar que\(H\) debe fallar para el objeto también. En este caso habrás demostrado que\[(\forall x)[\neg P(x) \Rightarrow \neg H(x)] .\] Esto equivale a la reclamación\[(\forall x)[H(x) \Rightarrow P(x)] .\] EJEMPLO 3.20. Probar (3.16) demostrando el contrapositivo.

Vamos\(x \in \mathbb{N}\), y supongamos\(\neg E(x)\), así\(x\) es extraño. Como\(x\) es impar, entonces\(x\) dividido por 4 tiene resto 1 o 3. Entonces,\[x \neq 4 n \text {. }\] Así no\(x\) es un múltiplo de 4.

EJEMPLO 3.21. Demostrar que si\(x\) es un entero y\(x^{2}\) es par, entonces\(x\) es par.

El contrapositivo es la afirmación de que si\(x\) es un entero impar, entonces\(x^{2}\) es impar. Esto lo demostraremos.

Supongamos que\(x\) es impar, así que\(x=2 n+1\) para algún entero\(n\). Entonces\(x^{2}=\)\(4 n^{2}+4 n+1\), así\(x^{2} \equiv 1 \bmod 2\), y por lo tanto\(x^{2}\) es extraño.

(3) Contradicción.

Esta es una prueba en la que demostramos que\(H \wedge \neg P\) es necesariamente falsa. Es decir, asumir que se\(H\) sostiene para un objeto arbitrario y\(P\) falla para ese objeto, y demostrar que esto da lugar a una contradicción. Dado que las contradicciones son lógicamente imposibles, es lógicamente necesario aquello\[\neg(H \wedge \neg P)\] que es proposicionalmente equivalente a\[\neg H \vee P\] o, alternativamente,\[H \Rightarrow P \text {. }\] ya que habremos demostrado que para cualquier sustitución de\(x\), el enunciado \(H \Rightarrow P\)sostiene, habremos mostrado el reclamo universal.

EJEMPLO 3.22. Probar (3.16) por contradicción.

Supongamos que\(x\) es un múltiplo de 4 y eso\(x\) es impar. Dejar\(r\) ser el residuo del\(x\) módulo 2. Ya que\(x\) es un múltiplo de\(4=2 \cdot 2\), tenemos eso\(r \equiv 0 \bmod 2\). Ya que\(r\) es extraño, tenemos eso\(r \equiv 1 \bmod 2\). Esto implica\(0 \equiv 1 \bmod 2\), una contradicción. Por lo tanto, la suposición de\(x\) que había un que era a la vez un múltiplo de 4 e impar es falsa, y así ((3.16) debe ser verdadera. EJEMPLO 3.23. Demostrar que\(\sqrt{2}\) es irracional.

Prueba. Reafirmamos esto como implicación: Si un número es racional, es cuadrado no puede igualar 2. Comenzamos por considerar la estructura lógica del reclamo. Aquí la hipótesis\(H(x)\) es que\(x\) es un número racional, y la conclusión\(P(x)\) es que\(x^{2} \neq 2\). \[(\forall x) H(x) \Rightarrow P(x) .\]Deseamos probar Daremos una prueba por contradicción. Es decir, asumimos que la afirmación es falsa y derivamos una contradicción. Entonces asumimos\[\neg((\forall x) H(x) \Rightarrow P(x)) .\] Esto es lógicamente equivalente a\[(\exists x) H(x) \wedge \neg(P(x)) .\] Volvamos a la prosa matemática ahora que hemos luchado a través de la lógica. Supongamos que\(x\) es un número racional, y asumir también eso\(x^{2}=2\); deseamos derivar una contradicción lógica. Escribir\(x=m / n\), donde\(m\) y\(n\) son enteros distintos de cero que no tienen factores comunes. Entonces\[x^{2}=m^{2} / n^{2}=2,\] así\(m^{2}=2 n^{2}\). Por lo tanto\(m^{2}\) es parejo, así que por el Ejemplo 3.21,\(m\) es parejo. Por lo tanto\(m=2 k\) para algún entero\(k\), y así\[m^{2}=4 k^{2}=2 n^{2} .\] Por lo tanto\(n^{2}=2 k^{2}\) es par, así\(n\) es par. Pero entonces ambos\(m\) y\(n\) son parejos, y así tienen 2 como factor común, lo que contradice la suposición de que\(m / n\) era la forma reducida del número racional\(x\).

Las pruebas contrapositivas y las pruebas por contradicción son muy similares. En efecto, cualquier prueba contrapositiva, eso\(\neg P \Rightarrow \neg H\), automáticamente cede eso\((H \wedge \neg P)\) es imposible. La distinción es más lingüística que lógica. La razón de tener nombres para diferentes estrategias de prueba es brindar orientación al lector para que la prueba sea más fácil de seguir. En el Capítulo 4 veremos otro método poderoso para probar declaraciones universales sobrepasadas\(\mathbb{N}\), a saber, el Principio de Inducción.

3.5.2. Pruebas de Existencia.

Una segunda forma común para una afirmación matemática es una declaración existencial, es decir, una declaración en la forma\[(\exists x) P(x) \text {. }\] Hay tres enfoques comunes para probar afirmaciones existenciales.

(1) Construcción.

Obviamente, la forma más directa de mostrar que algo existe con ciertas propiedades es introducir o construir un objeto con propiedad\(P\). Para las reclamaciones en esta forma, el ejemplo es la prueba, aunque habrá que demostrar que el objeto satisface\(P\), si no es obvio.

EJEMPLO 3.25. Demostrar que existe una función real cuya primera derivada es en todas partes positiva, y cuya segunda derivada es en todas partes negativa.

Prueba. La forma más fácil de hacerlo es anotar una función con estas propiedades. Una de esas funciones es\(f(x)=1-e^{-x}\). El derivado es\(e^{-x}\), que en todas partes es positivo, y el segundo derivado lo es\(-e^{-x}\), que en todas partes es negativo.

(2) Conteo.

A veces se puede establecer la existencia de un objeto mediante un argumento de conteo.

EJEMPLO 3.26. Supongamos que hay 30 alumnos en una clase. Demostrar que al menos dos de ellos comparten la misma última inicial.

PRUEBA. Por cada letra\(A, B, \ldots\) agrupa a todos los alumnos con esa letra como su última inicial. Como solo hay 26 grupos y\(30>26\) estudiantes, al menos un grupo debe tener más que sobre estudiante en él.

El argumento que acabamos de dar se llama el “principio del encasillamiento”, basado en la analogía de poner letras en los encasillados. Si hay más letras que encasillados, entonces algún pigeon-hole debe tener más de una letra. Observe que a diferencia de una prueba constructiva, una prueba de conteo no le dice qué grupo tiene más de un elemento en ella.

Para conocer la espectacular generalización de Cantor del principio del encasillamiento a conjuntos infinitos, ver Capítulo 6.

(3) Contradicción.

Puede ser difícil probar declaraciones existenciales por construcción. Una alternativa es asumir que la afirmación existencial es falsa (que no hay objeto que satisfaga\(P(x)\)). Si es imposible que ningún objeto tenga propiedad\(P\), entonces algún objeto debe. Nuevamente, este enfoque puede no darnos mucha idea de los objetos que tienen propiedad\(P\). Ver por ejemplo Ejercicio 3.27.

EJEMPLO 3.27. Supongamos que todos los puntos del plano son de color rojo o azul. Demostrar que debe haber dos puntos del mismo color exactamente a una unidad de distancia.

Prueba. Supongamos que no los hay. Dibuja un triángulo equilátero del lado 1. Etiquetar sus vértices\(A, B\) y\(C\). Entonces\(A\) y\(B\) deben ser diferentes colores,\(B\) y\(C\) deben ser diferentes colores,\(C\) y\(A\) deben ser diferentes colores. Esto es imposible con solo dos colores para elegir.

Observe que no hemos dicho si hay un par rojo-rojo que esté separado por unidad de distancia, o un par azul-azul que esté separado por unidad de distancia, solo que uno de esos pares debe existir.