Conjunto hereditariamente finito

Esta clase de conjuntos se clasifica naturalmente según el número de pares de corchetes necesarios para representar los conjuntos:

• ${\displaystyle \{\}}$(es decir${\displaystyle \emptyset }$, el ordinal de Neumann "0")
• ${\displaystyle \{\{\}\}}$(es decir${\displaystyle \{\emptyset \}}$o${\displaystyle \{0\}}$, el ordinal de Neumann "1")
• ${\displaystyle \{\{\{\}\}\}}$
• ${\displaystyle \{\{\{\{\}\}\}\}}$y luego también${\displaystyle \{\{\},\{\{\}\}\}}$(es decir${\displaystyle \{0,1\}}$, el ordinal de Neumann "2"),
• ${\displaystyle \{\{\{\{\{\}\}\}\}\}}$,${\displaystyle \{\{\{\},\{\{\}\}\}\}}$así como${\displaystyle \{\{\},\{\{\{\}\}\}\}}$,
• ... conjuntos representados con${\displaystyle 6}$pares de corchetes, por ejemplo${\displaystyle \{\{\{\{\{\{\}\}\}\}\}\}}$Hay seis conjuntos de este tipo.
• ... conjuntos representados con${\displaystyle 7}$pares de corchetes, por ejemplo${\displaystyle \{\{\{\{\{\{\{\}\}\}\}\}\}\}}$Hay doce conjuntos de este tipo.
• ... conjuntos representados con${\displaystyle 8}$pares de corchetes, por ejemplo${\displaystyle \{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}}$o${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}}$(es decir${\displaystyle \{0,1,2\}}$, el ordinal de Neumann "3")
• ... etc.

De esta manera, el número de conjuntos con${\displaystyle n}$Los pares de corchetes son ^{[ 1 ]}

En 1937, Wilhelm Ackermann introdujo una codificación de conjuntos hereditariamente finitos como números naturales. ^{[ 3 ] [ 4 ] [ 5 ]} Se define mediante una función${\displaystyle f\colon H_{\aleph _{0}}\to \omega }$que asigna a cada conjunto hereditariamente finito un número natural, dado por la siguiente definición recursiva:

${\displaystyle \displaystyle f(a)=\sum _{b\in a}2^{f(b)}}$

Por ejemplo, el conjunto vacío${\displaystyle \{\}}$no contiene miembros y, por lo tanto, se asigna a una suma vacía , es decir, al número cero . Por otro lado, un conjunto con miembros distintos${\displaystyle a,b,c,\dots }$está asignado a${\displaystyle 2^{f(a)}+2^{f(b)}+2^{f(c)}+\ldots }$.

La inversa viene dada por

${\displaystyle \displaystyle f^{-1}\colon \omega \to H_{\aleph _{0}}}$

${\displaystyle \displaystyle f^{-1}(i)=\{f^{-1}(j)\mid {\text{BIT}}(i,j)=1\}}$

donde BIT denota el predicado BIT .

La codificación de Ackermann se puede utilizar para construir un modelo de teoría de conjuntos finitos en los números naturales. Más precisamente,${\displaystyle (\mathbb {N} ,{\text{BIT}}^{\top })}$(dónde${\displaystyle {\text{BIT}}^{\top }}$es la relación inversa de${\displaystyle {\text{BIT}}}$(intercambiando sus dos argumentos) modela la teoría de conjuntos de Zermelo-Fraenkel ZF sin el axioma del infinito . Aquí, cada número natural modela un conjunto, y el${\displaystyle {\text{BIT}}}$Los modelos relacionales representan la relación de pertenencia entre conjuntos.

La clase${\displaystyle H_{\aleph _{0}}}$se puede observar que está en correspondencia exacta con una clase de árboles enraizados , concretamente aquellos sin simetrías no triviales (es decir, el único automorfismo es la identidad): El vértice raíz corresponde al corchete de nivel superior${\displaystyle \{\dots \}}$y cada arista conduce a un elemento (otro conjunto de este tipo) que puede actuar como un vértice raíz por derecho propio. No existe ningún automorfismo de este grafo, lo que corresponde al hecho de que se identifican ramas iguales (por ejemplo${\displaystyle \{t,t,s\}=\{t,s\}}$, trivializando la permutación de los dos subgrafos de forma${\displaystyle t}$). Este modelo gráfico permite una implementación de ZF sin infinito como tipos de datos y, por lo tanto, una interpretación de la teoría de conjuntos en teorías de tipos expresivas .

Existen modelos gráficos para ZF y también teorías de conjuntos distintas de la teoría de conjuntos de Zermelo, como las teorías no bien fundadas . Dichos modelos presentan una estructura de aristas más compleja.

En teoría de grafos , el grafo cuyos vértices corresponden a conjuntos hereditariamente finitos y cuyas aristas corresponden a la pertenencia a un conjunto es el grafo de Rado o grafo aleatorio.

En los enfoques comunes de la teoría axiomática de conjuntos, el conjunto vacío${\displaystyle \{\}}$también representa el primer número ordinal de von Neumann , denotado${\displaystyle 0}$. Todos los ordinales de von Neumann finitos son, en efecto, hereditariamente finitos y, por lo tanto, también lo es cada conjunto de la clase de conjuntos que representan los números naturales. En otras palabras,${\displaystyle H_{\aleph _{0}}}$incluye cada elemento en el modelo estándar de números naturales y por lo tanto una teoría de conjuntos que expresa${\displaystyle H_{\aleph _{0}}}$necesariamente deben contenerlos también.

Ahora bien, observe que la aritmética de Robinson ya puede interpretarse en ST , la subteoría muy pequeña de la teoría de conjuntos de Zermelo Z ⁻ con sus axiomas dados por Extensionalidad , Conjunto Vacío y Adjunción . Todo ello${\displaystyle H_{\aleph _{0}}}$tiene una axiomatización constructiva que involucra estos axiomas y, por ejemplo, la inducción de conjuntos y el reemplazo .

Al caracterizar axiomáticamente la teoría de conjuntos hereditariamente finitos, se puede agregar la negación del axioma de infinito . Como la teoría valida los otros axiomas de${\displaystyle {\mathsf {ZF}}}$, esto establece que el axioma del infinito no es una consecuencia de estos otros${\displaystyle {\mathsf {ZF}}}$axiomas.

Los conjuntos hereditariamente finitos son una subclase del universo de Von Neumann . Aquí, la clase de todos los conjuntos hereditariamente finitos bien fundados se denota${\displaystyle V_{\omega }}$. Tenga en cuenta que esto también es un conjunto en este contexto.

Si denotamos por${\displaystyle \wp (S)}$el conjunto de poderes de${\displaystyle S}$y por${\displaystyle V_{0}}$el conjunto vacío, entonces${\displaystyle V_{\omega }}$se puede obtener configurando${\displaystyle V_{i+1}=\wp (V_{i})}$para cada entero${\displaystyle i\geq 0}$. De este modo,${\displaystyle V_{\omega }}$puede expresarse como

${\displaystyle \displaystyle V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}}$

y todos sus elementos son finitos.

Esta formulación muestra, una vez más, que solo existen una cantidad numerable de conjuntos hereditariamente finitos:${\displaystyle V_{n}}$es finito para cualquier finito${\displaystyle n}$, su cardinalidad es${\displaystyle 2\uparrow \uparrow (n-1)}$en la notación de flecha hacia arriba de Knuth (una torre de${\displaystyle n-1}$potencias de dos), y la unión de una cantidad numerable de conjuntos finitos es numerable.

De forma equivalente, un conjunto es hereditariamente finito si y solo si su clausura transitiva es finita.