¿Un ejemplo fácil de una prueba no constructiva sin un evidente "fix"?

Question

Quería dar un ejemplo sencillo de un no-constructiva de la prueba, o, más precisamente, de una prueba que indica que existe un objeto, pero no da obvio receta para crear/buscar.

Euclides prueba de la infinitud de los números primos vinieron a la mente, sin embargo es evidente que existe una manera de "arreglar": sólo trato de que todos los números entre el mayor primer y el construido número, y usted encontrará un alojamiento en un número finito de pasos.

Hay buenos ejemplos de simple no-constructiva de las pruebas que requeriría un sustancial cambio constructivo? (O mejor aún, no puede ser hecho constructivo en todos).

Answer 1

Algunos dígitos se produce infinitamente a menudo en la expansión decimal de $\pi$.

Answer 2

Afirmación: Existen irracionales $x, y$ tal que $x ^ $ y es racional.

Prueba: Si $\sqrt2^{\sqrt2}$ es racional, toma $x = y = \sqrt 2$. De lo contrario tomar $x = \sqrt2^ {\sqrt2}, y = \sqrt2$, así que $x ^ y = 2$.

Answer 3

Hay un tipo estándar de ejemplo aquí. Vamos a $T$ ser cualquier pregunta abierta que requiere de un trabajo sustancial para resolver. Considere la posibilidad de:

Hay un número natural $n$ que $n = 0$ si y sólo si $T$.

Esa afirmación es claramente cierto, a través de un "simple" no-constructiva de la prueba: si $n = 0$ no es un ejemplo, entonces $n = 1$ es un ejemplo. Pero si pudiéramos producir un ejemplo claro, entonces nos gustaría saber si $T$ sostiene.

Un punto clave es que la prueba no requiere el axioma de elección, matemáticas avanzadas, o de otra cosa que de ordinario la lógica clásica. El nonconstructivity en el clásico de las matemáticas es una consecuencia directa de la lógica clásica que se utiliza. En la construcción de la matemática, de la propiedad que explícita ejemplos pueden ser construidos para comprobable existencial teoremas se llama el testigo de la propiedad.

Es común que la gente señale ejemplos de "no constructiva" consecuencias del lema de Zorn o el axioma de elección, pero la clásica teoría de conjuntos sin el axioma de elección es igualmente no constructiva.

Answer 4

El teorema del valor intermedio, en el formulario que para una función continua en $f:[a,b]\a\Bbb R$ con $f(a)<0<f(b)$ existe $x\in(a,b)$ $f(x)=0$, no es válido de manera constructiva.

Véase, por ejemplo, aquí o aquí. La dificultad fundamental con la obvia clásica prueba de la IVT es que no se puede demostrar de manera constructiva para $c\in(a,b)$ $f(c)\geq0$ o $f(c)\leq0$ tiene, de donde uno no puede decidir si a concentrarse en $[a,c]$ o en $[c,b]$, tratando de localizar la búsqueda para$~x$ $f(x)=0$, y por lo tanto ninguna secuencia de números que convergen a un valor de $x$ se puede construir.

Answer 5

Definición: Un número real $x$ es llamado normal si por cada $b>1$ los dígitos $0,1,2,...,b-1$ son igualmente distribuidos en el $b$-ádico de expansión de $x$.

Teorema: Normal números que existen.

El estándar de prueba no es constructiva, ya que procede por mostrar que el conjunto de la no-normalidad de los números ha Lebesgue-medida cero, por lo tanto debe tener no vacío complemento.

No sé si la existencia de un computable número normal puede ser probado, y si sí, si que la prueba puede ser realizada de forma constructiva en el sentido de que uno puede explícitamente escribir un algoritmo para la construcción de un número normal. Yo estaría más interesado en escuchar acerca de una cosa en caso de que alguien sabe más al respecto. Hasta entonces, yo no estoy convencido de que la normal de números que existen en un sentido real, pero que son inevitables los artefactos en una cierta lógica y establecer el marco teórico de los números reales.