Aproximado teorema del valor intermedio en el más puro constructivo de las matemáticas

Question

El ordinario teorema del valor intermedio (IVT) no es demostrable en la construcción de las matemáticas. Para mostrar esto, se puede construir un Brouwerian "débil contraejemplo" y también promover a un preciso contramodelo: la idea básica es que la raíz no pueden depender de forma continua o computably en la función, ya que una pequeña perturbación en el valor de la función puede causar una raíz a aparecer o desaparecer.

Sin embargo, hay muchas variantes de la formación profesional inicial que forma constructiva demostrable. Esta pregunta es sobre el aproximado de IVT, que dice que si $f(a)<0<f(b)$, entonces para cualquier $\epsilon>0$ hay un punto de $x$ con $|f(x)|<\epsilon$. Parece ser bien conocido que la aproximación de formación profesional inicial puede ser probado suponiendo (1) contable (o tal vez dependiente) la elección, o (2) que $f$ es uniformemente continua. Este documento contiene muchas versiones de aproximado de IVT el uso de un poco más débil de la hipótesis tales como "fuerte continuidad" de $f$. Pero me gustaría saber:

Puede aproximado de IVT ser probada de manera constructiva acerca de un arbitrario (pointwise) función continua $f$, sin utilizar ningún tipo de elección o del medio excluido (por ejemplo, en la matemática válida en cualquier primaria topos con NSIN)?

Si la respuesta es no, me gustaría ver al menos una débil contraejemplo, o mejor aún, un específico contramodelo (por ejemplo, un topos en el que se produce un error).

Edit: Para aclarar, las funciones en cuestión son de los números reales (o algún intervalo de la misma) a los números reales. Voy a aceptar una respuesta que define "los números reales", ya sea como clases de equivalencia de secuencias de Cauchy o como Dedekind cortes (pero no como un "setoid" de secuencias de Cauchy).

Answer 1

He aquí una constructivo prueba de los aproximadamente Intermedio Teorema del Valor de pointwise continuidad, no depender Dependiente de la Elección y no depender de un setoid la construcción de los reales.

Teorema: Si $f$ es pointwise continua con $f(a)<0, \ f(b)>0,\ \epsilon>0$, entonces hay algo de $x$ con $|f(x)|<\epsilon$.

Prueba: Definir de la siguiente forma inductiva: $$a_1 = a$$ $$b_1 = b$$ $$c_n = (a_n+b_n) / 2$$ $$d_n = \max( 0, \min( \textstyle\frac{1}{2}+ \frac{ f(c_n)}{\epsilon}, 1))$$ $$a_{n+1} = c_n - d_n (b-a)/2^n $$ $$b_{n+1} = b_n - d_n (b-a)/2^n$$ A continuación, $b_n - a_n = (b-a)/2^{n-1}.$ Por lo que el $c_n$'s convergen para algunos $c.$

Por pointwise continuidad en $c$, deje $\delta$ ser tal que $ |x-c|<\delta$ implica $|f(x)-f(c)| < \epsilon.$

Reclamo: Para cualquier $m\in\mathbb{N}$, ya sea (i) $\exists j \le m,\ |f(c_j)| < \epsilon$ o (ii) $f(a_m) < 0 $ e$ f(b_m) > 0$.

La prueba del teorema de reclamación:

Elija $c_m$ tal que $|c-c_m| < \delta / 2$ e $(a-b)/2^m < \delta / 2$, y aplicar la reclamación.

En el primer caso, de la reclamación, el teorema es inmediata.

En el segundo caso de la reclamación, $$ |c-a_m| \le |c-c_m| + |c_m-a_m| < \delta, \text{ so }|f(c)-f(a_m)| < \epsilon$$ $$ |c-b_m| \le |c-c_m| + |c_m-b_m| < \delta, \text{ so }|f(c)-f(b_m)| < \epsilon$$ Por lo $f(c)$ está dentro de $\epsilon$ tanto de un negativo y un número positivo, y $| f(c)| < \epsilon$, QED.

Prueba de reclamación por inducción en $m$. El caso base es dado por $ f(a) < 0, \ f(b) > 0.$

Ahora suponga que la demanda por $m$. En el caso (i), para algunos $ j < m,\ |f(c_j)| < \epsilon$, y el paso inductivo es trivial.

En el caso (ii), el uso de tricotomía, ya sea con $f(c_m) < -\epsilon/2, \ |f(c_m)| < \epsilon$ o $f(c_m) > \epsilon/2.$ Si $|f(c_m)| < \epsilon$, entonces el paso inductivo es nuevo trivial. Si $f(c_m) > \epsilon/2$, luego $$d_m = 1$$ $$a_{m+1} = a_m, \text{ so }f(a_{m+1}) < 0$$ $$b_{m+1} = c_m,\text{ so } f(b_{m+1}) > 0$$

Si $f(c_m) < - \epsilon/2$, luego $$d_m = 0$$ $$a_{m+1} = c_m, \text{ so }f(a_{m+1}) < 0$$ $$b_{m+1} = b_m,\text{ so } f(b_{m+1}) > 0$$

QED (reclamación y teorema).

Creo que esto funciona, espero a ver qué MO dice.

Answer 2

Actualización: esta respuesta fue antes de la edición a la pregunta rechazo de este setoid enfoque.

Podemos probar el aproximado teorema del valor intermedio uso constructivo de sólo pointwise continuidad. La prueba tiene la misma sensación como $\forall x \in \mathbf{R}\ \exists n \in \mathbf{N} \ n > r$, que es de forma constructiva válida, pero con $n$ elegido de una manera que depende de la particular racional de la secuencia de la definición de $x$.

Un número real $x$ se define como una secuencia de racionales $x^n$ tal que $|x^m-x^n|\le 1/m+1/n$. (Ya que no hay exponentes positivos en esta prueba, todos positivos superíndices serán estas aproximaciones racionales.) Por lo $|x-x^n| \le 1/n$ y, por ejemplo, podemos elegir el $n$ a $\lceil x^1 \rceil + 2.$

Ahora se nos da $a,\ b,\ \epsilon,\ f$ como en la pregunta. Vamos $a_1=a$, $b_1=b$.

$$\text{Let }c_n = (a_n+b_n)/2.$$ $$\text{If }f(c_n)^n < 0,\text{ then let }a_{n+1} = c_n,\ b_{n+1}=b_n.$$ $$\text{If }f(c_n)^n \ge 0,\text{ then let }a_{n+1} = a_n,\ b_{n+1}=c_n.$$

A diferencia de la versión que se hace referencia en el 11/16 comentario, esto es determinista en cada etapa, por lo que la construcción de la $c$'s sólo requiere la única opción y no dependiente de la elección. (Si hay un uso oculto de dependiente de la elección, por favor hágamelo saber!)

Los intervalos de $[a_n,b_n]$ tienen longitudes decrecientes por mitades con la intersección $c$. Además, $f(a_n)^n < 1/n$ e $f(b_n)^n \ge -1/n$ para todos los $n$.

Por pointwise continuidad de $f$, elija $\delta$ tal que $|x-c|<\delta$ implica $|f(x)-f(c)|<\epsilon/3$.

Elija $m$ con $(a-b)2^{-m} < \delta$ e $1/m < \epsilon/3$. Entonces

$$|a_m-c|<(a-b)2^{-m} < \delta, \ \text{ and }\ f(c) \le f(a_m) + \epsilon/3 \le f(a_m)^m + 1/m + \epsilon/3 \le \epsilon.$$ Por comparación similar con el $b$s, $f(c) \ge -\epsilon$. Por lo $c$ es de la forma deseada para demostrar el aproximado teorema del valor intermedio, QED.

Answer 3

[Acabo de empezar aquí y no tienen la suficiente reputación para comentar...así que estoy de tipo forzado a dar una respuesta.]

Creo que hay una manera diferente a eliminar contables de elección en la prueba de aIVT (aproximado teorema del valor intermedio). He descrito de esta manera en el constructivas-noticias del foro https://groups.google.com/forum/#!tema/constructivenews/e3JfKk_W2jI

No estoy seguro de si es una descripción demasiado especialista para publicar aquí. Pero lo que se reduce a esto: en que Matt primera prueba, el uso de interseccion, hay un uso oculto de contables elección. Porque para evaluar el número real $f(c_n)$, uno tiene que elegir a un representante de su clase de equivalencia. (Este es brillantemente evitarse en Mate de la segunda prueba).

Mi primer intento de evitar esta involucrado mirando recursiva de las matemáticas. Si tomamos $a,b$ e $f$ a ser recursivo, entonces si vamos a elegir (recursivo) representantes de la $a', b'$ podemos aplicar la interseccion método sin usar contables elección. Porque la toma de la media es una función recursiva $m(a,b)=\frac{(a+b)}{2}$, vemos que cada proceso iterativo de construcción y evaluación de las $f(c_n)$ es recursivo en $a', b'$.

Este enfoque puede ser caracterizado como: `sólo necesitamos contables elección, porque los objetos que estamos trabajando con han sido insuficientemente especificados de antemano'. En otras palabras: hemos dejado demasiado elección en $a,b$ E $f$

Sin embargo creo que hay una forma más general para evitar la elección en la construcción de $a,b$ E $f$. Mediante la descripción de R y continua de funciones reales de una manera diferente, es decir, R como #cociente de funciones reales y continuas como #-morfismos en Baire el espacio, podemos aplicar la interseccion método sin usar contables elección.

La razón de esto es comparable a la situación recursiva. Si retomamos el #a representantes de las $a'',b''$ de %de $a,b$ Y #a representantes de las $m'', f''$ de las funciones de $m, f$, no hay opción a la izquierda en la interseccion procedimiento de uso de $a'', b'', m'', f''$, debido a la composición de la #-morfismos es totalmente determinista.

En CLASE, INT y RUSS creo que podemos demostrar que toda función real continua puede ser representado por un #-morfismos. Esta prueba puede encontrarse en mi libro Natural Topología [pero lo que realmente debe ser comprobada por más personas]. Preprint que he presentado al LMC hace tres años (!) es todavía bajo del revisor de cuenta.

Así que creo que el uso de #-morfismos en BISH es una manera de evitar contables de elección en los teoremas comparable a aIVT. Desde #cociente de representaciones se puede encontrar para cualquier polaco espacio, esto va mucho más allá de funciones reales.