Inducción fuerte sin caso base

Question

La inducción fuerte demuestra una secuencia de afirmaciones $P(0)$ , $P(1)$ , $\ldots$ demostrando la implicación

"Si $P(m)$ es verdadera para todos los enteros no negativos $m$ menos de $n$ entonces $P(n)$ es cierto".

para cada entero no negativo $n$ . No hay necesidad de un caso base separado, porque el $n=0$ instancia de la implicación es el caso base, vacuamente. Pero la mayoría de las pruebas de inducción fuerte parecen implicar un argumento separado para manejar el caso base (es decir, para probar la implicación para $n=0$ ).

¿Puedes pensar en un ejemplo natural de una prueba de inducción fuerte que haga no ¿tratar el caso base por separado? Lo ideal es que sea un enunciado de nivel universitario o inferior, y que sea un enunciado para el que la inducción fuerte funcione mejor que la inducción ordinaria o cualquier prueba directa.

Answer 1

Mi ejemplo es la prueba clásica de que sqrt(2) es irracional.

De manera más general, muchas pruebas que proceden mostrando que no hay contraejemplos mínimos ejemplificar su fenómeno. El método de los no-minimales-contra-ejemplos es exactamente el mismo que la inducción fuerte, pero donde uno prueba la implicación requerida por contradicción. En muchas aplicaciones de este método, a menudo está claro que los números más pequeños no son contraejemplos, y esto no se consideraría ordinariamente como un "caso" base separado.

En la prueba clásica de que sqrt(2) es irracional, por ejemplo, suponemos que sqrt(2) = p/q, donde p es mínimo. Ahora, elevamos al cuadrado ambos lados y procedemos con el argumento habitual, para llegar a un contraejemplo menor. ¡Contradicción! Esto equivale a una prueba por inducción fuerte de que ningún número racional es cuadrado a 2, y parece que no hay ningún caso base separado aquí.

La gente suele llevar a cabo el argumento clásico asumiendo que p/q está en términos mínimos, pero el argumento que acabo de describir no necesita esta complicación extra. Además, en cualquier caso, la prueba de que todo número racional puede ponerse en términos mínimos es en sí misma otro caso del fenómeno. A saber, si p/q es un contraejemplo con p mínimo, entonces se divide por cualquier factor común y se aplica la inducción. Parece que no hay un caso base separado aquí donde ya está en términos mínimos, ya que estábamos considerando un mínimo contraejemplo . Tal vez alguien objete que aquí no hay ninguna inducción, ya que uno puede simplemente dividir por el gcd(p,q). Pero la prueba habitual de que dos números cualesquiera tienen un gcd es, por supuesto, también inductiva: considerar la menor combinación lineal xq+yp equivale a una inducción fuerte, de nuevo sin caso base separado.

Answer 2

Espero que lo siguiente satisfaga a Bjorn. Es una prueba por inducción que naturalmente se salta el caso base y está a nivel de licenciatura. Hoy he visto el argumento por primera vez en el documento que contiene 10 pruebas en ruso del Teorema Fundamental del Álgebra que Ilya Nikokoshev enlazó en su respuesta a una pregunta que pedía muchas pruebas diferentes de ese teorema. Aquí está:

Afirmación: Un polinomio distinto de cero (sobre un campo) no tiene más raíces que su grado.

Prueba: Lo demostramos por inducción en el grado $n$ del polinomio. Supongamos que el polinomio $$p(X) = a_nX^n + \cdots + a_1X + a_0$$ de grado $n$ tiene al menos $n+1$ diferentes raíces $r_1,\dots, r_{n+1}$ . Consideremos el polinomio $$q(X) = a_n(X-r_1)\cdots (X-r_n).$$ Tenemos $p(X) \not= q(X)$ desde $p(r_{n+1}) = 0$ y $q(r_{n+1}) \not= 0$ . La diferencia $d(X) = p(X) - q(X)$ es un polinomio no nulo de grado inferior a $n$ teniendo al menos $n$ raíces $r_1,\dots,r_n$ . Esto contradice la hipótesis inductiva. QED

[EDIT: IGNORAR lo que sigue en el siguiente párrafo, que estaba en el post original, ya que me confundí sobre la inducción fuerte frente a la ordinaria. La prueba anterior es por inducción fuerte ya que el grado de d(X) es simplemente menor que n y no necesariamente n-1 mismo].

Un aspecto que no se ajusta a la petición de Bjorn es que este argumento utiliza la inducción ordinaria, no la fuerte. Pero realmente, ¿es eso tan importante? Sospecho que su principal interés es ver un argumento inductivo en el que naturalmente no se mencione el caso base, en lugar de uno que utilice específicamente la inducción fuerte.

Answer 3

Creo que el mejor ejemplo de esto será el teorema fundamental de la aritmética La afirmación de que todo número natural mayor que 1 es primo o producto de primos (y de forma única).

La prueba de la existencia es por inducción fuerte. Supongamos que es cierto por debajo de n. Si n es primo, hemos terminado. Si no, n = ab para algunos a,b < n, y por inducción estos son productos de primos, así que n también lo es. QED (y no hay necesidad de un caso especial de anclaje).

La prueba de la unicidad no utiliza la inducción.

Answer 4

La jerarquía acumulativa en la teoría de conjuntos es la jerarquía V _α que a menudo se define por la recursión transfinita:

• V ₀ \= conjunto vacío
• V _α+1 \= P(V _α ), tomando el conjunto de potencias en las etapas sucesivas
• V _λ \= U{ V _α | α<λ }, tomando las uniones en los límites.

Y si se quiere considerar sólo la clase HF de conjuntos hereditariamente finitos, se restringe a la inducción de números naturales α=n, lo que lleva a HF = V _ω \= U V _n . Sin embargo, estas definiciones se dividen en casos separados para el cero, el sucesor y el límite.

Sin embargo, una definición equivalente evita por completo esta división. A saber:

• Para cualquier ordinal α, sea V _α \= U { P(V _β ) | β < α }.

Se ve fácilmente que esto es equivalente a la definición anterior.

Del mismo modo, se pueden definir los conjuntos finitos hereditarios HF como la unión de V _n donde V _n \= U { P(V _m | m < n }. Esta definición no necesita un caso base, y no se divide en casos.

Ahora se pueden demostrar todos los hechos básicos sobre el V _α jerarquía, también sin dividir en los casos cero, sucesor y límite. Por ejemplo, cada V _α es transitiva, ya que por inducción es la unión de conjuntos transitivos. Del mismo modo, la jerarquía es creciente, etc.

Answer 5

Un contexto en el que se hacen pruebas inductivas sin un caso base es el de los juegos/números de Conway, que se definen inductivamente sin un caso base.