En matemáticas , un contraejemplo mínimo es el ejemplo más pequeño que falsifica una afirmación, y una prueba mediante 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 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 tal vez deba elegirse con cuidado), se concluye que existe un contraejemplo C que es mí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 la de una prueba inductiva, conduciría a una contradicción, demostrando así que la proposición P es efectivamente verdadera. [3]
Si la forma de la contradicción es que podemos derivar otro contraejemplo D , que es más pequeño que C en el sentido de la hipótesis de trabajo de la minimalidad, entonces esta técnica se llama tradicionalmente prueba por descenso infinito . 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 algún tipo de buen ordenamiento . La ordenación 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 finitos simples . El teorema de Feit-Thompson , de que los grupos finitos simples que no son grupos cíclicos tienen orden par, fue [¿ cuándo? ] basado en la hipótesis de algún grupo G simple, y por lo tanto mínimo, de orden impar. Se puede suponer que cada subgrupo adecuado de G es un grupo resoluble , lo que significa que se podría aplicar gran parte de la teoría de tales subgrupos.
La prueba de Euclides del teorema fundamental de la aritmética es una prueba simple que utiliza un contraejemplo mínimo. [4] [5]
Courant y Robbins utilizaron el término criminal mínimo para un contraejemplo mínimo en el contexto del teorema de los cuatro colores. [6]