En matemáticas , un contraejemplo mínimo es el ejemplo más pequeño que falsifica una afirmación, y una prueba por contraejemplo mínimo es un método de prueba que combina el uso de un contraejemplo mínimo con las ideas de prueba por inducción y prueba por contradicción . [1] [2] [3] Más específicamente, al tratar de probar una proposición P , primero se supone por contradicción que es falsa y que, por lo tanto, debe haber al menos un contraejemplo . Con respecto a alguna idea de tamaño (que puede ser necesario elegir con cuidado), se llega a la conclusión de que existe un contraejemplo C de este tipo que esmínimo . Con respecto al argumento, C es generalmente algo bastante hipotético (ya que la verdad de P excluye la posibilidad de C ), pero puede ser posible argumentar que si C existiera, entonces tendría algunas propiedades definidas que, después de aplicar algún razonamiento similar a eso en una prueba inductiva, conduciría a una contradicción, mostrando así que la proposición P es de hecho verdadera. [4]
Si la forma de la contradicción es que podemos derivar un contraejemplo adicional D , que es más pequeño que C en el sentido de la hipótesis de trabajo de minimidad, entonces esta técnica se llama tradicionalmente prueba por descendencia infinita . [1] En cuyo caso, puede haber formas múltiples y más complejas de estructurar el argumento de la prueba.
La suposición de que si hay un contraejemplo, hay un contraejemplo mínimo, se basa en un buen orden de algún tipo. El ordenamiento habitual de los números naturales es claramente posible, mediante la formulación más habitual de inducción matemática ; pero el alcance del método puede incluir inducción bien ordenada de cualquier tipo.
Ejemplos de
El método del contraejemplo mínimo se ha utilizado mucho en la clasificación de grupos simples finitos . El teorema de Feit-Thompson , según el cual los grupos finitos simples que no son grupos cíclicos tienen orden par, se basó en la hipótesis de algunos, y por lo tanto, algunos grupos simples mínimos G de orden impar. Se puede suponer que cada subgrupo adecuado de G es un grupo con solución , lo que significa que se podría aplicar gran parte de la teoría de tales subgrupos.
La demostración de Euclides del teorema fundamental de la aritmética es una demostración simple que utiliza un contraejemplo mínimo. [5] [6]
Referencias
- ^ a b "El glosario definitivo de jerga matemática superior" . Bóveda de matemáticas . 2019-08-01 . Consultado el 28 de noviembre de 2019 .
- ^ Chartrand, Gary , Albert D. Polimeni y Ping Zhang . Pruebas matemáticas: una transición a las matemáticas avanzadas. Boston: Pearson Education, 2013. Imprimir.
- ^ Klipper, Michael (otoño de 2012). "Prueba por mínimo contraejemplo" (PDF) . alpha.math.uga.edu . Consultado el 28 de noviembre de 2019 .[ enlace muerto ]
- ^ Lewis, Tom (otoño de 2010). "§20 contraejemplo más pequeño" (PDF) . math.furman.edu . Consultado el 28 de noviembre de 2019 .
- ^ "El teorema fundamental de la aritmética | divisibilidad e inducción | Matemáticas subterráneas" . undergroundmathematics.org . Consultado el 28 de noviembre de 2019 .
- ^ "El teorema fundamental de la aritmética" . www.dpmms.cam.ac.uk . Consultado el 28 de noviembre de 2019 .