¿Cuándo podemos decir que un teorema ha sido demostrado?

Question

Estoy haciendo un curso de Estructuras de Datos y Algoritmos para un programa de CS. El material introductorio era todo matemático, principalmente una serie de fórmulas que debemos recordar. Puedo trabajar con las fórmulas sin problemas. Sin embargo, la demostración de teoremas también forma parte del material.

He tomado una buena cantidad de clases de matemáticas pero, de alguna manera, nunca llegué a entender las pruebas. Sé que esta pregunta puede ser algo amplia, así que estoy dispuesto a intentar ser específico si es necesario.

Nuestro libro explica brevemente las pruebas por inducción, contraejemplo y contradicción. Independientemente del método, no sé cuando la prueba ha sido satisfecha.

Answer 1

"Prueba" se refiere realmente a un espectro de conceptos relacionados. En un extremo está la noción de prueba formal . Una prueba formal es una secuencia de afirmaciones, cada una de las cuales es una axioma o es deducido de las declaraciones anteriores de algunos regla de deducción. Esta noción de prueba depende de los axiomas y las reglas de deducción que uno utilice. Si quieres sentirte cómodo con este tipo de pruebas, no sería mala idea estudiar algunas lógica proposicional donde los axiomas y las reglas de deducción son relativamente simples. Para acercarse un poco más a las matemáticas reales, el siguiente paso es lógica de predicados .

En el otro extremo está la noción que los matemáticos utilizan realmente en la práctica. El estudio de la lógica puede llevar a pensar que la noción de prueba que utilizan los matemáticos es la de una prueba formal en ZFC . Sin embargo, muchos matemáticos en activo probablemente no podrían describir los axiomas de ZFC cuando se les pregunta; en la práctica, no es así como piensan los matemáticos. Y por una buena razón: escribir pruebas formales en ZFC es, para la mayoría de la gente, una enorme pérdida de tiempo.

La noción de prueba que los matemáticos utilizan en la práctica es una construcción social En el caso de los matemáticos, la cuestión es que ciertos tipos de deducciones y supuestos son socialmente aceptables como obvios, y uno los utiliza para construir una prueba socialmente aceptable. No digo esto para argumentar que las pruebas que los matemáticos describen en la práctica no son válidas, sino sólo para subrayar que lo que cuenta como una prueba es una cuestión sutil, y la respuesta depende del contexto histórico y cultural. Lo que contaba como prueba para Euler no es lo mismo que lo que cuenta como prueba ahora, por ejemplo.

En tu caso, creo que lo mejor que podrías hacer para entender lo que es una prueba en la práctica es leer el principio (y más, si quieres) del libro de Sipser Introducción a la teoría de la computación que contiene la introducción más clara a las matemáticas que he visto nunca.