Tesis de Church (matemática constructiva)

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, que lleva el mismo nombre, afirma que toda función efectivamente calculable es una función computable , con lo que la primera noción se fusiona con la segunda. es más fuerte en el sentido de que con ella toda función es computable. Sin embargo, el principio constructivista también se da, en diferentes teorías y encarnaciones, como un axioma completamente 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 tal como se estableció 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 se valida para todos de manera computable, el contrapositivo del axioma implica que esto no se valida entonces por ninguna función total (es decir, ninguna aplicación correspondiente a ). Por lo tanto, colapsa el alcance posible 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 se demuestra que no son computables. Más concretamente, afecta al cálculo de pruebas 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 un sistema de este tipo. En lugar de ella, 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, concerniente a las asociaciones entre números naturales. Esta teoría refuta algunas variantes universalmente cerradas de instancias del principio del medio excluido . Es de esta manera que el axioma se muestra incompatible con . Sin embargo, es equiconsistente con ambos , así como con la teoría dada por más . Es decir, agregar la ley del medio excluido o la tesis de Church no hace que la aritmética de Heyting sea inconsistente, pero agregar 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. Sea el predicado T de Kleene , de modo que, por ejemplo, la validez del predicado expresa que es el índice de una función computable total. Nótese 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. Por lo tanto, la función computable con índice termina en con valor si y solo si . Este -predicado de sobre tripletas puede expresarse por , a costa de introducir una notación abreviada que involucra el signo ya utilizado para la igualdad aritmética. En teorías de primer orden como , que no pueden cuantificar sobre relaciones y funcionan directamente, puede enunciarse 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 satisfactorio , entonces de hecho hay un que es el número de Gödel de una función recursiva parcial que, para cada , producirá tal satisfactorio la fórmula - y con algunos siendo un número de Gödel que codifica un cálculo verificable que da testimonio del 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 similar, 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 se valida metalógicamente. Se dice entonces que una teoría está cerrada bajo la regla. ${\displaystyle \to }$ ${\displaystyle e}$

Variantes

Tesis de Church extendida

La afirmación extiende la afirmación a relaciones que están definidas y son totales en un cierto tipo de dominio. Esto se puede lograr permitiendo limitar el alcance del cuantificador universal y, por lo tanto, se puede expresar 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, se restringe a ser casi negativo . Para la aritmética de primer orden (donde el esquema se designa ), esto significa que no puede contener ninguna disyunción , y los cuantificadores existenciales solo pueden aparecer delante de fórmulas (decidibles). En presencia del principio de Markov , las restricciones sintácticas pueden flexibilizarse un poco. ^[1] ${\displaystyle \psi }$ ${\displaystyle {\mathrm {ECT_{0}} }}$ ${\displaystyle \psi }$ ${\displaystyle \Delta _{0}^{0}}$ ${\displaystyle {\mathrm {MP} }}$

Al considerar el dominio de todos los números (por ejemplo, al tomar 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 fuertes ya que también constituyen una forma de elección de función: las relaciones totales contienen funciones recursivas totales.

La tesis de Church extendida 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 existencia única (de ), es decir, el valor de retorno ya tiene que estar determinado. ${\displaystyle y}$

Formulación de orden superior

La primera formulación de la tesis anterior también se denomina forma aritmética del principio, ya que en su formulación solo aparecen cuantificadores sobre números. Utiliza una relación general en su antecedente. En un marco como la teoría de la recursión, 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 directamente funciones (totales), se puede enunciar una forma de como un único axioma, diciendo que toda función desde los números naturales hasta los números naturales es computable. 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. Por lo tanto, también lo son todos los valores . Se puede escribir con , que denota 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 de funciones y funciones 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 los topos de realizabilidad , este objeto exponencial del objeto de los números naturales también puede identificarse con conjuntos de aplicaciones menos restrictivos. ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

Declaraciones más débiles

Existen formas más débiles de la tesis, denominadas 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 existen funciones no recursivas. Esto aún restringe el espacio de funciones, pero no constituye un axioma de elección de función.

Una afirmación relacionada es que no se puede descartar que cualquier subconjunto decidible de números 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 a cualquier predicado no computable en violación del tercero excluido, por lo que esto sigue siendo generalmente anticlásico. A diferencia de , como principio esto es compatible con las formulaciones del teorema del abanico . ${\displaystyle \mathrm {CT} _{0}}$

Se pueden definir variantes para premisas relacionadas . Por ejemplo, un principio que siempre conceda la existencia de una función recursiva total en algún conjunto binario discreto que valide uno de los disyuntos. Sin la doble negación, esto se puede denotar como . ${\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 añade a sistemas constructivos como , implica la negación de la versión cuantificada universalmente de la ley del medio excluido para algunos predicados. Como ejemplo, el problema de la detención no es decidible de forma computacional , pero suponiendo la lógica clásica es una tautología que cada máquina de Turing se detiene o no se detiene en una entrada dada. Suponiendo además la tesis de Church, uno a su vez concluye 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 cuestión de la detención, relacionando cualquier código de una enumeración de máquinas de Turing y valores de . Suponiendo la tautología clásica anterior, esta relación puede probarse total, es decir, constituye una función que retorna si la máquina se detiene y si no se detiene. Pero además refuta esta consecuencia de la ley del medio 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}}$

Principios como el del doble desplazamiento de la negación (conmutatividad de la cuantificación universal con una doble negación) también son rechazados por el principio.

La forma de axioma único de con anterioridad 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 axioma único se vuelve inconsistente con el medio excluido en cualquier sistema que tenga axiomas suficientes para demostrar la existencia de funciones como la función . Por ejemplo, la adopción de variantes de elección contable , como la 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, arruina esta consistencia. ${\displaystyle a}$

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

Normalmente, se puede demostrar que las subteorías de la estructura formuladas de manera constructiva están cerradas bajo la regla de una Iglesia y, por lo tanto, el principio correspondiente es compatible. Pero, como implicación ( ), no se puede probar mediante 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 metalogicos

La tesis anterior puede caracterizarse como que una oración es verdadera si y solo si es computablemente realizable . 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 simplemente la equivalencia en la teoría aritmética, mientras que " " denota la equivalencia metateórica. Para dado , el predicado se lee como " ". En palabras, el primer resultado anterior establece que es demostrable en plus que una oración es verdadera si y solo si es realizable. Pero también, el segundo resultado anterior establece que es demostrable en plus si y solo si es demostrablemente 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, recordemos que no es constructivo y carece de la propiedad de existencia , mientras que la aritmética de Heyting la muestra: ${\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 fuera . En otras palabras, es demostrable en más y también si uno puede establecer metateóricamente que existe algún número tal que el numeral estándar correspondiente en , denotado , realiza demostrablemente . Suponiendo junto con variantes alternativas de la tesis de Church, se han obtenido más afirmaciones metalógicas de existencia de este tipo. ${\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} }}$

Véase 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; pág. 206
2. Troelstra, AS Investigación metamatemática de la aritmética y el análisis intuicionistas . Vol. 344 de Lecture Notes in Mathematics; Springer, 1973

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