Wikipedia dice que el teorema del valor intermedio "depende de (y en realidad es equivalente a) la completitud de los números reales". A continuación, ofrece un contraejemplo sencillo a la proposición análoga sobre y una demostración del teorema en términos de la propiedad de completitud.
¿Sirve un resultado análogo para los reales computables (quizá suponiendo que la función en cuestión sea computable)? Si no es así, ¿existe un buen contraejemplo?
Permítame suponer que está hablando de reales y funciones computables en el sentido de análisis computable que es uno de los enfoques más exitosos del tema. (Hay que tener cuidado, ya que existen varias nociones incompatibles de computabilidad en los reales).
En el análisis computable, el números reales computables son aquellos que pueden calcularse con la precisión deseada mediante un algoritmo finito y terminable (por ejemplo, utilizando máquinas de Turing). Hay que imaginar que se reciben aproximaciones racionales al real dado. En este tema, se dice que las funciones sobre los reales son computables, si existe un algoritmo que pueda calcular, para cualquier grado deseado de precisión, el valor de la función, para cualquier algoritmo que produzca aproximaciones a la entrada con suficiente precisión. Es decir, si queremos conocer f(x) con una precisión de epsilon, el algoritmo puede preguntar por x con cualquier delta que desee.
En Teorema del valor intermedio computable sería la afirmación de que si f es una función continua computable y f(a)< c<f(b) para reales computables a, b, c, entonces existe un real computable d con f(d)=c.
El libro Análisis computable: una introducción de Klaus Weihrauch trata exactamente esta cuestión en el ejemplo 6.3.6.
La situación básica es la siguiente. La respuesta es Sí . Si resulta que f es creciente, entonces la prueba habitual de existencia por bisección resulta eficaz. Para otras f, sin embargo, se puede utilizar una prueba de trisección. El teorema 6.3.8 dice que si f es computable y f(x)*f(z)<0, entonces f tiene un cero computable. Esto implica el teorema del valor intermedio computable anterior.
Por el contrario, el mismo teorema también dice que existe una función continua computable no negativa f sobre [0,1], tal que el conjunto de ceros de f tiene medida de Lebesgue mayor que 1/2, pero f no tiene ningún cero computable.
En resumen, si la función cruza la línea, se puede calcular un punto de cruce, pero si se queda en un lado, es posible que no se pueda calcular un punto de beso, aunque sea de beso en un conjunto de medidas grande.
Me temo que Joel ha pasado por alto un detalle importante que merece la pena señalar. Supongamos que $f$ es continua y computable en $[a,b]$ y $f(a) \cdot f(b) < 0$ . Debemos distinguir entre
existe un $x$ en $[a,b]$ tal que $f(x) = 0$ y
existe un algoritmo que acepta como entrada $f$ , $a$ y $b$ y salidas $x$ en $[a,b]$ tal que $f(x) = 0$ .
En el primer caso tenemos un clásico existencia de una entidad computable $x$ mientras que en el caso (b) tenemos a computable existencia de una entidad computable.
Estoy bastante seguro de que Weihrauch sólo demuestra 1., y es imposible demostrar 2., incluso si además suponemos que $f$ no sólo es computable sino computablemente continua, o incluso Lipshitz con una constante computable conocida. La razón básica por la que 2. no se cumple es que la $x$ no puede elegirse de forma continua con respecto a los datos de entrada: esencialmente, una perturbación muy pequeña de $f$ puede causar $x$ para saltar. Como todos los mapas computables son continuos, no podemos tener un algoritmo que compute $x$ (esto no es una prueba, sólo la idea, hay que trabajar un poco más para conseguir todos los detalles correctos).
Sin embargo, puede imponer condiciones bastante suaves a $f$ que suelen satisfacerse en la práctica. Por ejemplo, si $f$ es localmente no constante, con lo que quiero decir que para cada $y$ en $[a,b]$ podemos calcular los puntos cercanos $z$ y $w$ tal que $f(z) \neq f(w)$ entonces IVT se cumple computacionalmente en el sentido de 2. Para verlo, basta con realizar la bisección, pero evitando siempre llegar a un cero yendo a un punto cercano distinto de cero (porque o bien $f(z)$ o $f(w)$ es distinto de cero, y podemos calcular cuál). Esta condición la cumplen, por ejemplo, los polinomios no triviales, así como cualquier función diferenciable cuya derivada sólo tenga ceros aislados.
Permítanme también decir algo sobre el uso de la completitud de los reales en la IVT. La observación de Neel se traduce de la matemática constructiva a la computabilidad de la siguiente manera: podemos calcular aproximaciones arbitrariamente buenas a la IVT. El problema es que las aproximaciones no tienen por qué converger a nada, al menos no de forma computable. Clásicamente tienen un punto de acumulación, pero no podemos calcular ninguna información a partir de él.
Un segundo punto es que la IVT se mantiene no porque $\mathbb{R}$ está completa, sino porque está conectada. Paul Taylor realizó un análisis muy exhaustivo de esta cuestión en su artículo "A lambda-calculus for real analysis", véase http://www.paultaylor.eu/ASD/lamcra/ . No es una lectura fácil, pero sí muy didáctica.
Gracias en primer lugar a Andrej por llamar la atención sobre mi documento sobre la IVT , y, de hecho, por sus contribuciones a la propia obra. Este artículo es la introducción a la Dualidad Abstracta de la Piedra (mi teoría de la topología general computable) para el matemático general, pero las secciones 1 y 2 discuten primero la IVT en lenguaje tradicional. Lo que sigue son pistas sobre las ideas que encontrará allí y al final de la Sección 14.
Creo que merece la pena empezar con una advertencia sobre el computable en ${\bf R}^2$ donde se acostumbra a hablar de fijos en lugar de ceros.
Gunter Baigger descrito una endofunción computable del cuadrado. El teorema clásico de Brouwer dice que tiene un punto fijo, pero no se puede definir un punto fijo de este tipo mediante un programa . Esto contrasta con la respuesta clásica a la constructiva IVT, que o bien existe un cero computable, o bien la función se sitúa en cero a lo largo de un intervalo. (Todavía no he conseguido incorporar el contraejemplo de Baigger en mi pensamiento).
Volver a ${\bf R}^1$ tenemos un lamentable fracaso de la clásica y constructivos para entablar un debate significativo. Los primeros afirman que el resultado en toda su generalidad es "obvio", y argumentan citar fragmentos aleatorios de lo que han dicho sus oponentes para para hacerles parecer estúpidos . Por otra parte, decir que "constructivamente, el teorema del valor intermedio falla" demostrando que implica un valor intermedio excluido es igualmente un constructivo.
Incluso entre los matemáticos de la corriente dominante se confunden varios argumentos, así que me gustaría clasificarlos sobre la base de la generalidad de las funciones a los que se aplican.
Por otro lado tenemos la IVT clásica, y la aproximada constructiva que menciona Neel. Éstas se aplican a cualquier función continua con $f(0) < 0 < f(1)$ .
Hay otros resultados que imponen otras condiciones previas:
el IVT constructivo exacto, para funciones no oscilantes, descrita por Reid;
utilizando Algoritmo de Newton , para funciones continuamente diferenciables tales que $f(x)$ y $f'(x)$ nunca son simultáneamente cero; y
el Grado de Brouwer , con una condición análoga en dimensiones superiores.
Todas estas condiciones son formas más débiles de decir que la función es una mapa abierto .
Cualquier función continua $f:X\to Y$ entre espacios compactos de Hausdorff es correcto la imagen inversa $Z=f^{-1}(0)\subset X$ de $0\in Y$ es compacta (aunque posiblemente vacía).
Si $f:X\to Y$ también es un mapa abierto, entonces $Z$ es abiertamente también. Volveré sobre esa palabra dentro de un momento.
En $f$ es un mapa abierto entre espacios compactos de Hausdorff y $Z$ no es vacío, existe un subespacio compacto $K\subset X$ y un una $V\subset Y$ con $0\in V$ y $V\subset f(K)$ .
Así pues, para las variedades reales podemos pensar en $K$ es un (relleno) bola y $f(K)\setminus V$ como el distinto de cero valores que $f$ asume el esfera envolvente .
¿Podría haber olvidado que la pregunta original era sobre computabilidad ?
No, eso es exactamente lo que quiero decir.
En ${\bf R}^1$ una esfera envolvente es una intervalo a horcajadas , $[d,u]$ tal que $f(d) < 0 < f(u)$ o $f(d) > 0 > f(u)$ .
El algoritmo de intervalo (o, sospecho, cualquier algoritmo computacional) genera una secuencia convergente de intervalos a horcajadas.
De forma más abstracta, escriba $\lozenge U$ si el subconjunto abierto $U$ contiene un intervalo a horcajadas. El algoritmo de superación de intervalos (conocido históricamente como Teorema de Bolzano--Weierstrass o caza del león ) depende exactamente de la propiedad que $\lozenge$ lleva a los sindicatos a disyunciones, y en particular $$ \lozenge(U\cup V) \Longrightarrow \lozenge U \lor \lozenge V. $$ (Compárese con el grado de Brouwer, que toma uniones disjuntas a sumas de números enteros).
Afirmo, por tanto, que la formulación de la IVT constructiva debería consistir en la identificación de las condiciones adecuadas (más de continuidad pero menos que apertura) sobre $f$ para demostrar la propiedad anterior de $\lozenge$ .
Alternativamente, en lugar de restringir la función $f$ , podríamos restringir los subconjuntos abiertos $U$ y $V$ . Esto es lo que el argumento al final de Sección 14 de mi papel lo hace. Esto da una factorización $f=g\cdot p$ de cualquier continuo función $f:{\bf R}\to{\bf R}$ en un suryecto propio $p$ con fibras compactas conexas y un mapa no giratorio $g$ .
A un matemático clásico, $p$ es obviamente surjective en el sentido puntual, mientras que ésta es precisamente la situación que un constructivista considera inaceptable. Mientras tanto, están de acuerdo en encontrar ceros de $g$ .
De hecho, este proceso encuentra ceros con valor de intervalo de cualquier función continua que tome signos opuestos, que era la respuesta de sentido común a la pregunta en primer lugar.
El operador $\lozenge$ define un subespacio abierto , pero le dejo que lea el artículo para averiguar qué significa.
Esta pregunta y sus respuestas me confundieron durante un tiempo, pero creo que ahora lo entiendo, así que describiré mi experiencia con la esperanza de que ayude a otros no expertos, y los expertos puedan decirme si todavía tengo algo mal.
Mi reacción inicial fue: dada una función computable f : [a, b] → ℝ con f(a) < 0 y f(b) > 0, "por supuesto" podemos calcular un elemento z de [a, b] con f(z) = 0, de la siguiente manera: elegir c para que sea el punto medio (a+b)/2, comprobar si f(c) es positiva o negativa, informar de que z está en [a, c] o [c, b] respectivamente, y recorrer ese intervalo. Irónicamente, el problema es que f(c) podría ser exactamente 0. Si es así, podemos preguntar por su valor con una precisión arbitraria, pero nunca sabremos si es positivo, negativo o cero, por lo que no podemos obtener c como respuesta, ni garantizar que ninguno de los subintervalos [a, c] o [c, b] contenga una raíz de f.
Sin embargo, bajo la hipótesis localmente no constante, podemos elegir c' cerca de c (de modo que ambos intervalos [a, c'] y [c', b] sean menos de k veces más anchos que [a, b] para algún k fijo < 1) de modo que f(c) y f(c') sean distintos. Entonces podemos calcular f(c) y f(c') en paralelo, deteniéndonos cuando sepamos que una de ellas es positiva o negativa, como debe ocurrir eventualmente ya que ambas no pueden ser cero, y proceder como antes.
Ahora también está claro por qué clásicamente existe una raíz computable de f sin ninguna hipótesis además de la computabilidad de f: o bien algún número de la forma a + (s/2 r )(b-a) es una raíz de f-estos números son todos computables-o el algoritmo original tendrá éxito para siempre y, por tanto, computará una raíz de f.
Constructivamente, el teorema del valor intermedio falla, por lo que no existe un procedimiento computable para calcular un valor intermedio en los reales computables.
Sin embargo, el siguiente teorema sí se cumple, recordando que constructivamente todas las funciones de valor real son computables, al igual que los propios reales. Para cada función continua de valor real f en un intervalo [a,b] con a < b, para cada c entre f(a) y f(b), se cumple lo siguiente:
$\forall n.\; \exists x \in [a,b].\; |f(x) − c| < 2^{−n}$
Clásicamente, creo que puedes usar esto para derivar el teorema del valor intermedio, ya que puedes usarlo para cocinar una secuencia de Cauchy. Pero entonces pasarás fuera del conjunto de los reales computables, por supuesto.
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.
