Contraejemplo mínimo

En matemáticas , un contraejemplo mínimo es el ejemplo más pequeño que falsifica una afirmación. También se le llama a veces criminal mínimo , ^{[ 1 ]} criminal más pequeño , ^{[ 2 ]} o criminal menos importante , ^{[ 3 ] [ 4 ]} especialmente (pero no exclusivamente) en el contexto del teorema de los cuatro colores . ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]} Una prueba por contraejemplo mínimo (o por criminal mínimo/más pequeño/menor importante ) es un método de prueba que combina el uso de un contraejemplo mínimo con los métodos de prueba por inducción y prueba por contradicción . ^{[ 10 ] [ 11 ]} Más específicamente, al intentar probar una proposición P , primero se asume 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 cuidadosamente), se concluye entonces que existe tal contraejemplo C que es mínimo . En cuanto al argumento, C es generalmente algo bastante hipotético (ya que la verdad de P excluye la posibilidad de C ), pero podría argumentarse que si C existiera, tendría algunas propiedades definidas que, tras aplicar un razonamiento similar al de una demostración inductiva, conducirían a una contradicción, demostrando así que la proposición P es verdadera. ^{[ 12 ]}

Si la contradicción consiste en derivar un contraejemplo D adicional , menor que C según la hipótesis de minimalidad, esta técnica se conoce tradicionalmente como prueba por descenso infinito . En tal caso, puede haber múltiples y más complejas maneras de estructurar el argumento de la prueba.

La suposición de que si existe un contraejemplo, existe un contraejemplo mínimo, se basa en algún tipo de ordenamiento adecuado . El ordenamiento habitual de los números naturales es claramente posible, mediante la formulación más común de la inducción matemática ; pero el alcance del método puede incluir inducciones bien ordenadas de cualquier tipo.

El método del contraejemplo mínimo se ha utilizado ampliamente en la clasificación de grupos simples finitos . El teorema de Feit-Thompson , que establece que los grupos simples finitos que no son grupos cíclicos tienen orden par, se demostró basándose en la hipótesis de la existencia de algún grupo simple G de orden impar, y por lo tanto, de algún grupo simple mínimo G. Se puede suponer que todo subgrupo propio de G es un grupo resoluble, lo que significa que se puede aplicar gran parte de la teoría de dichos subgrupos. ^{[ 13 ]}

La demostración de Euclides del teorema fundamental de la aritmética es una demostración sencilla que utiliza un contraejemplo mínimo. ^{[ 14 ] [ 15 ]}

Un contraejemplo mínimo se ha utilizado con frecuencia en demostraciones del teorema de los cuatro colores , donde generalmente se le llama criminal mínimo . ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]}