Conjunto hereditariamente finito

Conjuntos finitos cuyos elementos son todos conjuntos hereditariamente finitos.

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

Definicion 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 recursividad : si son hereditariamente finitos, entonces también lo son . ${\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 corchetes necesarios para representar los conjuntos:

• ${\displaystyle \{\}}$(es decir , el ordinal de Neumann "0") ${\displaystyle \emptyset }$
• ${\displaystyle \{\{\}\}}$(es decir , o , 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, por ejemplo . Hay seis conjuntos de este tipo. ${\displaystyle 6}$ ${\displaystyle \{\{\{\{\{\{\}\}\}\}\}\}}$
• ... conjuntos representados con pares de corchetes, por ejemplo . 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 forma, 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 hereditariamente finito y también lo es el conjunto vacío , como se señaló. Por otro lado, los conjuntos o son ejemplos de conjuntos finitos que no son hereditariamente finitos. Por ejemplo, el primero no puede ser hereditariamente finito 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 hereditariamente finitos se denota por , lo que significa que la cardinalidad de cada miembro es menor que . (De manera análoga, la clase de conjuntos contables hereditariamente se denota por .) está en correspondencia biyectiva con . También se puede denotar por , que denota la octava etapa del universo de von Neumann . ^[2] Así que aquí hay 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 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, dado 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 está 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 del BIT .

La codificación de Ackermann se puede utilizar para construir un modelo de teoría de conjuntos finitos en números naturales. Más precisamente, (dónde está 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 soporte del nivel superior y cada borde conduce a un elemento (otro conjunto de este tipo) que puede actuar como vértice raíz por derecho propio. No existe ningún automorfismo de este gráfico, correspondiente al hecho de que se identifican ramas iguales (p. ej. , trivializando la permutación de los dos subgrafos de forma ). Este modelo gráfico permite una implementación de ZF sin infinito como tipos de datos y, por 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 gráficos para ZF y también teorías de conjuntos diferentes a la teoría de conjuntos de Zermelo, como las teorías no bien fundadas . Estos modelos tienen una estructura de bordes más compleja.

En teoría de grafos , el gráfico cuyos vértices corresponden a conjuntos hereditariamente finitos y aristas corresponden a la pertenencia a conjuntos es el gráfico de Rado o gráfico aleatorio.

Axiomatizaciones

Teorías de conjuntos finitos

En los enfoques axiomáticos comunes de la teoría de conjuntos, 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 tanto, también lo es la clase de conjuntos que representan los números naturales. En otras palabras, incluye cada elemento en el modelo estándar de números naturales y una teoría de conjuntos que expresa debe contenerlos todos. ${\displaystyle \{\}}$ ${\displaystyle 0}$ ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle H_{\aleph _{0}}}$

Ahora tenga en cuenta que la aritmética de Robinson ya se puede interpretar en ST , la muy pequeña subteoría de la teoría de conjuntos Z de Zermelo ^, con sus axiomas dados por Extensionalidad , Conjunto Vacío y Adjunción . tiene una axiomatización constructiva que involucra estos axiomas y, por ejemplo, Inducción y reemplazo de conjuntos . ${\displaystyle H_{\aleph _{0}}}$

Al caracterizar axiomáticamente la teoría de conjuntos hereditariamente finitos, se puede agregar la negación del axioma del infinito, demostrando así que el axioma del infinito no es consecuencia de los demás axiomas de ZF.

ZF

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

Los conjuntos hereditariamente finitos son una subclase del universo de Von Neumann . Aquí se denota la clase de todos los conjuntos hereditariamente finitos bien fundados . Tenga en cuenta 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 configurando para cada número entero . Así, 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 muestra, nuevamente, que sólo hay un número contable de conjuntos hereditariamente finitos: es finito para cualquier finito , su cardinalidad está en la notación de flecha hacia arriba de Knuth (una torre de potencias de dos), y la unión de un número 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 cierre transitivo es finito.

Ver también

• Teoría de conjuntos constructiva
• Conjunto finito
• conjunto hereditario
• Conjunto contable hereditariamente
• propiedad hereditaria
• Árboles enraizados

Referencias

1. Sloane, Nueva Jersey (ed.). "Secuencia A004111". La enciclopedia en línea de secuencias enteras . Fundación OEIS.
2. "conjunto hereditariamente finito". nLaboratorio . nLab. Enero de 2023 . Consultado el 28 de enero de 2023 . El conjunto de todos los conjuntos hereditariamente finitos (bien fundados) (que es infinito y no hereditariamente finito en sí mismo) está escrito para mostrar su lugar en la jerarquía de conjuntos puros de von Neumann. ${\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 finitos". Revista de lógica formal de Notre Dame . 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 hereditariamente finitos". Sobre conjuntos y gráficos: perspectivas sobre lógica y combinatoria . Saltador. págs. 70–71. doi :10.1007/978-3-319-54981-1. ISBN 978-3-319-54980-4. SEÑOR  3558535.