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?
Respuestas
¿Demasiados anuncios?
Brad Thomas
Puntos
761
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$.)
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.
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.
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».
