2.5: Más sobre la cuantificación

Al escribir pruebas matemáticas, no utilizamos explícitamente la representación simbólica de una declaración dada en términos de cuantificadores y conectivos lógicos. Sin embargo, tener esta notación a nuestra disposición nos permite compartimentalizar la naturaleza abstracta de las proposiciones matemáticas y nos proporciona una manera de hablar sobre la estructura general involucrada en la construcción de una prueba.

Definición 2.74. Dos proposiciones cuantificadas son lógicamente equivalentes si tienen el mismo valor de verdad en cada universo del discurso.

Problema 2.75. Consideremos las proposiciones (x ∈ U) (x ² − 4 = 0) y (x ∈ U) (x ² − 2 = 0), donde U es algún universo del discurso.

a) ¿Estas proposiciones tienen el mismo valor de verdad si el universo del discurso es el conjunto de números reales?

b) Proporcionar un ejemplo de un universo de discurso tal que las proposiciones arrojan diferentes valores de verdad.

c) ¿Qué puede concluir sobre la equivalencia lógica de estas proposiciones?

Vale la pena señalar una distinción importante. Considera las proposiciones “Todos los autos son rojos” y “Todos los números naturales son positivos”. Ambas son instancias de la forma lógica (∀x) P (x). Resulta que la primera proposición es falsa y la segunda es verdadera; sin embargo, no tiene sentido atribuir un valor de verdad a la forma lógica. Una forma lógica es un plano para proposiciones particulares. Si tenemos cuidado, tiene sentido hablar de si dos formas lógicas son lógicamente equivalentes. Por ejemplo, (∀x) (P (x) =⇒ Q (x)) es lógicamente equivalente a (∀x) (¬Q (x) =⇒ ¬P (x)) ya que una proposición condicional es lógicamente equivalente a su contrapositiva (ver Teorema 2.39). Para P (x) y Q (x) fijos, estas dos formas siempre tendrán el mismo valor de verdad independientemente del universo del discurso. Si cambias P (x) y Q (x), entonces el valor de verdad puede cambiar, pero las dos formas seguirán de acuerdo.

El siguiente teorema nos dice cómo negar formas lógicas que involucran cuantificadores. Su prueba debe involucrar varios mini argumentos. Por ejemplo, en la Parte (a), necesitará probar que si ¬ (∀x) P (x) es verdadero, entonces (x) (¬P (x)) también es verdadero.

Teorema 2.76. Que P (x) sea predicado en algún universo de discurso. Entonces

(a) ¬ (∀x) P (x) es lógicamente equivalente a (x) (¬P (x));

(b) ¬ (x) P (x) es lógicamente equivalente a (∀x) (¬P (x)).

Problema 2.77. Niéguese cada una de las siguientes frases. Desatender el valor de la verdad y el universo del discurso.

(a) (∀x) (x > 3)

(b) (x) (x es primitivox es par)

(c) Todos los autos son de color rojo.

d) Cada wookiee se llama Chewbacca.

(e) Algunos hippies son republicanos.

(f) Algunas aves no están enojadas.

(g) No todos los videojuegos pudrirán tu cerebro.

(h) Para todos x ∈ N, x ² + x + 41 es primo.

(i) Existe x ∈ Z tal que 1/x < Z.

(j) No existe ninguna función f tal que si f es continua, entonces f no es diferenciable.

Usando el Teorema 2.76 y nuestros resultados previos que involucran cuantificación, podemos negar proposiciones matemáticas complejas trabajando de izquierda a derecha. Por ejemplo, si negamos la falsa proposición

(x ∈ R) (∀y ∈ R) (x + y = 0),

obtenemos la proposición

¬ (x ∈ R) (∀y ∈ R) (x + y = 0),

que es lógicamente equivalente a

(∀x ∈ R) (y ∈ R) (x + y, 0)

y debe ser verdad. Para un ejemplo más complicado, considere la proposición (falsa)

(∀x) [x > 0 =⇒ (y) (y < 0∧xy > 0)].

Entonces su negación

¬ (∀x) [x > 0 =⇒ (y) (y < 0∧xy > 0)]

es lógicamente equivalente a

(x) [x > 0¬ (y) (y < 0∧xy > 0)],

lo que resulta ser lógicamente equivalente a

(x) [x > 0( ∀y) (y ≥ 0xy ≤ 0)].

¿Se pueden identificar los teoremas que se utilizaron en los dos ejemplos anteriores?

Problema 2.78. Negar cada una de las siguientes proposiciones. Desatender el valor de la verdad y el universo del discurso.

(a) (∀n ∈ N) (m ∈ N) (m < n)

(b) Por cada y ∈ R, existe x ∈ R tal que y = x ².

(c) Para todos y ∈ R, si y no es negativo, entonces existe x ∈ R tal que y = x ².

(d) Por cada x ∈ R, existe y ∈ R tal que y = x ².

(e) Existe x ∈ R tal que para todos y ∈ R, y = x ².

(f) Existe y ∈ R tal que para todos x ∈ R, y = x ².

(g) (∀x, y, z ∈ Z) ((xy es par) =⇒ xz es par) =⇒ xz es par)

(h) Existe una persona casada x tal que para todas las personas casadas y, x está casada con y.

Problema 2.79. Consideremos la siguiente proposición en algún universo de discurso.

“Para todos los tontos wobblers x, existe un dinglehopper y tal que si x no es una pepita, entonces y es un doofus”.

Encuentra la negación de esta proposición para que incluya la frase “no es un tonto”.

Problema 2.80. Consideremos la siguiente proposición en algún universo de discurso.

“Si x e y son ambos elegantes, entonces xy no es ingenioso”.

Encuentra lo contrapositivo de esta proposición para que incluya la frase “no snazzy”.

En este punto, deberíamos ser capaces de utilizar nuestra comprensión de la cuantificación para construir contra-ejemplos a proposiciones falsas complicadas y pruebas de proposiciones verdaderas complicadas. Aquí hay algunas estructuras de prueba generales para diversas formas lógicas.

Prueba de Esqueleto 2.81 (Prueba Directa de (∀x) P (x)). Aquí está la estructura general para una prueba directa de la proposición (∀x) P (x). Supongamos que U es el universo del discurso.

Comprobante. [Exponga cualquier suposición inicial.] Dejar x ∈ U.

... [Utilizar definiciones y resultados conocidos.]...

Por lo tanto, P (x) es cierto. Ya que x era arbitrario, para todos x, P (x).

Combinando Skeleton Proof 2.81 con Skeleton Proof 2.48, obtenemos la siguiente prueba de esqueleto.

Prueba de Esqueleto 2.82 (Prueba de (∀x) (A (x) =⇒ B (x))). A continuación se muestra la estructura general para una prueba directa de la proposición (∀x) (A (x) =⇒ B (x). Supongamos que U es el universo del discurso.

Comprobante. [Exponga cualquier suposición inicial.] Dejar x ∈ U. Supongamos A (x).

... [Utilizar definiciones y resultados conocidos para derivar B (x)]...

Por lo tanto, B (x).

Prueba de Esqueleto 2.83 (Prueba de (∀x) P (x) por Contradicción). Aquí está la estructura general para una prueba de la proposición (∀x) P (x) vía contradicción. Supongamos que U es el universo del discurso.

Comprobante. [Exponga cualquier suposición inicial.] En aras de una contradicción, supongamos que existe x ∈ U tal que ¬P (x).

... [Hacer algo para derivar una contradicción.]...

Esto es una contradicción. Por lo tanto, para todos x, P (x) es cierto.

Prueba de Esqueleto 2.84 (Prueba Directa de (x) P (x)). Aquí está la estructura general para una prueba directa de la proposición (x) P (x). Supongamos que U es el universo del discurso.

Comprobante. [Declarar cualquier suposición inicial.]...

... [Usa definiciones, axiomas y resultados previos para deducir que existe una x para la que P (x) es verdadera; o si tienes una x que funcione, solo verifica que sí.]...

Por lo tanto, existe x ∈ U tal que P (x).

Prueba de Esqueleto 2.85 (Prueba de (x) P (x) por Contradicción). A continuación se muestra la estructura general para una prueba de la proposición (x) P (x) vía contradicción. Supongamos que U es el universo del discurso.

Comprobante. [Exponga cualquier suposición inicial.] En aras de una contradicción, supongamos que para todos x ∈ U, ¬P (x).

... [Hacer algo para derivar una contradicción.]...

Esto es una contradicción. Por lo tanto, existe x ∈ U tal que P (x).

Obsérvese que si Q (x) es un predicado para el cual (∀x) Q (x) es falso, entonces un contraejemplo a esta proposición equivale a mostrar (x) (¬Q (x)), lo que puede probarse siguiendo la estructura de Prueba Esqueleto 2.84.

Es importante señalar que a veces tendremos que combinar diversas técnicas de prueba en una sola prueba. Por ejemplo, si quisieras probar una proposición de la forma (∀x) (P (x) =⇒ Q (x)) por contradicción, comenzaríamos asumiendo que existe x en el universo del discurso tal que P (x) y ¬Q (x).

Problema 2.86. Determinar si cada una de las siguientes afirmaciones es verdadera o falsa. Si la afirmación es cierta, probarla. Si la declaración es falsa, proporcione un contraejemplo.

(a) Para todos n ∈ N, n ² ≥ 5.

(b) Existe n ∈ N tal que n ² − 1 = 0.

(c) Existe x ∈ N tal que para todos y ∈ N, y ≤ x.

(d) Para todos x ∈ Z, x ³ ≥ x.

(e) Para todos n ∈ Z, existe m ∈ Z tal que n + m = 0.

(f) Existen números enteros a y b tales que 2a + 7b = 1.

(g) No existen enteros m y n tales que 2m + 4n = 7.

(h) Para todos a, b, c ∈ Z, si a divide bc, entonces a divide b o a divide c.

(i) Para todos a, b ∈ Z, si ab es par, entonces ya sea a o b es par.

Problema 2.87. Explique por qué la siguiente “prueba” no es un argumento válido.

Reclamación. Para todos x, y ∈ Z, si x e y son pares, entonces x + y es par.

“Prueba”. Supongamos x, y ∈ Z tal que x e y son pares. En aras de una contradicción, supongamos que x+y es extraño. Entonces existe k ∈ Z tal que x+y = 2k+1. Esto implica que (x +y) −2k = 1. Vemos que el lado izquierdo de la ecuación es par porque es la diferencia de números pares. No obstante, el lado derecho es impar. Como un número par no puede ser igual a un número impar, tenemos una contradicción. Por lo tanto, x + y es parejo.

A veces es útil dividir el universo del discurso en múltiples colecciones para tratar por separado. Al hacer esto, es importante asegurarse de que sus casos sean exhaustivos (es decir, se ha contabilizado cada elemento posible del universo del discurso). Idealmente, tus casos también serán disjuntos (es decir, no has considerado el mismo elemento más de una vez). Por ejemplo, si nuestro universo de discurso es el conjunto de enteros, podemos considerar por separado enteros pares versus impares. Si nuestro universo de discurso es el conjunto de números reales, podríamos querer considerar números racionales versus irracionales, o posiblemente negativos versus cero versus y positivos. Atacar una prueba de esta manera, a menudo es referido como prueba por los casos (o prueba por agotamiento). Una prueba por casos también puede ser útil cuando se trata de hipótesis que involucran “o”. Obsérvese que el uso de una prueba por los casos se justifica por el Teorema 2.30.

Si decide acercarse a una prueba usando casos, asegúrese de informar al lector que lo está haciendo y organice su prueba de manera sensata. Tenga en cuenta que se debe evitar hacer un análisis de casos si es posible. Por ejemplo, si bien es válido considerar por separado los casos de si a es un entero par versus un entero impar en la prueba del Teorema 2.11, es completamente innecesario. Para probar el siguiente teorema, es posible que desee considerar dos casos.

Teorema 2.88. Para todos n ∈ Z, 3n ² + n + 14 es par.

Demostrar el siguiente teorema demostrando el contrapositivo usando dos casos.

Teorema 2.89. Para todo n, m ∈ Z, si nm es impar, entonces n es impar y m es impar.

Al probar el teorema anterior, probablemente experimentaste algún dejavu. Deberías haber asumido “n es par o m es par” en algún momento de tu prueba. El primer caso es “n es par” mientras que el segundo caso es “m es par”. (Tenga en cuenta que no es necesario manejar el caso cuando tanto n como m son pares ya que los dos casos individuales ya dan el resultado deseado). Las pruebas para ambos casos son idénticas excepto que se intercambian los roles de n y m. En instancias como esta, los matemáticos tienen un atajo. En lugar de escribir dos pruebas esencialmente idénticas para cada caso, simplemente puede manejar uno de los casos e indicar que el caso restante se deduce de una prueba casi idéntica. La forma más rápida de hacerlo es usar la frase, “Sin pérdida de generalidad, asuma.”. Por ejemplo, aquí hay una prueba del Teorema 2.89 que utiliza este enfoque.

Prueba de Teorema 2.89. Demostraremos lo contrapositivo. Deje n, m ∈ Z y supongamos que n es par o m es par. Sin pérdida de generalidad, supongamos que n es parejo. Entonces existe k ∈ Z tal que n = 2k. Eso lo vemos\[nm = (2k)m = 2(km)\].

Dado que tanto k como m son enteros, km es un entero. Esto demuestra que nm es parejo. Hemos demostrado el contrapositivo, y por lo tanto para todos n, m ∈ Z, si nm es impar, entonces n es impar y m es impar.

Obsérvese que no sería apropiado utilizar el enfoque “sin pérdida de generalidad” para combinar los dos casos en la prueba del Teorema 2.88 ya que la prueba del segundo caso no es tan simple como el intercambio de los papeles de los símbolos en la prueba del primer caso.

Hay momentos en que un teorema hará una afirmación sobre la singularidad de un objeto matemático en particular. Por ejemplo, en la Sección 5.1, se le pedirá que demuestre que tanto las identidades aditivas como las multiplicativas (es decir, 0 y 1) son únicas (ver Teoremas 5.2 y 5.3). Como otro ejemplo, el Teorema Fundamental de la Aritmética (ver Teorema 6.17) establece que cada número natural mayor que 1 puede expresarse de manera única (hasta el orden en que aparecen) como producto de uno o más primos. El enfoque típico para probar la singularidad es suponer que potencialmente hay dos objetos con la propiedad deseada y luego mostrar que estos objetos son realmente iguales. Si aborda esto como una prueba por contradicción es cuestión de gustos. Es común utilizar\(∃!\) como abreviatura simbólica de “existe un único.. tal que”.

Prueba de Esqueleto 2.90 (Prueba Directa de (! x) P (x)). Aquí está la estructura general para una prueba directa de la proposición (! x) P (x). Supongamos que U es el universo del discurso.

Comprobante. [Declarar cualquier suposición inicial.]...

... [Usa definiciones, axiomas y resultados previos para deducir que existe una x para la que P (x) es verdadera; o si tienes una x que funcione, solo verifica que sí.]...

Por lo tanto, existe x ∈ U tal que P (x). Ahora, supongamos x1, x2 ∈ U tal que P (x1) y P (x2).

... [Demostrar que x1 = x2.]...

Esto implica que existe una x única tal que P (x).

El siguiente teorema brinda la oportunidad de practicar demostrando singularidad.

Teorema 2.91. Si c, a, r ∈ R tal que c, 0 y r, a/c, entonces existe una x ∈ R única tal que (ax + 1)/(cx) = r.