¿Por qué funciona la prueba por eliminación?

Question

Entiendo que si todas las demás opciones se demuestran erróneas, entonces la única opción que queda debe ser la correcta. Pero, ¿por qué funciona esto? ¿Cuál es la lógica detrás de esto? Por alguna razón, no me cuadra, aunque sé que debería entenderlo porque lo "comprendo", al menos a un nivel superficial.

---

_{<strong>Actualización: </strong>Se ha cambiado "agotamiento" por "eliminación" en el título para evitar confusiones.}

Answer 1

Para reformular mi comentario, considere lo siguiente.

Hay cinco gatos en una habitación, y tú conozca que exactamente uno de ellos es negro. Si se demuestra que cuatro de ellos son no negro, entonces se puede concluir razonablemente que como hay que ser negro tiene que ser el definitivo. De lo contrario, si el último tampoco fuera negro, entonces habría sido falso decir que hay exactamente un negro en el primer caso.

---

Mi primera experiencia con este tipo de pruebas fue una prueba de teoría de grupos. Tenía un grupo de orden $8$ y necesitaba demostrar que pertenecía a una clase de isomorfismo particular (es decir, que era isomorfo a uno del orden "estándar $8$ grupos). Al tratarse de un grupo de orden $8$ , es debe ser isomorfo a uno de los cinco órdenes "estándar $8$ grupos.

En lugar de construir el isomorfismo explícitamente, podría demostrar que es no isomorfo a cuatro del orden "estándar $8$ grupos con facilidad, lo que significa que tenía para ser isomorfo al grupo final "estándar" de orden $8$ .

Si no lo fuera, entonces o no era una orden $8$ grupo para empezar, lo que sería falso, o sería una estructura de grupo completamente nueva de orden $8$ , lo que también es falso. Por lo tanto tenía para ser isomorfo al caso final.

---

Algunos otros ejemplos (bastante triviales) son:

• Dejemos que $n$ sea un número entero, y aclaramos que $0$ está en paz. O bien $n$ es impar o $n$ es uniforme. Si demuestras que no es divisible por $2$ , has demostrado que ni siquiera es ( $0$ es divisible por $2$ ), por lo que debe ser impar. Así es como se suele comprobar si algo es par o impar.

• Dejemos que $a$ sea un número real. Entonces es positivo, negativo o cero. Si se demuestra que no es ni negativo ni cero, debe ser positivo. Del mismo modo, esta es la razón por la que la frase " $a$ es no negativo" es equivalente a "o bien $a$ es cero o $a$ es positivo".

• Dejemos que $x$ sea un número entero positivo. Entonces modulo $4$ su resto es uno de $0$ , $1$ , $2$ o $3$ . Si se demuestra que su resto no es ninguno de $0$ , $1$ o $2$ , entonces su resto debe ser $3$ .

• Dejemos que $G$ sea un grupo cíclico de orden $4$ con elementos $a, b, c, d$ . Se sabe que los elementos deben tener un orden $1$ , $2$ o $4$ . Así, si se demuestra que, por ejemplo, el elemento $a$ no tiene orden $1$ o pedir $2$ (mostrando que ni ella misma ni su cuadrado son la identidad), debe tener orden $4$ y sería un generador. Ver aquí para un ejemplo.

Insisto en que el método de prueba por eliminación no es probablemente el mejor método de prueba para muchos de los ejemplos anteriores, pero seguiría funcionando si conozca que su objeto tiene para satisfacer uno de los casos que ibas a comprobar. Un contraejemplo sencillo es dejar que $a$ sea un número real, demuestre que no es divisible por $2$ y concluir entonces que debe ser impar. Esto es claramente falso, ya que los números reales no se pueden dividir en sólo números pares e Impares, por lo que es cierto que podría ser ninguno de los dos.

Answer 2

Ver Silogismo disyuntivo :

\begin{align} \frac{P \lor Q \ \ \ \lnot P}{Q} \end{align}

lo que equivale al siguiente principio :

si sabemos que la pelota es o bien negro o blanco y sabemos que la pelota es no negro entonces debe sea blanco .

Si llamamos a $P_1,P_2,\ldots, P_n$ las opciones disponibles, podemos hacer valer la disyunción :

$(P_1 \lor P_2 \lor \ldots \lor P_{n-1}) \lor P_n$ .

Así, si hemos establecido que $P_1,P_2,\ldots, P_{n-1}$ no sostienen, podemos afirmar :

$(\lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_{n-1})$ ,

que, según De Morgan, es equivalente a :

$\lnot (P_1 \lor P_2 \lor \ldots \lor P_{n-1})$ .

Así, habiendo rechazado todos los primeros $n-1$ opciones, estamos autorizados a concluir que la última debe mantenerse.

Answer 3

Considere la siguiente afirmación:

Todas las combinaciones posibles de dos números del 0 al 10 (tanto el 0 como el 10 inclusive) multiplicadas entre sí no dan 13.

Esto es $\binom{11}{2}$ = 55 combinaciones posibles.

Prueba por agotamiento significa que intenta cada una de las combinaciones y mira si da 13. Después de probar todas las combinaciones, de hecho has demostrado que la frase anterior es cierta.

Para que esto funcione se necesita un número limitado de opciones que todos puedan probar. Esto no funciona para las pruebas que tienen un número ilimitado de posibilidades, como la conjetura de Goldbach o el último teorema de Fermat.

En el ejemplo anterior, también se demuestra que..es un poco tonto. Todo matemático sabe que 13 es un primo y que no se puede construir multiplicando dos números.

Pero hay muchos casos en los que, de hecho, la prueba por agotamiento era exactamente la prueba del problema. Uno de ellos es el Teorema de los cuatro colores dividiendo el problema en 1936 mapas posibles y comprobando para cada mapa que, de hecho, cuatro colores son suficientes. Otro es el Conjetura de Kepler donde se conocía el mejor resultado posible y "sólo" había que demostrar que cualquier combinación es peor.

Answer 4

Esto es lo que yo entiendo por prueba por agotamiento (o casos, o eliminación):

Supongamos, por ejemplo, que $P_1 \lor P_2 \lor P_3$ es verdadera, es decir, al menos una de estas 3 proposiciones debe ser verdadera.

Si puede demostrar que $P_1\implies Q$ , $P_2\implies Q$ y $P_3\implies Q$ , entonces se puede deducir que $Q$ debe ser cierto.

Answer 5

La lógica que describes es la que la gente suele utilizar en eventos de entretenimiento como los concursos o los exámenes de matemáticas que se basan en preguntas de opción múltiple y en las que sabes que exactamente una de las respuestas es la correcta. Si no sabes la respuesta correcta, intentas eliminar todas las respuestas excepto una. La respuesta restante debe ser la correcta.