En matemática constructiva , una colecciónes contable si existe una sobreyección parcial de los números naturales sobre él. Esto puede expresarse como
dónde son los números de conteo sin tener en cuenta la aritmética) y donde denota que es una función sobreyectiva de sobre . En otras palabras, todos los elementos de una colección contable están funcionalmente en la imagen de un conjunto de indexación de números de conteo y así el conjunto puede entenderse como dominado por el conjunto contable .
Discusión
Ejemplo
Un caso importante es donde denota alguna subclase de una clase más grande de funciones estudiadas en la teoría de la computabilidad .
Considere la subclase de funciones totales y observe que ser total no es una propiedad decidible, es decir, no puede haber una biyección constructiva entre las funciones totales y los números naturales. Sin embargo, mediante la enumeración de los códigos de todas las funciones parciales posibles (que también incluye funciones no terminantes), se considera que los subconjuntos de esas, como las funciones totales, son conjuntos subcontables. Tenga en cuenta que según el teorema de Rice sobre conjuntos de índices , la mayoría de los dominiosno son recursivas. De hecho, no hay un mapa efectivo entre todos los números de conteo. y el conjunto de indexación infinito (no finito) se afirma aquí, simplemente la relación de subconjunto . Estar dominado por un conjunto de números constructivamente no contables, el nombre subcontable, por lo tanto, transmite que el conjunto incontable no es más grande que .
La demostración de que es subcontable también implica que es clásicamente (no constructivamente) formalmente contable, pero esto no refleja ninguna contabilización efectiva. En otras palabras, el hecho de que un algoritmo que enumere todas las funciones totales en secuencia no pueda codificarse no es captado por los axiomas clásicos con respecto a la existencia de conjuntos y funciones. Vemos que, dependiendo de los axiomas, es más probable que la sub-contabilidad sea demostrable que la contabilidad.
Relación con el medio excluido
En las lógicas constructivas y las teorías de conjuntos , que vinculan la existencia de una función entre conjuntos infinitos (no finitos) a cuestiones de efectividad y decidibilidad , la propiedad de subcontabilidad se separa de la contabilidad y, por tanto, no es una noción redundante. El conjunto de indexaciónde números naturales puede postularse para existir, por ejemplo, como un subconjunto a través de un conjunto de axiomas teóricos como el axioma de separación , de modo que
- .
Pero este conjunto puede que aún no sea desmontable, en el sentido de que
no se puede probar sin asumirlo como axioma. Uno puede no contar con eficacia si uno no mapea los números de conteo en el conjunto de indexación , por esta razón.
En matemática clásica
Afirmando todas las leyes de la lógica clásica, la propiedad disyuntiva de de hecho, lo discutido anteriormente es válido para todos los conjuntos. Entonces, por no vacío, las propiedades numerables ( inyecta en ), contable ( posee como su rango), subcontable (un subconjunto de se sobreyecta en ) y tampoco -productivo (una propiedad de contabilización esencialmente definida en términos de subconjuntos de , formalizado a continuación) son todos equivalentes y expresan que un conjunto es finito o infinito numerable .
Afirmaciones no clásicas
No hacer valer la ley del medio excluido
- para toda propuesta ,
entonces también puede ser consistente afirmar la subcontabilidad de conjuntos que clásicamente (es decir, no constructivamente) exceden la cardinalidad de los números naturales. Tenga en cuenta que en un entorno constructivo, una afirmación de contabilidad sobre fuera del conjunto completo , como en , puede ser refutado. Pero la responsabilidad de un conjunto incontable por un conjunto que no es efectivamente separable de puede ser permitido.
Establecer teorías
Argumentos cantorianos sobre subconjuntos de los naturales
En espacios funcionales
Como ejemplo, la teoría CZF tiene Separación limitada , Infinito, es agnóstica hacia la existencia de conjuntos de potencias , pero incluye el axioma que afirma que cualquier espacio funcional está establecido, dado también son conjuntos. En esta teoría, además es coherente afirmar que todo conjunto es subcontable.
Afirmando la sub-contabilidad permitida de todos los conjuntos, es responsable en particular. Para una función en un subconjunto infinito de los números de conteo,, considere el conjunto comprendido como [1]
con el predicado diagonalizante definido como
que también podemos expresar sin las negaciones como
- .
Este conjunto es clásicamente una función en y se puede usar para argumentar que no puede ser una sobreyección. Sin embargo, constructivamente, a menos que las proposiciones en su definición son decidibles de modo que el conjunto realmente definió una asignación funcional, no podemos sacar esta conclusión acerca de la sobrejetividad de .
Para cualquier número distinto de cero , Las funciones en no se puede extender a todos por la misma razón. Tenga en cuenta que cuando se le da un, no se puede decidir necesariamente si , es decir, si el valor de una extensión de función potencial en ya está determinado por . En otras palabras, hay funciones parciales que no se pueden extender a funciones completas..
Sin embargo, incluso en este caso, la existencia de un rechazo total , con dominio , es de hecho contradictorio, ya que la pertenencia a es decidible.
El axioma de subcontabilidad es incompatible con cualquier nuevo axioma que haga contables, incluido LEM.
En clases de poder
Asumiendo es un conjunto, el conjunto violando una posible sobreyección , dada por
dónde
- ,
en el teorema de Cantor sobre conjuntos de potencias existe a través de la separación y de hecho conduce inmediatamente a una contradicción. [2] Esto demuestra que en realidad, no puede ser un conjunto y, por lo tanto, es una clase adecuada.
Las dos situaciones discutidas son diferentes en que una función hace accesibles los datos para todos sus subdominios (subconjuntos del superconjunto). Naturalmente, en CZF, las funciones totales no están en biyección con los subconjuntos de , un concepto más complicado. De hecho, incluso el conjunto de potencias de un singleton, p. Ej., se demuestra que es una clase adecuada en este contexto (es probable que no solo existan los dos valores de verdad y ).
La noción de tamaño
Motivado por lo anterior, el conjunto infinito puede considerarse "más pequeño" que la clase . La suposibilidad no debe confundirse con la definición matemática estándar de relaciones de cardinalidad tal como las define Cantor, definiéndose una cardinalidad menor en términos de inyecciones fuera de y la igualdad de cardinalidades se define en términos de biyecciones. Además, tenga en cuenta que de forma constructiva, un pedido ""como el de las cardinalidades puede ser indecidible. Como se ve en el ejemplo del espacio funcional considerado en la teoría de la computabilidad , no todos los subconjuntos infinitos de necesariamente está en biyección constructiva con , lo que da lugar a una distinción más refinada entre conjuntos incontables en contextos constructivos. El espacio funcional (y también ) en una teoría de conjuntos moderadamente rica no siempre se encuentra ni finita ni en biyección con , por el argumento diagonal de Cantor . Eso es lo que significa ser incontable. Pero el argumento de que la cardinalidad de ese conjunto excedería en cierto sentido a 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.
Modelos
El análisis anterior afecta las propiedades formales de las codificaciones de . Se han construido modelos para esta extensión no clásica de la teoría CZF. [3] Tales axiomas no constructivos pueden verse como principios de elección que, sin embargo, no tienden a aumentar mucho las fortalezas teóricas de prueba de las teorías.
Más ejemplos:
- Hay modelos de IZF en los que todos los conjuntos con relaciones de separación son contables. [4]
- En CZF , como se discutió, de hecho es consistente afirmar el axioma de responsabilidad de que todos los conjuntos son (internamente) contables. La teoría resultante está en contradicción con el axioma del conjunto de poder y con la ley del medio excluido .
- Más fuerte aún, algunos modelos de la teoría de conjuntos de Kripke-Platek validan que todos los conjuntos son incluso contables.
Contable implica que no -productivo
Cualquier conjunto contable es subcontable y cualquier conjunto subcontable no es -productivo: un conjunto se ha dicho - productivo si, siempre que alguno de sus subconjuntos sea el rango de alguna función parcial, siempre queda al menos un elemento que se encuentra fuera de ese rango. Esto puede expresarse como
Un ser conjunto -productivo habla de lo difícil que es generar sus elementos: no se pueden generar usando una sola función. Como tal,-los conjuntos productivos escapan a la sub-contabilidad. Los argumentos diagonales a menudo involucran esta noción, ya sea explícita o implícitamente.
Ver también
Referencias
- ^ John L. Bell " Paradoja y diagonalización de Russel en un contexto constructivo "
- ^ Daniel Méhkeri " Una interpretación computacional simple de la teoría de conjuntos "
- ^ Rathjen, M. " Principios de elección en teorías de conjuntos constructivas y clásicas ", Actas del coloquio de lógica, 2002
- ↑ McCarty, J. " Subcountability under realizability ", Notre Dame Journal of Formal Logic, Vol 27 no 2 de abril de 1986