En matemáticas y teoría de conjuntos , los conjuntos finitos hereditariamente se definen como conjuntos finitos cuyos elementos son todos conjuntos finitos hereditariamente. En otras palabras, el conjunto en sí es finito y todos sus elementos son conjuntos finitos, recursivamente hasta el conjunto vacío.
Definicion formal
Una definición recursiva de conjuntos finitos hereditariamente fundamentados es la siguiente:
- Caso base : el conjunto vacío es un conjunto finito hereditariamente.
- Regla de recursividad : si a 1 , ..., a k son hereditariamente finitos, entonces también lo es { a 1 , ..., a k }.
El conjunto es un ejemplo de un conjunto tan finito hereditariamente y también lo es el conjunto vacío . 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.
Discusión
Un símbolo de la clase es , representando que la cardinalidad de cada uno de sus miembros es menor que . Ya sea es un conjunto y los enunciados sobre cardinalidad dependen de la teoría en contexto.
Biyección de Ackermann
La clase es contable . Ackermann (1937) dio la siguiente biyección natural f de los números naturales a la, conocido como codificación Ackermann . Se define de forma recursiva por
- si a , b , ... son distintos.
P.ej
Tenemos f ( m ) ∈ f ( n ) si y solo si el m- ésimo dígito binario de n (contando desde la derecha comenzando en 0) es 1.
Representación
Esta clase de conjuntos se clasifica naturalmente por el número de pares de corchetes necesarios para representar los conjuntos:
- (es decir , es decir, el ordinal de Neumann "0"),
- (es decir , es decir, ordinal de Neumann "1"),
- ,
- y luego también (es decir, ordinal "2" de Neumann),
- , así como ,
- ... conjunto representado con pares de soportes,
- ... conjunto representado con pares de soportes, p. ej. o (es decir, Neumann ordinal "3"),
- ... etc.
De esta forma, el número de conjuntos con pares de corchetes es [1]
Axiomatizaciones
Teorías de conjuntos finitos
El conjunto también representa el primer número ordinal de von Neumann , denotado. Y, de hecho, todos los ordinales finitos de von Neumann están eny así la clase de conjuntos que representan los números naturales, es decir, incluye cada elemento en el modelo estándar de números naturales . La aritmética de Robinson ya se puede interpretar en ST , la subteoría muy pequeña decon axiomas dados por Extensionalidad , Conjunto Vacío y Adjunción .
En efecto, tiene axiomatizaciones constructivas que involucran estos axiomas y, por ejemplo , inducción y reemplazo de conjuntos .
Entonces, sus modelos también cumplen los axiomas que consisten en los axiomas de la teoría de conjuntos de Zermelo-Fraenkel sin el axioma del infinito . En este contexto, se puede agregar la negación del axioma del infinito, probando así que el axioma del infinito no es una consecuencia de los otros axiomas de la teoría de conjuntos.
ZF
Los conjuntos finitos hereditariamente son una subclase del universo de Von Neumann . Aquí, la clase de todos los conjuntos finitos hereditariamente bien fundados se denota V ω . Tenga en cuenta que esto también es un conjunto en este contexto.
Si denotamos por ℘ ( S ) el conjunto de potencias de S , y por V 0 el conjunto vacío, entonces V ω se puede obtener estableciendo V 1 = ℘ ( V 0 ), V 2 = ℘ ( V 1 ), .. ., V k = ℘ ( V k −1 ), ... y así sucesivamente.
Por tanto, V ω se puede expresar como.
Vemos, de nuevo, que sólo hay muchos conjuntos finitos hereditariamente contables : V n es finito para cualquier n finito , su cardinalidad es n −1 2 (ver tetración ), y la unión de muchos conjuntos finitos numerables es contable.
De manera equivalente, un conjunto es hereditariamente finito si y solo si su cierre transitivo es finito.
Modelos gráficos
La clase se puede ver que 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 de la raíz corresponde al paréntesis de nivel superiory cada borde conduce a un elemento (otro conjunto similar) que puede actuar como un vértice raíz por derecho propio. No existe automorfismo de este gráfico, lo que corresponde 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 lo tanto, una interpretación de la teoría de conjuntos en las teorías de tipos expresivos .
Existen modelos de gráficos para ZF y también teorías de conjuntos diferentes de la teoría de conjuntos de Zermelo, como teorías no bien fundamentadas . Tales modelos tienen una estructura de borde más intrincada.
En la teoría de grafos , el grafo cuyos vértices corresponden a conjuntos finitos hereditariamente y los bordes corresponden a la pertenencia al conjunto es el grafo de Rado o grafo aleatorio.
Ver también
Referencias
- Ackermann, Wilhelm (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre", Mathematische Annalen , 114 (1): 305–315, doi : 10.1007 / BF01594179