Subcontabilidad

Nótese que la nomenclatura de las propiedades de numerabilidad y finitud varía sustancialmente, en parte porque muchas coinciden cuando se asume el principio del tercero excluido. Para reiterar, la discusión aquí se refiere a la propiedad definida en términos de sobreyecciones sobre el conjunto${\displaystyle X}$que se está caracterizando. El lenguaje aquí es común en los textos de teoría constructiva de conjuntos , pero el nombre subcontable también se ha dado a propiedades en términos de inyecciones fuera del conjunto que se está caracterizando.

El conjunto${\displaystyle {\mathbb {N} }}$en la definición también se puede abstraer, y en términos de la noción más general${\displaystyle X}$puede llamarse un subcociente de${\displaystyle {\mathbb {N} }}$.

Los casos importantes son aquellos en los que el conjunto en cuestión es una subclase de una clase mayor de funciones, como se estudia en la teoría de la computabilidad . Para contextualizar, recordemos que ser total no es una propiedad decidible de las funciones. De hecho, según el teorema de Rice sobre conjuntos de índices , la mayoría de los dominios de índices no son, en realidad, conjuntos computables .

No puede existir una sobreyección computable.${\displaystyle n\mapsto f_ {n}}$de${\displaystyle {\mathbb {N} }}$sobre el conjunto de funciones computables totales${\displaystyle X}$, como se demuestra a través de la función${\displaystyle n\mapsto f_{n}(n)+1}$a partir de la construcción diagonal, que nunca podría estar en tal imagen de sobreyecciones. Sin embargo, a través de los códigos de todas las posibles funciones computables parciales , que también permiten programas no terminantes, tales subconjuntos de funciones, como las funciones totales, se ven como conjuntos subcontables: Las funciones totales son el rango de algún subconjunto estricto${\displaystyle I}$de los números naturales. Al estar dominado por un conjunto incomputable de números naturales, el nombre subcontable transmite, por lo tanto, que el conjunto${\displaystyle X}$no es más grande que${\displaystyle {\mathbb {N} }}$. Al mismo tiempo, para algunas semánticas constructivas restrictivas particulares de espacios de funciones, en casos en los que${\displaystyle I}$Se ha demostrado que no es computacionalmente enumerable , tal${\displaystyle I}$entonces tampoco es contable , y lo mismo ocurre con${\displaystyle X}$.

Tenga en cuenta que no existe una correspondencia efectiva entre todos los números naturales.${\displaystyle {\mathbb {N} }}$y el conjunto de índices no acotado y no finito${\displaystyle I}$se afirma en la definición de subcontabilidad: simplemente la relación de subconjunto${\displaystyle I\subseteq {\mathbb {N} }}$. Una demostración de que${\displaystyle X}$Que un conjunto sea subcontable implica que, al mismo tiempo, es formalmente contable de forma clásica (no constructiva), pero esto no refleja ninguna contabilizabilidad efectiva. En otras palabras, el hecho de que no se pueda codificar un algoritmo que enumere todas las funciones totales en secuencia no se contempla en los axiomas clásicos sobre la existencia de conjuntos y funciones. Vemos que, según los axiomas de una teoría, la subcontabilizabilidad puede ser más demostrable que la contabilizabilidad.

En las lógicas constructivas y las teorías de conjuntos, la existencia de una función entre conjuntos infinitos (no finitos) está ligada a cuestiones de decidibilidad y posiblemente de efectividad . Allí, la propiedad de subcontabilidad se separa de la contabilidad y, por lo tanto, no es una noción redundante. El conjunto de indexación${\displaystyle I}$Se puede postular la existencia de números naturales, por ejemplo, como un subconjunto a través de axiomas de teoría de conjuntos como el esquema del axioma de separación . Entonces, por definición de${\displaystyle I\subseteq {\mathbb {N} }}$, $${\displaystyle \forall (i\in I).(i\in {\mathbb {N} }).}$$ Pero este conjunto aún podría no ser desmontable, en el sentido de que $${\displaystyle \forall (n\in {\mathbb {N} }).{\big (}(n\in I)\lor \neg (n\in I){\big )}}$$ Puede que no sea demostrable sin asumirlo como un axioma. Puede que no se pueda contar eficazmente el conjunto subcontable.${\displaystyle X}$si uno no logra mapear los números de conteo${\displaystyle {\mathbb {N} }}$en el conjunto de índices${\displaystyle I}$, por esta razón. Ser contable implica ser subcontable . En el contexto apropiado con el principio de Markov , lo recíproco es equivalente a la ley del tercero excluido , es decir, que para toda proposición${\displaystyle \phi }$sostiene${\displaystyle \phi \lor \neg \phi }$En particular, desde un punto de vista constructivo, esta dirección inversa generalmente no se cumple.

Un conjunto${\displaystyle X}$será llamado${\displaystyle \omega }$- productivo si, siempre que cualquiera de sus subconjuntos${\displaystyle W\subset X}$es el rango de alguna función parcial en${\displaystyle {\mathbb {N} }}$, siempre existe un elemento${\displaystyle d\in X\setminus W}$que permanece en el complemento de ese rango. ^{[ 1 ]}

Si existe alguna sobreyección sobre algún${\displaystyle X}$, entonces su complemento correspondiente, como se describe, sería igual al conjunto vacío.${\displaystyle X\setminus X}$y por lo tanto un conjunto subcontable nunca es${\displaystyle \omega }$-productivo. Como se definió anteriormente, la propiedad de ser${\displaystyle \omega }$-asociados productivos de la gama${\displaystyle W}$de cualquier función parcial a un valor particular${\displaystyle d\in X}$no está en el rango de funciones,${\displaystyle d\notin W}$De esta manera, un conjunto${\displaystyle X}$ser${\displaystyle \omega }$-productivo indica lo difícil que es generar todos sus elementos: no se pueden generar a partir de los naturales usando una sola función.${\displaystyle \omega }$La propiedad de productividad constituye un obstáculo para la subcontabilidad. Dado que esto también implica la incontabilidad, los argumentos diagonales suelen incluir esta noción, explícitamente desde finales de los años setenta.

Se puede establecer la imposibilidad de enumerabilidad computable de${\displaystyle X}$considerando únicamente los subconjuntos computacionalmente enumerables${\displaystyle W}$y uno puede requerir el conjunto de todos los obstáculos${\displaystyle d}$debe ser la imagen de una función de producción recursiva total, denominada así.

${\displaystyle {\mathbb {N} }\rightharpoonup X}$denota el espacio que contiene exactamente todas las funciones parciales en${\displaystyle {\mathbb {N} }}$que tienen, como su rango, solo subconjuntos${\displaystyle W}$de${\displaystyle X}$En la teoría de conjuntos, las funciones se modelan como una colección de pares. Siempre que${\displaystyle {\mathcal {P}}{\mathbb {N} }}$es un conjunto, el conjunto de conjuntos de pares${\displaystyle \cup _{I\subseteq {\mathbb {N} }}X^{I}}$puede utilizarse para caracterizar el espacio de funciones parciales en${\displaystyle {\mathbb {N} }}$. El para un${\displaystyle \omega }$-conjunto productivo${\displaystyle X}$uno encuentra

${\displaystyle \forall (w\in ({\mathbb {N} }\rightharpoonup X)).\exists (d\in X).\forall (n\in {\mathbb {N} }).w(n)\neq d.}$

Léase de forma constructiva, esto asocia cualquier función parcial.${\displaystyle w}$con un elemento${\displaystyle d}$no en ese rango de funciones. Esta propiedad enfatiza la incompatibilidad de un${\displaystyle \omega }$-conjunto productivo${\displaystyle X}$con cualquier función sobreyectiva (posiblemente parcial). A continuación, esto se aplica en el estudio de los supuestos de subcontabilidad.

Como teoría de referencia, consideramos la teoría constructiva de conjuntos CZF, que posee Reemplazo , Separación Acotada , Infinito Fuerte , es agnóstica respecto a la existencia de conjuntos potencia , pero incluye el axioma que afirma que cualquier espacio de funciones${\displaystyle Y^{X}}$está establecido, dado${\displaystyle X,Y}$También son conjuntos. En esta teoría, además es consistente afirmar que todo conjunto es subcontable. La compatibilidad de varios axiomas adicionales se analiza en esta sección mediante posibles sobreyecciones sobre un conjunto infinito de números naturales.${\displaystyle I\subseteq {\mathbb {N} }}$. Aquí${\displaystyle {\mathbb {N} }}$denotará un modelo de los números naturales estándar.

Recuerda que para las funciones${\displaystyle g\colon X\to Y}$Por definición de funcionalidad total, existe un valor de retorno único para todos los valores.${\displaystyle x\in X}$en el dominio,

${\displaystyle \exists$ !(y\in Y).g(x)=y,}

y para un conjunto subcontable, la sobreyección sigue siendo total en un subconjunto de${\displaystyle {\mathbb {N} }}$. De manera constructiva, se podrán demostrar menos afirmaciones existenciales de este tipo que en la teoría clásica.

Las situaciones que se analizan a continuación —sobre clases de potencia frente a sobre espacios de funciones— son diferentes entre sí: a diferencia de las subclases generales que definen predicados y sus valores de verdad (no necesariamente demostrablemente solo verdadero y falso), una función (que en términos de programación es terminante) hace accesible información sobre los datos para todos sus subdominios (subconjuntos de la${\displaystyle X}$). Cuando como funciones características para sus subconjuntos, las funciones, a través de sus valores de retorno, deciden la pertenencia a un subconjunto. Como la pertenencia a un conjunto generalmente definido no es necesariamente decidible, las funciones (totales)${\displaystyle X\to \{0,1\}}$no están automáticamente en biyección con todos los subconjuntos de${\displaystyle X}$. Así pues, de forma constructiva, los subconjuntos son un concepto más elaborado que las funciones características. De hecho, en el contexto de algunos axiomas no clásicos sobre CZF, incluso la clase potencia de un singleton, por ejemplo la clase${\displaystyle {\mathcal {P}}\{0\}}$de todos los subconjuntos de${\displaystyle \{0\}}$, se demuestra que es una clase apropiada.

El análisis anterior afecta las propiedades formales de las codificaciones de${\displaystyle \mathbb {R} }$Se han construido modelos para la extensión no clásica de la teoría CZF mediante postulados de subcontabilidad. ^{[ 6 ]} Estos axiomas no constructivos pueden considerarse principios de elección que, sin embargo, no tienden a aumentar significativamente la solidez teórica de las teorías.

• Existen modelos de IZF en los que todos los conjuntos con relaciones de separación son subcontables. ^{[ 7 ]}
• CZF tiene un modelo en, por ejemplo, la teoría de tipo Martin-Löf.${\displaystyle {\mathsf {ML_{1}V}}}$En esta teoría constructiva de conjuntos con espacios de funciones clásicamente no numerables, es consistente afirmar el axioma de subcontabilidad , que establece que todo conjunto es subcontable. Como se ha comentado, la teoría resultante contradice el axioma del conjunto potencia y la ley del tercero excluido .
• Más aún, algunos modelos de la teoría de conjuntos de Kripke-Platek , una teoría que no requiere el postulado del espacio funcional, incluso validan que todos los conjuntos son numerables.

La subcontabilidad como juicio de tamaño pequeño no debe confundirse con la definición matemática estándar de relaciones de cardinalidad tal como la define Cantor, donde la cardinalidad menor se define en términos de inyecciones y la igualdad de cardinalidades se define en términos de biyecciones. Constructivamente, el preorden "${\displaystyle \leq }$" sobre la clase de conjuntos no es decidible y antisimétrico. El espacio de funciones${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$(y también${\displaystyle \{0,1\}^{\mathbb {N} }}$) en una teoría de conjuntos moderadamente rica siempre se encuentra que no es ni finito ni está en biyección con${\displaystyle {\mathbb {N} }}$, por el argumento diagonal de Cantor . Esto es lo que significa ser incontable. Pero el argumento de que la cardinalidad de ese conjunto excedería, en cierto sentido, la de los números naturales se basa en una restricción a la concepción clásica del tamaño y su ordenación inducida de conjuntos por cardinalidad.

Como se ve en el ejemplo del espacio de funciones considerado en la teoría de la computabilidad , no todo subconjunto infinito de${\displaystyle {\mathbb {N} }}$necesariamente está en biyección constructiva con${\displaystyle {\mathbb {N} }}$, dejando así espacio para una distinción más refinada entre conjuntos no numerables en contextos constructivos. Motivados por las secciones anteriores, el conjunto infinito${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$puede considerarse "más pequeño" que la clase${\displaystyle {\mathcal {P}}{\mathbb {N} }}$.