¿Debemos utilizar la inducción para demostrar una afirmación para todos los enteros

Question

Esta pregunta viene motivada por un comentario de Bill Dubuque en su respuesta a este pregunta sobre la demostración de una suma particular sin utilizar la inducción matemática.

De la respuesta de Bill:

Una prueba de que un enunciado es verdadero para todos los números enteros debe -en algún momento- emplear la inducción matemática. El uso de la inducción puede no ser obvio - puede estar oculto (muy) abajo en la cadena de inferencia en algún otro teorema o lema invocado, como en dicho teorema de unicidad para las recurrencias (ecuaciones de diferencia).

Mi pregunta es: ¿es esto siempre cierto? (No tengo ninguna razón en particular para dudar de su veracidad, pero tengo curiosidad por saber si es siempre verdadero). Y si es así, ¿por qué es ésta la única estrategia defendible para demostrar una afirmación sobre todos los números enteros? Si no es así, ¿cuáles son las estrategias alternativas?

Parece que tenemos que demostrar cosas para todos los números enteros con cierta frecuencia (en algunas áreas de las matemáticas), así que darse cuenta de que cada una de estas pruebas se basará de alguna manera en la inducción reduce el espacio de búsqueda de una prueba de manera sustancial. Me gustaría saber qué fuerza tiene esta afirmación.

Answer 1

Bueno, técnicamente no es cierto. Para un ejemplo trivial, mire la frase $\forall x(x=x)$ . No necesitamos la inducción para demostrar que esto es cierto para todos los números naturales.

Desgraciadamente, el conocimiento de que en principio la mayoría de los resultados requieren inducción no ofrece una ayuda significativa a la hora de producir pruebas. Como señaló Bill Dubuque, la inducción puede estar oculta en lo más profundo de la cadena de inferencia, en las pruebas de otros teoremas que se utilizan en nuestra prueba. Uno sabe que, en principio, necesitamos poner un pie delante del otro repetidamente para poder correr. Ese conocimiento no es realmente de mucha ayuda para correr un maratón.

Answer 2

Respuesta técnica

En la aritmética de Peano, incluso $+$ y $\cdot$ se definen mediante inducción, y sus propiedades (conmutatividad, asociatividad, distributividad, etc.) se demuestran mediante inducción. Por lo tanto, si su prueba utiliza una de estas propiedades, y usted fuera a alinear las pruebas a los axiomas desnudos (como usted mira la asamblea generada de un programa de ordenador escrito en un lenguaje de alto nivel), la inducción será en alguna parte.

Opinión subjetiva

Prefiero clasificar una prueba como inductiva sólo si tiene un argumento inductivo novedoso - no si sólo se basa en propiedades establecidas como $\sum_{i=1}^{n} x_i = \sum_{i=1}^{n} x_{n+1-i}$ o $a+b=b+a$ . Aunque esas propiedades se demuestran de forma inductiva, una vez que las has demostrado, no necesitas repetir su demostración de nuevo. En la terminología de programación, estas pruebas son como rutinas que no llaman a la inducción directamente, sino indirectamente a través de subrutinas.

Por lo tanto, casi todas las pruebas con números naturales utilizan la inducción, pero no creo que sea necesario descomponer las pruebas complejas para ver cómo se utiliza la inducción. La abstracción es algo bueno.

Answer 3

O bien se definen los números naturales de forma axiomática mediante Los axiomas de Peano o los defines como el subconjunto inductivo más pequeño de los números reales o algo equivalente en la teoría de conjuntos . Así que, sí, se necesita la inducción en alguna parte cuando se habla de los números naturales, excepto, por supuesto, en los casos triviales que se mantienen para las teorías más simples, como el ejemplo dado por André Nicolas.

Answer 4

Se puede entender la pregunta de dos maneras diferentes:

• (fuerte) ¿Puede demostrarse la afirmación dada sin implicar la inducción en ningún paso o nivel de razonamiento?
• (débil) Dadas todas las definiciones inductivas y las propiedades triviales conocidas, ¿podemos demostrar la afirmación sin implicar ninguna inducción adicional, relacionada únicamente con este problema

Me parece que lo que se plantea en esa pregunta es la forma débil de la misma, y lo que Bill tiende a pensar es la fuerte. Pero aún así, en esa pregunta, estoy de acuerdo con Bill, que las respuestas que implican argumentos como, por ejemplo, $a_1-a_0+a_2-a_1+...+a_n-a_{n-1}=a_n-a_0$ sí requieren inducción (simplemente se reescriben de otra forma).

En cuanto al comentario de Bill, creo que no es exactamente correcto (incluso para la forma fuerte de la pregunta).

Yo diría que se necesita (a cierto nivel) la inducción cuando se trata de una afirmación que es correcta o incluso significativa sólo para números enteros. Por ejemplo, un ejemplo dado por Beni Bogosel, obviamente, requiere inducción en algún momento, al menos porque no tiene sentido hablar de "5 divide a x" o "-1 a la potencia de x" si x no es un número entero. Por lo tanto, para definir cuándo es verdadera, hay que utilizar la inducción en algún momento. Su primera prueba requiere la inducción explícitamente, y la segunda - implícitamente.

Al mismo tiempo, puede haber una afirmación de carácter más general que simplemente se enuncie sólo para los números enteros. Un ejemplo trivial es el de André Nicolas: $\forall n:n=n$ (bueno, es trivial dado el axioma de reflexividad). Pero otro ejemplo podría ser una afirmación que es verdadera para todos los números reales y, por tanto, para todos los enteros. Por ejemplo, $(n\neq 0\wedge m\neq 0)\Rightarrow n\cdot m\neq 0$ . Ni la definición del operador, ni la demostración del enunciado para reales requiere de la inducción. Y, ahora, si pensamos en (o definimos) los enteros como un subconjunto de los reales, entonces ni siquiera necesitamos la definición exacta de los enteros... todo lo que necesitamos saber es que es un subconjunto de un conjunto tal que la afirmación ya ha sido demostrada.

Answer 5

Sospecho fuertemente que no estoy entendiendo el punto aquí, así que sea gentil. Y mi habilidad para escribir pruebas en $\LaTeX$ se ha desvanecido en los últimos 20 años, así que perdonen la informalidad.

Prueba de $\forall x(x\neq x+1)$ sin inducción:

Supongamos que $\exists x$ ( $x=x+1$ ).

Restando $x$ de ambos lados, obtenemos $0=1$ , lo cual es una contradicción.

$\therefore$ por contradicción, $\not \exists x$ ( $x=x+1$ ).

$\therefore \forall x(x\neq x+1)$ porque $\neg (\exists x\in X : P(x)) \equiv \forall x\in X, \neg P(x)$

No veo ninguna inducción aquí. ¿Qué me he perdido?