157 votos

Ejemplos de posibles contraejemplos

Definir un "eventual contraejemplo" para ser

  • $P(a) = T $ for $a < n$

  • $P(n) = F$

  • % # % # % 'razonable' conjetura de hacer.

donde 'razonable' está abierto a la interpretación, y declaraciones similares racional, real, o de manera más abstracta de conjuntos ordenados de $n$ is sufficiently large for $P(n) = T\ \ \forall n \in \mathbb{N}$ a pertenecer a son respuestas aceptables.

¿Cuáles son algunos ejemplos de posibles contraejemplos, famoso o no, y hacer diferentes eventual contraejemplos compartir cualquier rasgos comunes? Podríamos construir un "sistema de alerta temprana" conjunto de heurísticas para aparentemente plausible teoremas?

edit: La Polya conjetura es un buen ejemplo de lo que yo estaba tratando de hacer, pero las respuestas no están restringidos a la teoría de números o cualquier área.

147voto

Gerry Myerson Puntos 23836

Una vez se conjeturó que factores de %#% #%.

147voto

Richard Stanley Puntos 19788

El entero menos positivo para que la igualdad $$ \left\lceil \frac{2}{2^{1/n}-1}\right\rceil = \left\lfloor \frac{2n}{\log 2} \right\rfloor. $$ falla es %#% #%. Ver http://oeis.org/A129935.

Otro ejemplo que me gusta es la número #% #%, la cardinalidad del continuo.

66voto

Macho Matt Puntos 595

Ley fuerte de números pequeños de Guy.

Steve

54voto

Gerry Myerson Puntos 23836

Estoy tratando de reconstruir un ejemplo que vi en algún lugar hace algunos años. Es algo como esto: %#% #% (cuando el MCD es 1968751).

5voto

thedeeno Puntos 12553

La esencia del fenómeno de la eventual contraejemplos es que un cierto patrón que tiene entre números pequeños, resulta no ser universal. En el mejor de los ejemplos, tales como los ejemplos proporcionados en las otras respuestas, que he disfrutado mucho, lo que tenemos es un fácil de describir la propiedad $P(n)$, cuya primera fallando instancia es muy grande en comparación. De hecho, la calidad de la respuesta que puede ser medido por la diferencia entre el tamaño de la descripción de la propiedad y el tamaño de la primera fallando instancia de ella. Cuando un fácil describir la propiedad es válida para un tiempo muy largo, y luego, de repente falla en algún número muy grande, nos sorprende. Por lo tanto, a mi juicio, el fenómeno de la eventual contraejemplos está íntimamente envuelto con la posibilidad de proporcionar descripciones muy breves de grandes números.

Seguramente todos somos capaces fácilmente para proporcionar una breve descripción de algunos números muy grandes, tales como % # % # % -mente bogglingly enorme.

Todos estos ejemplos, descripciones cortas de los grandes números, pueden ser sistemáticamente transformado en casos de eventual contraejemplos. Por si ^{100}$ or ^{2^{100!}}$. In order to go beyond exponentiation and factorials, we might make use of other easily described functions exhibiting even more enormous growth. The Ackermann function, for example, defined by a simple one-line recursion, has diagonal values 1, 3, 7, 61, ^{2^{2^{65536}}}$, with the next value $A(5)$ sí. Por lo tanto, se hace muy bien por la medida de la calidad que he mencionado anteriormente.

Así que en mi opinión, el verdadero problema es: ¿cuáles son los números más grandes que se pueden describir por una descripción muy breve?

Esta pregunta puede ser hecha precisa que requiere la descripción para ser expresable en un determinado lenguaje formal. Una vez que el idioma es lo suficientemente rica, sin embargo, este problema será, sin duda wade en interesantes fundacional de aguas, para la cuestión de si una determinada descripción éxito en la descripción de un número---por ejemplo, "la longitud de la menor prueba de una contradicción en ZFC"---puede ser independiente de nuestros axiomas básicos, incluso si es enorme.

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