28 votos

Demostrar que un contraejemplo existe sin saber uno

Me esfuerzo por encontrar una declaración $S(n)$ $n \in N $ que se puede probar que no es generalmente verdad a pesar de que nadie sabe un contraejemplo, es decir, es válido para todos $ $n probado hasta ahora. ¿Alguna ayuda?

72voto

Brad Thomas Puntos 761

Declaración: "no hay primos mayor que $2 ^ {60.000.000} $". Ningún contraejemplo conocido. Ejemplo contrario debe existir puesto que el conjunto de números primos es infinito (Euclides).

23voto

rlpowell Puntos 126

Según el artículo de la Wikipedia en Skewes' número, no es explícito el valor de $x$ se sabe (aún) para que $\pi(x)\gt\text{li}(x)$. (Hay, sin embargo, el candidato de los valores, y no hay rangos dentro de los cuales contraejemplos se encuentran, por lo que este puede no ser lo que el OP es después.)

Otro ejemplo en la misma línea es la conjetura de Mertens.

Un poco tonto el ejemplo sería la declaración de "$(100!)!+n+2$ es compuesto." Es claro que $S(n)$ es verdadera para todos los "pequeños" valores de $n\in\mathbb{N}$, y es claro que es falso en general, pero yo estaría dispuesto a apostar una pequeña suma de dinero que no contraejemplo se encuentra en el siguiente $100!$ años....

(Nota: he editado en un "$+2$" para asegurarse de que mi tonta $S(n)$ es claramente cierto para $n=0$ y $1$ así como otros "pequeños" valores de $n$.)

10voto

fgp Puntos 15322

Asumir la enumeración de todas las fórmulas de primer orden de la aritmética de peano, y dejar $S(n)$ ser la declaración de

El $$n-ésimo de la fórmula no es comprobable, pero consistente, en primer lugar-fin de la aritmética de peano, y no es ninguna de las conocidas fórmulas de $\mathcal{F}$."

Suponiendo que el conjunto de conocidos tales fórmulas de $\mathcal{F}$ es recursivo (lo que significa que para cualquier fórmula, uno puede decidir si es en $\mathcal{F}$ o no), no es siempre una fórmula. De lo contrario, no sería un recursiva y extensión de la PA, lo que contradice el teorema de la incompletitud.


Actualización: de Acuerdo a esto, recursiva puede ser relajado para recursivamente enumerable en la anterior. Por lo tanto, el "saber" un contra-ejemplo no es necesario que implica que, dada una fórmula, podemos decidir si es un conocido contra-ejemplo. En lugar de ello, es suficiente que exista un algoritmo que produce estos contra-ejemplos, uno por uno, que parece muy natural la definición de "conocer un contra-ejemplo". Entonces sabemos que no siempre debe ser contra-ejemplos que el algoritmo hace que no se genere.

7voto

user126154 Puntos 4315

Vamos $S(n)\equiv$ "$n$ aparece sólo un número finito de veces en el desarrollo decimal de $\pi$". Sabemos que, ciertamente, esto no puede ser cierto para todo $n$. También sabemos que, al menos, dos contraejemplos son en $\{1,2,3,4,5,6,7,8,9,0\}$, pero no conocemos ningún contraejemplo.

Por supuesto, esto depende, como otras respuestas, en hechos que aún son desconocidas (no pueden ser probados antes de contestar: que son los números que aparecen infinidad de veces en el desarrollo de $\pi$?) Así que, estrictamente hablando, no es una nueva respuesta, pero creo que es bueno.

6voto

sewo Puntos 58

Definir $k$ para ser 42 si la hipótesis de Riemann es verdad y 108 si es falso.

Ahora consideremos $S(n) \equiv n\ne k$.


Alternativamente considerar $S(n)$ «$n$ es mayor que $\mathit{BB}(100)$ que es el más largo tiempo en marcha de una máquina de Turing de dos símbolos que termina con 100 Estados cuando comenzó sobre una cinta vacía».

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X