El hacinamiento de los límites de la no-constructivity sin cruzar?

Question

Puede cualquier sentido de ser de mi vaga sensación de que algunas pruebas en Ramsey teoría están tan cerca como usted puede conseguir a la no-constructiva pruebas sin cruzar la línea? ¿Hay alguna manera de hacer este preciso?

PS: OK, la versión corta de la elaboración de lo que escribí en los comentarios de abajo va como esto: En muchas áreas de las matemáticas, si quieres demostrar que $X$ existe alguna manera de averiguar algo plausible conjetura acerca de que el objeto $X$ es o dónde encontrar $X$, y, a continuación, trabajar en averiguar cómo rigurosamente demostrar que $X$ es. En la teoría de Ramsey, parece como si usted tiene un eliminar sistemáticamente a todos los sospechosos, uno por uno, y hasta que nada queda sino $X$.

Bien, un ejemplo concreto: Poco antes de la publicación de este yo había trabajado a través de este elemental ejercicio: En un conjunto de $(n-1)m+1$ de la gente, muestran que no hay un conjunto de $m$ que son mutuamente no conocen o hay uno que sabe, al menos, $n$ otros.

Se me ocurrió una descripción de un algoritmo, de la siguiente manera.

$(1)$ Principio deje $A=\varnothing$. Vamos incremento $A$ mediante la adición de un nuevo miembro a él tantas veces como este algoritmo ocasiones en las que, además de. Los miembros del conjunto, $A$ siempre será mutuamente ignoraba.

$(2)$ Hace algunos miembros de $A$ conoce al menos a $n$ no miembros de $A$? Si es así, DEJE de hacerlo. Hemos terminado.

$(3)$ Lo contrario, cada uno de los miembros de $A$ conoce en la mayoría de las $n-1$ no miembros de $A$, por lo que el número total de personas conocidos por los miembros de $A$ es en la mayoría de las $(n-1)|A|\le(n-1)m<(n-1)m+1$. En ese caso, al menos uno que no sea miembro de $A$ es desconocido para todos los miembros de $A$. Deje que el nuevo valor de $A$$A\cup\{\text{that one non-member of $$}\}$.

$(4)$ Si $|A|=m$ la PARADA; hemos terminado. En caso contrario, devuelve a $(2)$ e ir de allí.

Answer 1

Una razón de este fenómeno es que el finito versión del teorema de Ramsey, en el final, se basa en el principio del palomar para el caso base de un argumento inductivo. (De hecho, una forma razonable de entender el teorema de Ramsey es que es sólo una declaración más fuerte del principio del palomar). Debido a la natural algoritmo que da cuenta el principio del palomar es una búsqueda de fuerza bruta, los algoritmos para el caso general, con el mismo carácter.

Para un ejemplo concreto, supongamos que acabamos de 2 colores y coloreando los embarazos únicos, y desea un conjunto homogéneo de tamaño 100. Sabemos que no es suficiente para color 199 elementos, pero dado 199 elementos, la única manera sencilla de encontrar un conjunto homogéneo de tamaño 100 es buscar a través de los elementos hasta encontrar 100 del mismo color. No existe una estructura en el problema que se puede intentar explotar, sólo 199 elementos de cada uno de los cuales tiene uno de los dos colores.

Sin embargo, por supuesto, una búsqueda por fuerza bruta sobre un conjunto finito buscando elementos con un decidable propiedad está perfectamente constructiva, cuando ya sabemos que la búsqueda tenga éxito.

En el pleno del teorema de Ramsey, donde hemos color $[\mathbb{N}]^k$ $l$ colores y quieren un infinito conjunto homogéneo, aspectos de la computabilidad del principio del palomar llegar a ser muy relevante.

El principio del palomar indica que si $\mathbb{N} = C_1 \cup C_2$, entonces al menos uno de $C_1$ $C_2$ es infinito. Ahora bien, si tenemos una computable 2 para colorear de $\mathbb{N}$, no será computable la solución a esa instancia de Ramsey del teorema: $C_1$ o $C_2$. Pero no hay ninguna manera de determinar, dado algoritmos para$C_1$$C_2$, que de ellos va a ser infinito, como una función de los algoritmos. Así, podemos decir que la prueba de Ramsey del teorema de exponente 1 es "eficaz", pero no "uniforme".

Esto es importante cuando nos fijamos en exponente $2$. Ahora tenemos una coloración $f$ $[\mathbb{N}]^2$ y queremos que un conjunto infinito $H$ $[H]^2$ monocromática. Una forma común de la prueba comienza con esta construcción: para cada una de las $n \in \mathbb{N}$, inducir una coloración $f_n$ $\{n+1, n+2, \ldots\}$ a través de la regla de $f_n(m) = f(n,m)$. Cada una de estas funciones $f_n$ debe tener un infinito conjunto monocromático, por inducción.

Pero, incluso si $f$ es computable, no puede ser capaz de decirle a como una función de la $n$ si $f_n$ tiene una infinita monocromática conjunto de color 1, o sea que tiene uno de color 2. Que falta de uniformidad en la prueba de el principio del palomar se convierte en un obstáculo para la eficacia de la prueba de Ramsey del teorema de 2 colores y el exponente 2. De hecho, la computabilidad de Ramsey del teorema ha sido muy estudiado, y, en particular, sabemos que no son computables 2-colorantes de $[\mathbb{N}]^2$ sin computable infinito monocromática conjunto. El caso finito, mientras que la perfección constructiva, refleja algunos de los nonconstructivity de la general del teorema de Ramsey.

Answer 2

El comentario fue demasiado corto.

Mi intuición es que una prueba es constructiva si se da un algoritmo que construye una representación del objeto deseado (el algoritmo de aquí, tiene un poco significado más amplio que la noción usual en ciencias de la computación). Sin embargo, el algoritmo puede no ser factible, a/intracable, es decir, el número de operaciones que se requiere puede quedar inservible, incluso para pequeñas entradas (por ejemplo, véase esta clase).

En tal caso sabemos que el algoritmo existe, pero no nos ayuda en la construcción del objeto. Curiosamente nos encontramos en la situación que es prácticamente (lo que sea que signifique en este resumen) no es mejor que uno con los no-constructiva de la prueba. Yo diría que esto está muy cerca de su límite y Ramsey teoría no impliquen el uso de números tan enormes que mi imaginación tiene problemas con el manejo de ellos.

No estoy seguro de si esto es más preciso que su descripción, pero sin embargo tengo la esperanza de que ayuda a $\ddot\smile$