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] Más específicamente, al intentar 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 necesitar ser elegido con cuidado), uno luego concluye que existe tal contraejemplo C 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. [3]
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 . 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 ordenamiento 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.
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 un orden par, se basó en la hipótesis de algunos, y por lo tanto, un grupo G simple mínimo 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 usa un contraejemplo mínimo. [4] [5]