Conjunto inmune

Un conjunto inmune es un conjunto infinito de objetos constructivos (por ejemplo, números naturales ), cualquier subconjunto enumerable de los cuales es finito. En matemáticas constructivas, los conjuntos inmunes a veces se utilizan para construir ejemplos de objetos con propiedades "patológicas" (desde el punto de vista de las matemáticas tradicionales de teoría de conjuntos ).

Ejemplo

El conjunto inmune más simple de números naturales se puede construir de la siguiente manera. Fijamos alguna numeración de todas las funciones parcialmente recursivas de una variable, y consideramos el predicado de dos lugares correspondiente a esta numeración , expresando la condición "una función parcialmente recursiva con un número es aplicable a un número natural ". En este caso, el complemento del conjunto ${\ estilo de visualización T (x, \; y)}$ $X$ $y$ $I\rightleftharpoons \mathbb {N} \setminus C$

C\rightleftharpoons \{x\in \mathbb {N} \mid (\existe y)\;(2y<x)\land (T(y,\;x)\land ((\forall z)\ ;T(y,\;z)\supset ((z\leqslant 2y)\lor (z\geqslant x))))\}

es un conjunto inmune. De hecho, para cualquier número natural, el conjunto contiene como máximo números menores que el número y, por lo tanto, el conjunto es infinito. Por otro lado, cualquier subconjunto enumerable de un conjunto es el dominio de alguna función parcialmente recursiva de una variable. Esta función corresponde a un número determinado con la numeración fijada por nosotros, lo que, por la naturaleza de la construcción del conjunto , significa que el conjunto no puede contener números mayores que . Por lo tanto, mucho, por supuesto. $norte$ $C$ $norte$ $2n$ $yo$ $METRO$ $yo$ $norte$ $C$ $METRO$ $2n$ $METRO$

Véase también

conjunto aritmético

Literatura

Rogers H. Teoría de funciones recursivas y computabilidad efectiva . — M.: Mir, 1972.