Paso de prueba de iteración

Question

Muchos libros demuestran teoremas realizando un paso de demostración y usando este paso como esquema dicen repitiendo este paso $l$ veces que probamos eso... Me pregunto si hay algún metateorema formal que diga que esto es una prueba válida.

Por ejemplo, digamos que quiero demostrar la desigualdad del triángulo para múltiples puntos (no sólo tres), así que quiero demostrar que $$d(x_1, x_n) \le \sum_{x=1}^{n-1}d(x_i, x_{i+1})$$

Ya conozco esa desigualdad ordinal del triángulo: $d(x_1, x_3) \le d(x_1, x_2) + d(x_2, x_3)$ se mantiene.

Usando estos hechos puedo crear una prueba perfectamente formal para cualquier constante $n$ que muestra $$d(x_1, x_2) + d(x_2, x_3) + d(x_3, x_4) + d(x_4, x_5) \ge d(x_1, x_2) + d(x_2, x_3) + d(x_3, x_5)$$

Por lo que respecta a la arbitrariedad $n$ Podría repetir este razonamiento $n-3$ veces por lo que tengo esquema de prueba para cualquier $n$ elegidos de antemano. Me gustaría saber si existe algún metateorema más o menos genérico que demuestre que efectivamente puedo iterar dicho paso de prueba para obtener prueba formal para cualquier $n$ . En otras palabras, ¿hay una manera de convertir un bucle informal en un esquema de prueba en una construcción formal que resulte en la creación de una prueba formal?

Answer 1

Cualquier prueba válida que pueda expresarse como "haz algo, luego repítelo hasta que termines" puede formalizarse como una prueba por inducción.

¿Por qué? Bueno, para convertir una prueba mediante "repite hasta que acabes" en una prueba válida, tienes que demostrar que no tendrás que repetir eternamente: al final acabarás. Es decir, deberías ser capaz de asignar alguna medida de complejidad a todas las situaciones que podrían surgir mientras repites tu(s) paso(s) de la prueba y demostrar que 1. cada vez que completas un paso, pasas a una situación estrictamente más simple, 2. si alguna vez llegas a una situación en la que no puedes completar más pasos de la prueba, has terminado, y 3. la situación no puede volverse estrictamente más simple infinitas veces seguidas.

La condición 3 dice que se quiere la relación "situación $x$ es más simple que la situación $y$ " para ser fundado es decir, algo que se puede inducir.

La condición 2 dice que se pueden manejar los casos base (la proposición $P$ que intentas demostrar es cierto allí).

La condición 1 dice que se puede reducir la verdad de $P$ en una situación $x$ a la verdad de $P$ en alguna situación estrictamente más simple $y$ (aplicando un paso de prueba). Dando la vuelta a esto, tenemos la condición inductiva: si $P$ es cierto en todas las situaciones $y$ que son estrictamente más simples que la situación $x$ entonces $P$ es cierto en $x$ .

Si la medida de la complejidad es sólo un número natural, y una situación de complejidad $n$ es más simple que una situación de complejidad $m$ justo cuando $n<m$ entonces tienes una inducción matemática normal (o tal vez inducción completa [o fuerte] ). Si la relación "más simple que" es un orden lineal, pero con un tipo de orden diferente al orden en $\mathbb{N}$ entonces tienes inducción transfinita . Y si la relación es algo más extraña, entonces tienes (generalmente) una inducción bien fundamentada.

Pero la mayoría de los casos que surgen en la práctica, como el ejemplo de la desigualdad del triángulo que das, son simplemente una simple inducción sobre los números naturales reformulada. Estás demostrando por inducción sobre $n\geq 3$ que $$d(x_1,x_n) \leq \sum_{i = 1}^{n-1} d(x_i,x_{i+1}).$$ La medida de la complejidad es el número de términos de la secuencia $x_1,\dots,x_n$ .

El caso base $n = 3$ es la desigualdad del triángulo. El paso inductivo sigue exactamente el argumento que has dado: aplicar la desigualdad del triángulo como $d(x_{n-2},x_n)\leq d(x_{n-2},x_{n-1}) + d(x_{n-1},x_n)$ obtenemos $$d(x_1,x_2) + \dots + d(x_{n-2},x_n) \leq \sum_{i = 1}^{n-1}d(x_i,x_{i+1}).$$

Y en lugar de decir "repetir", podemos concluir por inducción, ya que hemos simplificado el problema. Ahora hay $n-1$ elementos de la secuencia $x_1,\dots,x_{n-2},x_n$ Así que $$d(x_1,x_n) \leq d(x_1,x_2) + \dots + d(x_{n-2},x_n)\leq \sum_{i = 1}^{n-1}d(x_i,x_{i+1}).$$