3.4: Improbantes
- Page ID
- 113969
La idea de una “desprueba” es realmente solo semántica —para desmentir una afirmación necesitamos probar su negación.
Hasta ahora hemos estado discutiendo bastante las pruebas, pero hemos prestado muy poca atención a un tema realmente enorme. Si las declaraciones que estamos intentando probar son falsas, nunca va a ser posible ninguna prueba. Realmente, un requisito previo para desarrollar una instalación con pruebas es desarrollar un buen “detector de mentiras”. Tenemos que ser capaces de adivinar, o determinar rápidamente, si una declaración es verdadera o falsa. Si se nos da una declaración universalmente cuantificada lo primero que debemos hacer es probarla para algunos elementos aleatorios del universo en el que estamos trabajando. Si sucedemos a través de un valor que satisface las hipótesis de la declaración pero no satisface la conclusión, hemos encontrado lo que se conoce como contraejemplo.
Considere la siguiente declaración sobre enteros y divisibilidad:
\[∀a, b, c ∈ \mathbb{Z}, a| bc \implies a| b ∨ a| c.\]
Esto se expresa como un SCP, por lo que la hipótesis es clara, estamos buscando tres enteros para que el primero divida el producto de los otros dos. En la siguiente tabla, hemos recopilado varios valores para\(a\),\(b\) y\(c\) tal que\(a| bc\).
| \(a\) | \(b\) | \(c\) | \(a| b ∨ a| c ?\) |
|---|---|---|---|
| \ (a\) ">\(2\) | \ (b\) ">\(7\) | \ (c\) ">\(6\) | \ (a| b \) ">\(\text{yes}\) |
| \ (a\) ">\(2\) | \ (b\) ">\(4\) | \ (c\) ">\(5\) | \ (a| b \) ">\(\text{yes}\) |
| \ (a\) ">\(3\) | \ (b\) ">\(12\) | \ (c\) ">\(11\) | \ (a| b \) ">\(\text{yes}\) |
| \ (a\) ">\(3\) | \ (b\) ">\(5\) | \ (c\) ">\(15\) | \ (a| b \) ">\(\text{yes}\) |
| \ (a\) ">\(5\) | \ (b\) ">\(4\) | \ (c\) ">\(15\) | \ (a| b \) ">\(\text{yes}\) |
| \ (a\) ">\(5\) | \ (b\) ">\(10\) | \ (c\) ">\(3\) | \ (a| b \) ">\(\text{yes}\) |
| \ (a\) ">\(7\) | \ (b\) ">\(2\) | \ (c\) ">\(14\) | \ (a| b \) ">\(\text{yes}\) |
Como se señala en la Sección 1.2 el enunciado anterior se relaciona con si a es primo o no. Tenga en cuenta que en la tabla, solo\(a\) aparecen los valores primos de. Este es un indicio bastante amplio. Encuentra un contraejemplo a Conjetura\(3.4.1\).
Puede haber momentos en que la búsqueda de un contraejemplo empiece a sentirse realmente inútil. ¿Pensarías que es probable que una declaración sobre números naturales pueda ser cierta para (más que) los primeros\(50\) números a pero aún así ser falsos?
\(∀n ∈ \mathbb{Z} + n^2 − 79n + 1601\)es primo.
Encuentra un contraejemplo para Conjetura\(3.4.2\)
Oculta dentro de la prueba de Euclides de la infinitud de los primos hay una secuencia. Recordemos que en la prueba deducimos una contradicción al considerar el número\(N\) definido por
\[N = 1 + \prod_{k=1}^{n} p_k. \]
Definir una secuencia por
\[N_n = 1 + \prod_{k=1}^{n} p_k, \]
donde\(\{p_1, p_2, . . . , p_n\}\) están los primeros\(n\) primos reales. Los primeros valores de esta secuencia son:
| \(n\) | \(N_n\) |
|---|---|
| \ (n\) ">\(1\) | \ (N_n\) ">\(1 + (2) = 3\) |
| \ (n\) ">\(2\) | \ (N_n\) ">\(1 + (2 · 3) = 7\) |
| \ (n\) ">\(3\) | \ (N_n\) ">\(1 + (2 · 3 · 5) = 31\) |
| \ (n\) ">\(4\) | \ (N_n\) ">\(1 + (2 · 3 · 5 · 7) = 211\) |
| \ (n\) ">\(5\) | \ (N_n\) ">\(1 + (2 · 3 · 5 · 7 · 11) = 2311\) |
| \ (n\) ">\(⋮\) | \ (N_n\) ">\(⋮\) |
Ahora bien, en la prueba, deducimos una contradicción al señalar que\(N_n\) es mucho mayor que\(p_n\), así que si\(p_n\) es el prime más grande se deduce que no\(N_n\) puede ser primo — pero lo que realmente parece ser el caso (¡solo mira esa tabla!) es que\(N_n\) en realidad es primordial para todos\(n\).
Encuentra un contraejemplo a la conjetura que en sí misma siempre\(1 + \prod^{n}_{k=1} p_k\) es un primo.
Ejercicios:
Encuentre un polinomio que asuma solo valores primos para un rango razonablemente grande de entradas.
Encuentra un contraejemplo para conjeturar\(3.4.1\) usando solo poderes de\(2\).
La suma alternada de factoriales proporciona un interesante ejemplo de una secuencia de enteros.
\(1! = 1 \\ 2! − 1! = 1 \\ 3! − 2! + 1! = 5 \\ 4! − 3! + 2! − 1! = 19 \\ \text{et cetera}\)
¿Son todos primos? (Después de los dos\(1\) primeros.)
Se ha conjeturado que siempre que\(p\) es primo, también\(2^p − 1\) es primo. Encuentra un contraejemplo mínimo.
Verdadero o falso: La suma de dos números irracionales cualesquiera es irracional. Demuestra tu respuesta.
Verdadero o falso: Hay dos números irracionales cuya suma es racional. Demuestra tu respuesta.
Verdadero o falso: El producto de dos números irracionales cualesquiera es irracional. Demuestra tu respuesta.
Verdadero o falso: Hay dos números irracionales cuyo producto es racional. Demuestra tu respuesta.
Verdadero o falso: Siempre que un entero n es un divisor del cuadrado de un entero,\(m^2\), se deduce que\(n\) es un divisor de\(m\) también. (En símbolos,\(∀n ∈ \mathbb{Z}, ∀m ∈ \mathbb{Z}, n | m^2 \implies n | m.)\) Demuestra tu respuesta.
En un ejercicio en la Sección 3.2, probamos que la ecuación cuadrática\(ax^2 + bx + c = 0\) tiene dos soluciones si\(ac < 0\). Encuentra un contraejemplo que demuestre que esta implicación no puede ser reemplazada por una bicondicional.