Conjunto finito hereditario

Conjuntos finitos cuyos elementos son todos conjuntos finitos hereditarios

En matemáticas y teoría de conjuntos , los conjuntos finitos hereditarios se definen como conjuntos finitos cuyos elementos son todos conjuntos finitos hereditarios. En otras palabras, el conjunto en sí es finito, y todos sus elementos son conjuntos finitos, recursivamente hasta llegar al conjunto vacío .

Definición formal

Una definición recursiva de conjuntos hereditariamente finitos bien fundados es la siguiente:

Caso base : El conjunto vacío es un conjunto hereditariamente finito.

Regla de recursión : Si son hereditariamente finitos, entonces también lo es . ${\displaystyle a_{1},\dots a_{k}}$ ${\displaystyle \{a_{1},\dots a_{k}\}}$

Sólo los conjuntos que pueden construirse mediante un número finito de aplicaciones de estas dos reglas son hereditariamente finitos.

Representación

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

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

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

1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, ...

Discusión

El conjunto es un ejemplo de un conjunto finito hereditario, y también lo es el conjunto vacío , como se ha señalado. Por otra parte, los conjuntos o son ejemplos de conjuntos finitos que no son finitos hereditariamente . Por ejemplo, el primero no puede ser finito hereditariamente ya que contiene al menos un conjunto infinito como elemento, cuando . ${\displaystyle \{\{\},\{\{\{\}\}\}\}}$ ${\displaystyle \{\}}$ ${\displaystyle \{7,{\mathbb {N} },\pi \}}$ ${\displaystyle \{3,\{{\mathbb {N} }\}\}}$ ${\displaystyle {\mathbb {N} }=\{0,1,2,\dots \}}$

La clase de todos los conjuntos finitos hereditarios se denota por , lo que significa que la cardinalidad de cada miembro es menor que . (De manera análoga, la clase de conjuntos contables hereditarios se denota por .) está en correspondencia biyectiva con . También se puede denotar por , que denota la ésima etapa del universo de von Neumann . ^[2] Por lo tanto, aquí es un conjunto contable . ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle H_{\aleph _{1}}}$ ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle V_{\omega }}$ ${\displaystyle \omega }$

Modelos

Codificación de Ackermann

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 que asigna cada conjunto hereditariamente finito a un número natural, dada por la siguiente definición recursiva: ${\displaystyle f\colon H_{\aleph _{0}}\to \omega }$

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

Por ejemplo, el conjunto vacío no contiene miembros y, por lo tanto, se asigna a una suma vacía , es decir, el número cero . Por otro lado, un conjunto con miembros distintos se asigna a . ${\displaystyle \{\}}$ ${\displaystyle a,b,c,\dots }$ ${\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 finitarios en los números naturales. Más precisamente, (donde es la relación inversa de , intercambiando sus dos argumentos) modela la teoría de conjuntos de Zermelo-Fraenkel ZF sin el axioma de infinito . Aquí, cada número natural modela un conjunto, y la relación modela la relación de pertenencia entre conjuntos. ${\displaystyle (\mathbb {N} ,{\text{BIT}}^{\top })}$ ${\displaystyle {\text{BIT}}^{\top }}$ ${\displaystyle {\text{BIT}}}$ ${\displaystyle {\text{BIT}}}$

Modelos gráficos

Se puede ver que la clase está en correspondencia exacta con una clase de árboles enraizados , es decir, 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 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 gráfico, lo que corresponde al hecho de que se identifican ramas iguales (por ejemplo , trivializando la permutación de los dos subgrafos de forma ). Este modelo de 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 expresivos . ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle \{\dots \}}$ ${\displaystyle \{t,t,s\}=\{t,s\}}$ ${\displaystyle t}$

Existen modelos de grafos para ZF y también teorías de conjuntos diferentes de la teoría de conjuntos de Zermelo, como teorías no bien fundamentadas . Dichos modelos tienen una estructura de aristas más intrincada.

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

Axiomatizaciones

Teorías de conjuntos finitos

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

Nótese ahora 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 tiene una axiomatización constructiva que involucra estos axiomas y, por ejemplo, Inducción de conjuntos y Reemplazo . ${\displaystyle H_{\aleph _{0}}}$

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

ZF

${\displaystyle ~V_{4}~}$representado con círculos en lugar de llaves    

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

Si denotamos por el conjunto potencia de , y por el conjunto vacío, entonces se puede obtener fijando para cada entero . Por lo tanto, se puede expresar como ${\displaystyle \wp (S)}$ ${\displaystyle S}$ ${\displaystyle V_{0}}$ ${\displaystyle V_{\omega }}$ ${\displaystyle V_{i+1}=\wp (V_{i})}$ ${\displaystyle i\geq 0}$ ${\displaystyle V_{\omega }}$

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

y todos sus elementos son finitos.

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

De manera equivalente, un conjunto es hereditariamente finito si y sólo si su clausura transitiva es finita.

Véase también

• Teoría de conjuntos constructivos
• Conjunto finito
• Conjunto hereditario
• Conjunto contable hereditario
• Propiedad hereditaria
• Árboles enraizados

Referencias

1. Sloane, N. J. A. (ed.). "Secuencia A004111". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
2. "conjunto finito hereditario". nLab . Enero de 2023 . Consultado el 28 de enero de 2023 . El conjunto de todos los conjuntos finitos hereditarios (bien fundados) (que es infinito, y no finito hereditario en sí mismo) se escribe para mostrar su lugar en la jerarquía de von Neumann de conjuntos puros. ${\displaystyle V_{\omega }}$
3. Ackermann, Wilhelm (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre". Annalen Matemáticas . 114 : 305–315. doi :10.1007/bf01594179. S2CID  120576556 . Consultado el 9 de enero de 2012 .
4. Kirby, Laurence (2009). "Teoría de conjuntos finitarios". Notre Dame Journal of Formal Logic . 50 (3): 227–244. doi : 10.1215/00294527-2009-009 .
5. Omodeo, Eugenio G.; Policriti, Alberto; Tomescu, Alexandru I. (2017). "3.3: La codificación de Ackermann de conjuntos finitos hereditarios". Sobre conjuntos y grafos: perspectivas sobre lógica y combinatoria . Springer. págs. 70–71. doi :10.1007/978-3-319-54981-1. ISBN 978-3-319-54980-4.Señor 3558535  .