Pruebas no constructivas favoritas.

Hay muchos resultados para los que existe una prueba constructiva, pero no es tan buena como la prueba no constructiva. Por ejemplo, la construcción explícita de una función continua diferenciable en ninguna parte es bastante técnica en comparación con la prueba de existencia que invoca el teorema de la categoría de Baire.

¿Cuáles son tus pruebas o métodos no constructivos favoritos?

El teorema de capacidad de Claude Shannon de la teoría de la información: existen códigos que se acercan arbitrariamente a la capacidad (debido a un argumento de aleatorización), pero es muy difícil construir uno. En particular, es difícil encontrar uno con una regla de codificación/descodificación fácil.
Creo que la existencia de números normales satisface esto. La prueba constructiva requirió una construcción extraña así como bastante trabajo para mostrar que el número construido es normal, pero la prueba de que casi todos los números reales son normales es mucho más bonita.
Creo que esta es una gran pregunta, pero no es apropiada para este sitio; simplemente es demasiado amplia. (Dicho esto, mencionaré la prueba de que cada juego de Chomp está determinado , ¡que es una línea larga y no revela información sobre la estrategia ganadora en absoluto!)

Respuestas (3)

Siempre me ha gustado:

Afirmación: existen números irracionales α , β , posiblemente igual, tal que α β es racional

Pf: Considere 2 2 . Si es racional, entonces hemos terminado. Si es irracional, entonces llámalo. α y considerar α 2 = 2 . Y hemos terminado.

@MatthewDaly Es realmente un gran argumento. Especialmente cuando lo comparas con la prueba de que 2 2 es de hecho irracional.
Este es bueno, pero en realidad no es más simple que una prueba constructiva. 2 registro 2 ⁡ ( 9 ) = 3 es un ejemplo fácil. Todos saben eso 2 es irracional y registro 2 ⁡ 9 es irracional porque 2 a y 9 b son diferentes mod 2.

El robo de estrategia es otro ejemplo clásico que se aplica a varios juegos por turnos. Muestra que el primer jugador siempre gana o que el juego terminará en empate, suponiendo un juego perfecto de ambos lados. Las pruebas en realidad nunca exhiben las estrategias en cuestión.

Por ejemplo, tome Tic Tac Toe (en un tablero arbitrariamente grande de tamaño norte × norte ). Supongamos que el jugador 2 tiene una estrategia ganadora S , independientemente del primer movimiento del jugador 1. Luego hacemos una serie de observaciones:

1) Independientemente de donde el jugador 1 juegue primero X , el jugador 2 supuestamente tiene una estrategia ganadora, que es función de la posición del primero X .

2) Nunca hay una desventaja en tener una de tus piezas ya en el tablero, lo que significa que si el jugador 1 ya tiene una X en un cuadrado dado, entonces eso no puede ser peor que no tener un X en esa plaza.

3) Por 1), el jugador 1 puede adoptar la estrategia del jugador 2 colocando aleatoriamente un X , y luego, después de que el jugador 2 responda con su estrategia S , aplica el jugador 1 S a la respuesta del jugador 2, con X y O cambiado. Si S alguna vez llama para jugar en el primero X que el jugador 1 tenía que colocar, luego el jugador 1 puede hacer un movimiento aleatorio por 2).

Entonces, el jugador 2 no podría tener una estrategia ganadora. S , lo que significa que el jugador 1 siempre gana o el juego siempre termina en empate.

Grita por el teorema del punto fijo de Brouwer, aunque solo sea porque el otro gran reclamo de fama de Brouwer es ser un constructivista estricto.

Pruebas no constructivas favoritas.
RespuestasAquíPolítica de privacidad1y, 0v