Tesis de Church (matemáticas constructivas)

Axioma

En matemáticas constructivas , la tesis de Church es el principio que establece que todas las funciones totales son funciones computables . ${\displaystyle {\mathrm {CT} }}$

La tesis de Church-Turing , de nombre similar, establece que toda función efectivamente calculable es una función computable , colapsando así la primera noción en la segunda. es más fuerte en el sentido de que con él cada función es computable. Sin embargo, el principio constructivista también se presenta, en diferentes teorías y encarnaciones, como un axioma plenamente formal. Las formalizaciones dependen de la definición de "función" y "computable" de la teoría en cuestión. Un contexto común es la teoría de la recursión establecida desde la década de 1930. ${\displaystyle {\mathrm {CT} }}$

Adoptando como principio, entonces, para un predicado de la forma de una familia de afirmaciones de existencia (por ejemplo, a continuación) que se demuestra que no está validado para todos de manera computable, la contrapositiva del axioma implica que esto entonces no está validado por ningún función total (es decir, sin mapeo correspondiente a ). Por lo tanto, colapsa el posible alcance de la noción de función en comparación con la teoría subyacente, restringiéndola a la noción definida de función computable . A su vez, el axioma es incompatible con sistemas que validan asociaciones y evaluaciones de valores funcionales totales que también han demostrado no ser computables. Más concretamente, afecta el cálculo de prueba de una manera que hace demostrables las negaciones de algunas proposiciones clásicamente demostrables comunes. ${\displaystyle {\mathrm {CT} }}$ ${\displaystyle \exists !y.\varphi (x,y)}$ ${\displaystyle x}$ ${\displaystyle x\mapsto y}$

Por ejemplo, la aritmética de Peano es uno de esos sistemas. En lugar de esto, se puede considerar la teoría constructiva de la aritmética de Heyting con la tesis en su formulación de primer orden como un axioma adicional, relativo a las asociaciones entre números naturales. Esta teoría refuta algunas variantes universalmente cerradas de instancias del principio del tercero excluido . Es de esta forma que el axioma se muestra incompatible con . Sin embargo, es equiconsistente tanto con ambos como con la teoría dada por plus . Es decir, sumar la ley del tercero excluido o la tesis de Church no hace que la aritmética de Heyting sea inconsistente, pero sumar ambas sí. ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {CT} }_{0}}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {CT} }_{0}}$

Declaración formal

Este principio tiene formalizaciones en varios marcos matemáticos. Denotemos el predicado T de Kleene , de modo que, por ejemplo, la validez del predicado exprese que es el índice de una función computable total. Tenga en cuenta que también hay variaciones en y la extracción de valores , como funciones con valores de retorno. Aquí se expresan como predicados recursivos primitivos . Escriba para abreviar , ya que los valores juegan un papel en las formulaciones del principio. Entonces la función computable con índice termina con el valor iff . Este predicado - de sobre ternas puede expresarse mediante , a costa de introducir una notación abreviada que involucre el signo ya utilizado para la igualdad aritmética. En teorías de primer orden como , que no pueden cuantificar relaciones y funcionar directamente, se puede expresar como un esquema axiomático que dice que para cualquier relación total definible, que comprende una familia de afirmaciones de existencia válidas , estas últimas son computables en el sentido de . Para cada fórmula de dos variables, el esquema incluye el axioma ${\displaystyle T_{1}}$ ${\displaystyle \forall x\,\exists w\,T_{1}(e,x,w)}$ ${\displaystyle e}$ ${\displaystyle T_{1}}$ ${\displaystyle U}$ ${\displaystyle TU(e,x,w,y)}$ ${\displaystyle T_{1}(e,x,w)\land U(w,y)}$ ${\displaystyle y}$ ${\displaystyle e}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \exists w\,TU(e,x,w,y)}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle e,x,y}$ ${\displaystyle \{e\}(x)=y}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {CT} }}$ ${\displaystyle \exists y}$ ${\displaystyle TU}$ ${\displaystyle \varphi (x,y)}$ ${\displaystyle {\mathrm {CT} }_{0}}$

${\displaystyle {\big (}\forall x\;\exists y\;\varphi (x,y){\big )}\;\to \;\exists e\,{\big (}\forall x\;\exists y\;\exists w\;TU(e,x,w,y)\wedge \varphi (x,y){\big )}}$

En palabras: si para cada hay un , entonces de hecho hay un número de Gödel de una función recursiva parcial que, para cada , producirá una fórmula tan satisfactoria, y siendo some un número de Gödel que codifica un verificable. cálculo que atestigua el hecho de que es, de hecho, el valor de esa función en . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \varphi }$ ${\displaystyle e}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle w}$ ${\displaystyle y}$ ${\displaystyle x}$

De manera relacionada, las implicaciones de esta forma también pueden establecerse como propiedades metateóricas constructivas de las teorías. Es decir, la teoría no necesita necesariamente probar la implicación (una fórmula con ), pero la existencia de está validada metalógicamente. Entonces se dice que una teoría está cerrada bajo la regla. ${\displaystyle \to }$ ${\displaystyle e}$

Variantes

La tesis de la Iglesia Ampliada

La declaración extiende el reclamo a relaciones que están definidas y son totales en un cierto tipo de dominio. Esto se puede lograr permitiendo reducir el alcance del cuantificador universal y, por lo tanto, puede expresarse formalmente mediante el esquema: ${\displaystyle {\mathrm {ECT_{0}} }}$

${\displaystyle {\big (}\forall x\;\psi (x)\to \exists y\;\varphi (x,y){\big )}\;\to \;\exists e\,{\big (}\forall x\;\psi (x)\to \exists y\;\exists w\;TU(e,x,w,y)\wedge \varphi (x,y){\big )}}$

En lo anterior, está restringido a ser casi negativo . Para la aritmética de primer orden (donde se designa el esquema ), este medio no puede contener ninguna disyunción , y los cuantificadores existenciales sólo pueden aparecer delante de fórmulas (decidibles). En presencia del principio de Markov , las restricciones sintácticas pueden suavizarse un poco. ^[1] ${\displaystyle \psi }$ ${\displaystyle {\mathrm {ECT_{0}} }}$ ${\displaystyle \psi }$ ${\displaystyle \Delta _{0}^{0}}$ ${\displaystyle {\mathrm {MP} }}$

Cuando se considera el dominio de todos los números (por ejemplo, cuando se toma como trivial ), lo anterior se reduce a la forma anterior de la tesis de Church. ${\displaystyle \psi (x)}$ ${\displaystyle x=x}$

Estas formulaciones de primer orden son bastante sólidas en el sentido de que también constituyen una forma de elección de función: las relaciones totales contienen funciones recursivas totales.

La tesis de Church ampliada es utilizada por la escuela de matemáticas constructivas fundada por Andrey Markov .

Premisa funcional

${\displaystyle {\mathrm {CT} }_{0}!}$denota la variante más débil del principio en la que la premisa exige una existencia única (de ), es decir, el valor de retorno ya debe ser determinado. ${\displaystyle y}$

Formulación de orden superior

La primera formulación de la tesis anterior también se llama forma aritmética del principio, ya que en su formulación sólo aparecen cuantificadores sobre números. Utiliza una relación general en su antecedente. En un marco como la teoría de la recursividad, una función puede representarse como una relación funcional, otorgando un valor de salida único para cada entrada. ${\displaystyle \varphi }$

En sistemas de orden superior que pueden cuantificar funciones (totales) directamente, una forma de puede expresarse como un axioma único, diciendo que todas las funciones, desde los números naturales hasta los números naturales, son computables. En términos de los predicados recursivos primitivos, ${\displaystyle {\mathrm {CT} }}$

${\displaystyle \forall f\;\exists e\,{\big (}\forall x\;\exists w\;TU(e,x,w,f(x)){\big )}}$

Esto postula que todas las funciones son computables, en el sentido de Kleene, con un índice en la teoría. Así, también lo son todos los valores . Se puede escribir con denotando igualdad extensional . ${\displaystyle f}$ ${\displaystyle e}$ ${\displaystyle y=f(x)}$ ${\displaystyle \forall f\;\exists e\,f\cong \{e\}}$ ${\displaystyle f\cong g}$ ${\displaystyle \forall x.f(x)=g(x)}$

Por ejemplo, en la teoría de conjuntos las funciones son elementos de espacios funcionales y funcionales totales por definición. Una función total tiene un valor de retorno único para cada entrada en su dominio. Al ser conjuntos, la teoría de conjuntos tiene cuantificadores que abarcan funciones.

El principio puede considerarse como la identificación del espacio con el conjunto de funciones recursivas totales. En topoi de realizabilidad , este objeto exponencial del objeto de números naturales también se puede identificar con colecciones de mapas menos restrictivas. ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

Declaraciones más débiles

Hay formas más débiles de la tesis, llamadas de diversas formas . ${\displaystyle {\mathrm {WCT} }}$

Al insertar una doble negación antes de la afirmación de existencia del índice en la versión de orden superior, se afirma que no hay funciones no recursivas. Esto todavía restringe el espacio de funciones sin constituir un axioma de elección de función.

Una afirmación relacionada es que no se puede descartar que cualquier subconjunto decidible de naturales sea computable en el sentido de que

${\displaystyle {\big (}\forall x\ \chi (x)\lor \neg \chi (x){\big )}\;\to \;\neg \neg \exists e\,{\big (}\forall x\,{\big (}\exists w\;T_{1}(e,x,w){\big )}\leftrightarrow \chi (x){\big )}}$

El contrapositivo de esto pone cualquier predicado no computable en violación del tercero excluido, por lo que esto sigue siendo generalmente anticlásico. A diferencia de esto , como principio esto es compatible con las formulaciones del teorema del abanico . ${\displaystyle \mathrm {CT} _{0}}$

Se podrán definir variantes para locales relacionados . Por ejemplo, un principio que siempre garantiza la existencia de una función recursiva total en algún conjunto binario discreto que valida una de las disyunciones. Sin la doble negación, esto puede denotarse . ${\displaystyle \forall x\ \psi _{\mathrm {left} }(x)\lor \psi _{\mathrm {right} }(x)}$ ${\displaystyle {\mathbb {N} }\to \{\mathrm {left} ,\mathrm {right} \}}$ ${\displaystyle \mathrm {CT} _{0}^{\lor }}$

Relación con la lógica clásica

El esquema , cuando se agrega a sistemas constructivos como , implica la negación de la versión universalmente cuantificada de la ley del tercero excluido para algunos predicados. Como ejemplo, se ha demostrado que el problema de la detención no es computablemente decidible, pero suponiendo la lógica clásica, es una tautología que toda máquina de Turing se detiene o no se detiene ante una entrada determinada. Asumiendo además la tesis de Church, se llega a la conclusión de que esto es computable: una contradicción. Con un poco más de detalle: en sistemas suficientemente fuertes, como , es posible expresar la relación asociada con la pregunta detenida, relacionando cualquier código de una enumeración de máquinas de Turing y valores de . Asumiendo la tautología clásica anterior, esta relación puede demostrarse total, es decir, constituye una función que regresa si la máquina se detiene y si no se detiene. Pero plus refuta esta consecuencia de la ley del tercero excluido, por ejemplo. ${\displaystyle {\mathrm {CT} }_{0}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle h}$ ${\displaystyle \{0,1\}}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {CT} }_{0}}$

El principio también rechaza principios como el cambio de doble negación (conmutatividad de la cuantificación universal con una doble negación).

La forma de axioma único de con anterior es consistente con algunos sistemas clásicos débiles que no tienen la fuerza para formar funciones como la función del párrafo anterior. Por ejemplo, la aritmética clásica débil de segundo orden es consistente con este axioma único, porque tiene un modelo en el que cada función es computable. Sin embargo, la forma de un solo axioma se vuelve inconsistente con el tercero excluido en cualquier sistema que tenga axiomas suficientes para probar la existencia de funciones como la función . Por ejemplo, adopción de variantes de elección contable , como elección única para los cuantificadores numéricos, ${\displaystyle {\mathrm {CT} }}$ ${\displaystyle \forall f}$ ${\displaystyle {\mathsf {RCA_{0}}}}$ ${\displaystyle {\mathsf {RCA_{0}}}}$ ${\displaystyle h}$

${\displaystyle \forall n\;\exists !m\;\phi (n,m)\to \exists a\;\forall k\;\phi (k,a_{k}),}$

donde denota una secuencia, estropea esta consistencia. ${\displaystyle a}$

La formulación de primer orden ya incluye el poder de dicho principio de comprensión de funciones a través de funciones enumeradas. ${\displaystyle {\mathrm {CT} }_{0}}$

Por lo general, se puede demostrar que las subteorías formuladas de manera constructiva están cerradas bajo el gobierno de una Iglesia y, por lo tanto, el principio correspondiente es compatible. Pero como implicación ( ) no puede ser probado por tales teorías, ya que eso haría que la teoría clásica más fuerte fuera inconsistente. ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle \to }$

Realizadores y metalógicos.

Esta tesis anterior se puede caracterizar diciendo que una oración es verdadera si es realizable computablemente . Esto se refleja en las siguientes equivalencias metateóricas: ^[2]

${\displaystyle {\mathsf {HA}}+{\mathrm {ECT_{0}} }\vdash \varphi \leftrightarrow \exists n\,(n\Vdash \varphi )}$

y

${\displaystyle {\mathsf {HA}}+{\mathrm {ECT_{0}} }\vdash \varphi \;\iff \;{\mathsf {HA}}\vdash \exists n\,(n\Vdash \varphi )}$

Aquí " " es sólo la equivalencia en la teoría aritmética, mientras que " " denota la equivalencia metateórica. Dado , el predicado se lee como " ". En palabras, el primer resultado anterior establece que es demostrable en más que una oración es verdadera si es realizable. Pero también, el segundo resultado anterior establece que es demostrable en plus si es demostrable realizable en just . ${\displaystyle \leftrightarrow }$ ${\displaystyle \iff }$ ${\displaystyle \varphi }$ ${\displaystyle n\Vdash \varphi }$ ${\displaystyle n{\text{ realises }}\varphi }$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {ECT_{0}} }}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {ECT_{0}} }}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathsf {HA}}}$

Para el siguiente teorema metalógico, recuerde que no es constructivo y carece de la propiedad de existencia , mientras que la aritmética de Heyting la exhibe: ${\displaystyle {\mathsf {PA}}}$

${\displaystyle {\mathsf {HA}}\vdash \exists n.\phi (n)\implies {\text{exists}}\;{\mathrm {n} }\ {\mathsf {HA}}\vdash \phi ({\underline {\mathrm {n} }})}$

La segunda equivalencia anterior se puede ampliar de la siguiente manera: ${\displaystyle {\mathrm {MP} }}$

${\displaystyle {\mathsf {HA}}+{\mathrm {ECT_{0}} }+{\mathrm {MP} }\vdash \varphi \;\iff \;{\text{exists}}\;{\mathrm {n} }\ {\mathsf {PA}}\vdash ({\underline {\mathrm {n} }}\Vdash \varphi )}$

En este caso, el cuantificador existencial debe estar afuera . En palabras, es demostrable en más y si se puede establecer metateóricamente que existe algún número tal que el número estándar correspondiente en , denotado , realiza demostrablemente . Suponiendo que, junto con variantes alternativas de la tesis de Church, se hayan obtenido más afirmaciones de existencia metalógicas. ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {ECT_{0}} }}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {n} }}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\underline {\mathrm {n} }}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathrm {MP} }}$

Ver también

• Función computable
• Propiedades de disyunción y existencia.
• Realizabilidad

Referencias

1. Troelstra, AS, van Dalen D., Constructivismo en matemáticas: una introducción 1 ; Estudios de Lógica y Fundamentos de las Matemáticas; Springer, 1988; pag. 206
2. Troelstra, AS Investigación metamatemática del análisis y la aritmética intuicionista . Vol 344 de Apuntes de conferencias sobre matemáticas; Saltador, 1973

• Elliott Mendelson (1990) "Reflexiones sobre la tesis y las pruebas matemáticas de Church", Journal of Philosophy 87(5): 225–233.