3.1: Pruebas directas de declaraciones universales
- Page ID
- 113978
Si forma el producto de números\(4\) consecutivos, el resultado será uno menos que un cuadrado perfecto. ¡Pruébalo!
\(1 · 2 · 3 · 4 = 24 = 5^2 − 1\)
\(2 · 3 · 4 · 5 = 120 = 11^2 − 1\)
\(3 · 4 · 5 · 6 = 360 = 19^2 − 1\)
¡Siempre funciona!
Los tres cálculos que hemos realizado anteriormente constituyen un argumento inductivo a favor del resultado. Si te gusta podemos probar un montón de ejemplos adicionales,
\(13 · 14 · 15 · 16 = 43680 = 209^2 − 1\)
\(14 · 15 · 16 · 17 = 571200 = 239^2 − 1\)
pero realmente, no importa cuántos ejemplos produzcamos, no hemos probado la afirmación —acabamos de dar pruebas.
Generalmente, lo primero que hay que hacer para probar una afirmación universal como esta es reformularla como condicional. La sentencia resultante es una Declaración Condicional Universal o un SCP. El motivo para dar este paso es que entonces las hipótesis quedarán claras —forman el antecedente de la UCS—. Entonces, si bien realmente no habrás avanzado en la prueba tomando este consejo, al menos sabrás qué herramientas tienes a mano. Tomando el ejemplo con el que empezamos, y reformulándolo como un SCP obtenemos
\[∀a, b, c, d ∈ Z,(a,b,c,d \text{ consecutive}) \implies ∃k ∈ Z, a·b·c·d = k^2 − 1\]
El antecedente del SCP es ese\(a\),\(b\),\(c\) y\(d\) debe ser consecutivo. Al concentrar nuestra atención en lo que significa ser consecutivos, debemos darnos cuenta rápidamente de que la forma original en que pensamos del problema implicaba un arenque rojo. No necesitamos tener variables para los cuatro números; debido a que son consecutivos, a determina de manera única los otros tres. Por último, tenemos una versión de la declaración que nos gustaría probar que debería prestarse a nuestros esfuerzos de prueba.
\[∀a ∈ \mathbb{Z}, ∃k ∈ \mathbb{Z}, a(a + 1)(a + 2)(a + 3) = k^2 − 1.\]
En este ejemplo simplista, lo único que tenemos que hacer es llegar a un valor para\(k\) dado que sabemos lo que\(a\) es. Es decir, una “prueba” de esta afirmación implica hacer algo de álgebra.
Sin más preámbulos.
- Prueba
-
Supongamos que\(a\) es un entero particular pero arbitrariamente elegido. Considere el producto de los números enteros\(4\) consecutivos,\(a\),\(a + 1\),\(a + 2\) y\(a + 3\). Nos gustaría demostrar que este producto es uno menos que el cuadrado de un entero\(k\). Déjalo\(k\) ser\(a^2 + 3a + 1\).
Primero, tenga en cuenta que
\[a(a + 1)(a + 2)(a + 3) = a^4 + 6a^3 + 11a^2 + 6a.\]
Entonces, tenga en cuenta que
\[k^2 − 1 = (a^2 + 3a + 1)^2 − 1 = (a^4 + 6a^3 + 11a^2 + 6a + 1) − 1 = a^4 + 6a^3 + 11a^2 + 6a.\]
Q.E.D.
Ahora bien, si seguiste el álgebra anterior, (ninguno de los cuales fue particularmente difícil) la prueba se erige como un argumento completamente válido que muestra la verdad de nuestra proposición, ¡pero esto es muy insatisfactorio! Todo el trabajo real se ocultó en una pequeña frase descarada: “Let\(k\) be”\(a^2 + 3a + 1\). ¿De dónde\(k\) viene ese valor particular de la Tierra? Es de esperar que la respuesta a esa pregunta te convenza de que existe una gran diferencia entre idear una prueba y escribir una. Una buena prueba a veces puede ser algo parecida a una buena demostración de magia, un mago no revela el funcionamiento interno de su truco, ¡tampoco debe un matemático sentirse culpable por dejar fuera algunos de los detalles detrás de la obra! Diablos, hay muchas veces en las que solo tienes que adivinar algo, pero si tu conjetura funciona, puedes escribir una prueba perfectamente correcta.
Al idear la prueba anterior, multiplicamos los números consecutivos y luego nos dimos cuenta de que habríamos terminado si pudiéramos encontrar un polinomio en un cuyo cuadrado estaba\(a^4 + 6a^3 + 11a^2 + 6a + 1\). Ahora, obviamente, vamos a necesitar un polinomio cuadrático, y como el término principal es\(a^4\) y el término constante es\(1\), debería ser de la forma\(a^2 + ma + 1\). Al cuadrar esto da\(a^4 + 2ma^3 + (m^2 + 2)a^2 + 2ma + 1\) y comparar ese resultado con lo que queremos, rápidamente nos damos cuenta de que sería mejor\(m\) que fuera\(3\). ¡Entonces no fue magia después de todo!
Este parece un buen momento para hacer un comentario sobre la aritmética polinómica. Muchas personas se dan por vencidas (o van a buscar un sistema de álgebra computacional) cuando tratan con productos de algo más grande que binomios. Esto es una lástima porque existe un método fácil usando una tabla para realizar tales multiplicaciones. A modo de ejemplo, al idear la prueba previa que necesitábamos para conformar el producto\(a(a + 1)(a + 2)(a + 3)\), ahora podemos usar la ley distributiva o la infame regla F.O.I.L para multiplicar pares de estos, pero aún necesitamos multiplicar\((a^2 + a)\) con\((a^2 + 5a + 6)\). Crear una tabla que tenga los términos de estos dos polinomios como sus encabezados de fila y columna.
| \(a^2\) | \(5a\) | \(6\) | |
|---|---|---|---|
| \(a^2\) | \ (a^2\) "> | \ (5a\) "> | \ (6\) "> |
| \(a\) | \ (a^2\) "> | \ (5a\) "> | \ (6\) "> |
Ahora, rellene las entradas de la tabla multiplicando los encabezados de fila y columna correspondientes.
| \(a^2\) | \(5a\) | \(6\) | |
|---|---|---|---|
| \(a^2\) | \ (a^2\) ">\(a^4\) | \ (5a\) ">\(5a^3\) | \ (6\) ">\(6a^2\) |
| \(a\) | \ (a^2\) ">\(a^3\) | \ (5a\) ">\(5a^2\) | \ (6\) ">\(6a\) |
Finalmente sumar todas las entradas de la tabla, combinando cualquier término similar.
Debe tener en cuenta que la regla F.O.I.L es solo un mnemotécnico para el caso cuando la tabla tiene\(2\) filas y\(2\) columnas.
Bien, volvamos a hacer pruebas. Vamos a hacer muchas pruebas que involucran los conceptos de teoría elemental de números por lo que, como conveniencia, todas las definiciones que se hicieron en el Capítulo 1 se reúnen en la siguiente tabla.
| Nombre | Definición |
|---|---|
| Incluso | \(∀n \in \mathbb{Z}\),\(n\) es par\ (\ iff kz, n=2k\) |
| impar | \(∀n \in \mathbb{Z}\),\(n\) es impar\(\iff ∃k∈Z,n=2k+1\) |
| Divisibilidad | \(∀n \in \mathbb{Z}\),\(∀ d>0 \in \mathbb{Z}\),\(d|n \iff ∃k∈\mathbb{Z},n=kd\) |
| Piso | \(∀x \in \mathbb{R}\),\(y=⌊x⌋ \iff y∈\mathbb{Z}∧y≤x<y+1\) |
| Techo | \(∀x \in \mathbb{R}\),\(y=⌈x⌉ \iff y∈\mathbb{Z}∧y−1<x≤y\) |
| Teorema del cociente-resto, Div y Mod | \(∀n, d>0 \in \mathbb{Z}\),\(∃!q,r∈\mathbb{Z},n=qd+r∧0≤r<d n \text{ div } d=q n \text{ mod } =r\) |
| Prime | \(∀p \in \mathbb{Z}\),\(p\) es primo\(\iff (p>1)∧(∀x,y∈\mathbb{Z}^+,p=xy \implies x=1∨y=1) \) |
En esta sección, nos preocupan las pruebas directas de declaraciones universales. Tales declaraciones vienen en dos sabores: los que parecen involucrar condicionales, y los que no:
Cada primo mayor que dos es impar.
versus
Para todos los enteros\(n\), si\(n\) es un primo mayor que dos, entonces\(n\) es impar.
Estas dos formas se pueden transformar fácilmente una en otra, por lo que siempre nos concentraremos en esta última. Una prueba directa de un SCP siempre sigue una forma conocida como “generalizar a partir del particular genérico”. Estamos tratando de probar que ∀x ∈ U, P (x) =⇒ Q (x). El argumento (en esquema esquelético) se verá así:
Prueba: Supongamos que a es un elemento particular pero arbitrario de\(U\) tal que\(P(a)\) sostiene.
Por lo tanto,\(Q(a)\) es cierto.
Así lo hemos demostrado para todos\(x\) en\(U\),\(P(x) \implies Q(x)\).
Q.E.D.
Bien, entonces este esquema es bastante malo. Te dice como empezar y terminar una prueba directa, pero esos odiosos punto-punto-puntos-en el medio son donde tiene que ir todo el trabajo real. Si pudiera decirte (incluso en bosquejo) cómo rellenar esos puntos, eso significaría que la prueba matemática no es realmente una actividad muy interesante para participar. Rellenar esos puntos a veces (raramente) será obvio, más a menudo será extremadamente desafiante; requerirá gran creatividad, mucha concentración, recurrirás a todas tus experiencias matemáticas anteriores, y lo más probable es que experimentes cierto grado de angustia. Solo recuerda que tu sentido de logro es proporcional a la dificultad de los acertijos que intentas. Entonces intentemos otro..
En la Tabla 3.1.1, una de las nociones muy prácticas definidas es la del piso de un número real.
\[y = \lfloor x \rfloor \iff (y ∈ \mathbb{Z} ∧ y ≤ x < y + 1).\]
Existe una triste tendencia a que las personas apliquen reglas viejas en situaciones nuevas solo por una similitud casual en la notación. Los corchetes utilizados en la anotación de la función floor se ven muy similares a los paréntesis ordinarios, por lo que a menudo se propone la siguiente “regla”
\[\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor\]
Encuentra un contraejemplo a la “regla” anterior.
Lo que es (quizás) sorprendente es que si uno de los números involucrados es un entero entonces la “regla” realmente funciona.
\[∀x ∈ \mathbb{R}, ∀n ∈ \mathbb{Z}, \lfloor x + n \rfloor = \lfloor x \rfloor + \lfloor n \rfloor\]
Dado que el piso de un entero es ese entero, podríamos reafirmar esto como\(\lfloor x+n \rfloor = \lfloor x \rfloor + n\).
Ahora, intentemos reformular este teorema como un SCP: Si\(x\) es un número real y n es un entero, entonces\(\lfloor x + n \rfloor = \lfloor x \rfloor + n\). Esto es malo... parece que las únicas hipótesis que podemos usar involucran qué tipo de números\(x\) y\(n\) son —nuestras hipótesis no son particularmente potentes. Sus próximos aliados más útiles en la construcción de pruebas son las definiciones de los conceptos involucrados. La cantidad\(\lfloor x \rfloor\) aparece en el teorema, vamos a hacer uso de la definición:
\[a = \lfloor x \rfloor \iff a ∈ \mathbb{Z} ∧ a ≤ x < a + 1.\]
La única otra función floor que aparece en el enunciado del teorema (quizás aún más prominente) es\(\lfloor x + n \rfloor\), aquí, la definición que nos da
\[b = \lfloor x + n \rfloor \iff b ∈ Z ∧ b ≤ x + n < b + 1.\]
Estas definiciones son nuestras únicas herramientas disponibles por lo que sin duda tendremos que hacer uso de ellas, y es importante notar que eso es algo bueno; las definiciones nos permiten trabajar con algo bien entendido (las desigualdades que aparecen dentro de ellas) en lugar de con algo nuevo y relativamente sospechoso ( la notación del piso). Armar la prueba de esta afirmación es un ejercicio de mirar fijamente las dos definiciones anteriores y señalar cómo una se puede convertir en la otra. También es un testimonio del poder de nombrar las cosas.
- Prueba
-
Supongamos que\(x\) es un número real particular pero arbitrario y que\(n\) es un entero particular pero arbitrario. Vamos\(a = \lfloor x \rfloor\). Por la definición de la función floor se deduce que a es un entero y\(a ≤ x < a + 1\). Al\(n\) sumar a cada una de las partes de esta desigualdad deducimos una nueva (e igualmente válida) desigualdad,\(a + n ≤ x + n < a + n + 1\). Obsérvese que\(a + n\) es un entero y la desigualdad anterior junto con este hecho constituyen precisamente la definición de\(a + n = \lfloor x + n \rfloor\). Finalmente, recordando que\(a = \lfloor x \rfloor\) (por suposición), y reescribiendo, obtenemos el resultado deseado
\[\lfloor x + n \rfloor = \lfloor x \rfloor + n.\]
Q.E.D.
Como hemos visto en los ejemplos presentados en esta sección, llegar a una prueba a veces puede implicar un poco de ingenio. Pero, a veces, hay una especie de enfoque de “sigue tu nariz” que te permitirá idear un argumento válido sin mostrar necesariamente ningún gran salto de genio! Aquí hay algunos consejos sobre la redacción de pruebas:
- Antes que nada, determine con precisión qué hipótesis puede utilizar.
- Anote las definiciones de cualquier cosa en el enunciado del teorema.
- Hay 26 letras a tu disposición (y aún más si sabes griego) (¡y siempre puedes lanzar subíndices!) no seas tacaño con las letras. El error más asqueroso que puedes cometer es usar la misma variable para dos cosas diferentes.
- Por favor, escriba primero un borrador. ¡Escribe dos borradores! Aunque puedas escribir una prosa hermosa y lúcida en la primera vuelta, no volará a la hora de organizar una prueba.
- Se supone que las declaraciones en una prueba son afirmaciones lógicas. Eso significa que deben ser booleanos (declaraciones que son verdaderas o falsas). Una expresión algebraica por sí sola no cuenta, una desigualdad o una igualdad sí.
- No digas “si” cuando te refieres a “desde”. ¡De veras! Si empiezas una prueba sobre números racionales así:
Prueba: Supongamos que\(x\) es un número racional particular pero arbitrario. Si\(x\) es un número racional, se deduce de eso.
la gente te va a mirar gracioso. ¿De qué sirve suponer que eso\(x\) es racional, entonces actuar como si estuvieras en duda de ese hecho escribiendo “si”? Te refieres a “desde”.
- Marque el principio y el final de sus pruebas como una pista para sus lectores. En este libro, comenzamos una prueba escribiendo “Prueba:” en cursiva y terminamos cada prueba con la abreviatura Q.E.D. 1
Cerraremos esta sección con una palabra sobre axiomas. Los axiomas en cualquier área dada de las matemáticas son tus herramientas más fundamentales. Los axiomas no necesitan ser probados, ¡se supone que solo debemos aceptarlos! Un problema muy común para los escritores principiantes de pruebas es decir la diferencia entre afirmaciones que son axiomáticas y declaraciones que requieren alguna prueba. Por ejemplo, en los ejercicios para esta sección, hay un problema que nos pide probar que la suma de dos números racionales es racional. ¿No parece esto que podría ser uno de los axiomas de los números racionales? ¿De verdad es algo que se puede probar? Bueno, sabemos cómo funciona el proceso de sumar números racionales: colocamos las fracciones sobre un denominador común y luego solo agregamos numeradores. ¿Ves cómo sumar fracciones realmente descansa en nuestra capacidad de sumar los numeradores (que son enteros)? Entonces, al hacer ese ejercicio puedes usar el hecho (de hecho, necesitarás usar el hecho) de que la suma de dos enteros es un entero. Entonces, ¿qué tal esa declaración? ¿Es necesario probar que sumar enteros produce un entero? De hecho, es necesario ya que la estructura de los enteros descansa sobre una base conocida como los axiomas de Peano para los naturales —y los axiomas de Peano no incluyen uno que garantice que la suma de dos naturales también es natural. Si estás tentado a rastrear todo esto hacia atrás, para “averiguar a qué profundidad va la madriguera del conejo”, te felicito. Pero, si solo quieres poder seguir con tus problemas de tarea, yo también simpatizo con ese sentimiento. Vamos a estar de acuerdo en que los enteros se comportan de la manera que hemos llegado a esperar — si se suman o multiplican enteros el resultado será un entero.
Ejercicios:
Cada número primo mayor que\(3\) es de una de las dos formas\(6k + 1\) o\(6k + 5\). ¿Qué enunciado (s) podría (n) utilizarse como hipótesis para probar este teorema?
Demostrar que\(129\) es extraño.
Demostrar que la suma de dos números racionales es un número racional.
Demostrar que la suma de un número impar y un número par es impar.
Demostrar que si la suma de dos enteros es par, entonces también lo es su diferencia.
Demuéstralo por cada número real\(x\),\(\dfrac{2}{3} < x < \dfrac{3}{4} \implies \lfloor 12x \rfloor = 8\).
Demostrar que si\(x\) es un entero impar, entonces\(x^2\) es de la forma\(4k + 1\) para algún entero\(k\).
Demostrar que para todos los enteros\(a\) y\(b\), si\(a\) es impar y\(6 |(a + b)\), entonces\(b\) es impar.
\(∀x ∈ \mathbb{R}, x \notin \mathbb{Z} \implies \lfloor x \rfloor + \lfloor−x \rfloor = −1\)Demuéstralo.
Defina la uniformidad de un entero\(n\) por:
\(\text{evenness}(n) = k \iff 2^k |n ∧ 2^{k+1} - n∤\)
Estado y probar un teorema relativo a la uniformidad de los productos.
Supongamos que\(a\),\(b\) y\(c\) son enteros tales que\(a| b\) y\(b | c\). \(a| c\)Demuéstralo.
Supongamos que\(a\)\(b\),,\(c\) y\(d\) son enteros con\(a \neq c\). Además, supongamos que\(x\) es un número real que satisface la ecuación
\(\dfrac{ax+b}{cx+d} = 1.\)
Demostrar que\(x\) es racional. ¿Dónde se\(a \neq c\) utiliza la hipótesis?
Demostrar que si dos enteros positivos\(a\)\(a | b\) y\(b\) satisfacer y\(b | a\) entonces son iguales.