¿Es cierto que cada teorema que tiene una prueba directa también puede probarse mediante la inducción matemática?

Answer 1

Esta es una pregunta interesante. Estoy bastante seguro de que la respuesta es no, pero no creo que sea fácil dar una demostración completamente rigurosa. Para un contraejemplo específico, considere el teorema de Wilson .

Un entero [math] n> 1 [/ math] es primo si y solo si [math] (n-1)! + 1 [/ math] es un múltiplo de [math] n [/ math].

Puedo ver a un principiante determinado pasar horas tratando de demostrar esto mediante la inducción. Aunque es inútil. La divisibilidad por números primos es esencialmente eventos independientes cuando se mide en intervalos suficientemente grandes. No hay nada en la hipótesis de inducción para [math] n = 16 [/ math] (o [math] n \ le 16 [/ math] si uno prefiere una inducción fuerte) que puede usarse de manera efectiva para probar cualquier cosa sobre la divisibilidad mediante [math ] 17 [/ math], ya que es un animal completamente nuevo. Pero solo puedo esperar que este tipo de razonamiento sea persuasivo, y no lo llamaría una prueba férrea de la imposibilidad de una prueba del teorema de Wilson por inducción.

---

Hay algunos resultados interesantes sobre las limitaciones de ciertas técnicas de prueba. Por ejemplo, es fácil adaptar la prueba de Euclid de que hay infinitos números primos para mostrar la afirmación más fuerte de que hay infinitos números primos de la forma [math] 4k + 3 [/ math]. Una variación más sofisticada del argumento de Euclides se puede usar para mostrar que también hay infinitos números primos de la forma [math] 4k + 1 [/ math]. En 1912, Issai Schur demostró que las variaciones de la prueba de Euclides pueden usarse para establecer la infinitud de los números primos de la forma [math] mk + a [/ math] siempre que [math] a ^ 2-1 [/ math] sea un múltiplo de [matemáticas] m [/ matemáticas]. En 1988, Ram Murty demostró que esta condición suficiente también es necesaria; en particular, no hay pruebas al estilo de Euclides de la infinitud de números primos que terminan en [math] 7 [/ math]. Detalles pueden ser encontrados aqui:

http: //www.seminariomatematico.u…

Answer 2

Editar:

Uno puede probar cada teorema por inducción matemática introduciendo un número natural que no aparece en la declaración del teorema real. Por ejemplo, el teorema de Pitágoras

Para cada triángulo rectángulo con hipotenusa [math] c [/ math] y piernas [math] a, b [/ math] tenemos [math] a ^ 2 + b ^ 2 = c ^ 2 [/ math]

se puede reescribir como

Para cada número natural [math] n, para [/ math] cada triángulo rectángulo con hipotenusa [math] c [/ math] y piernas [math] a, b [/ math] tenemos [math] a ^ 2 + b ^ 2 = c ^ 2 [/ math]

¡Observe que [math] n [/ math] no aparece en el teorema de Pitágoras real! Luego procedemos con una prueba por inducción que nunca usa la hipótesis de inducción y tiene la misma prueba para el caso base y para el paso inductivo. Pero esta es una aplicación degenerada completa de la inducción matemática.

¿Se puede probar todo teorema con una “prueba directa”? Si por “prueba directa” nos referimos a una prueba que no usa reducción ni absurduo , entonces no. Las pruebas que no usan reductio (o técnicas de prueba que pueden establecerse a partir de la reductio , como la contraposición) son intuicionísticamente válidas, mientras que este no es el caso de las pruebas que sí usan reductio. Es bien sabido que hay fórmulas lógicas que son teoremas en la lógica clásica pero no en la lógica intuicionista. El ejemplo paradigmático es la ley del medio excluido: [math] \ varphi \ vee \ neg \ varphi [/ math].

Answer 3

Técnicamente sí, porque puede introducir un índice vacío que no se usa en la declaración y hacer una inducción sobre eso.

Entonces su caso base sería la prueba directa de la proposición P, y su paso inductivo sería el trivial [math] P \ Rightarrow P [/ math].

Answer 4

Solo los teoremas que involucran números enteros (o alguna otra estructura inductiva) son susceptibles de inducción matemática. Los primeros cuatro libros de los Elementos de Euclides , que están en geometría plana, no tienen números ni uso para la inducción matemática.

Answer 5

La inducción matemática es un método poderoso para resolver problemas relacionados con el infinitivo, algunos problemas no pueden resolverse mediante pruebas directas, pero sí mediante la inducción. No solo en el campo numérico sino también en otros. Consulte: Una prueba del teorema de los cuatro colores por inducción está disponible en Vixra.org/abs/1601.0247.

En general, hay problemas que se pueden utilizar de ellos, no los hay.