Conjunto finito hereditariamente

En matemáticas y teoría de conjuntos, los conjuntos finitos hereditariamente 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 el conjunto vacío.

Definición formal

editar

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 a1, ..., ak son hereditariamente finitos, entonces también lo es {a1, ..., ak}.

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

editar

Un símbolo de la clase es  , representando la cardinalidad de cada uno de sus miembros menor que   . Si   es un conjunto y los enunciados sobre cardinalidad dependen de la teoría en contexto.

Biyección de Ackermann

editar

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.

Por ejemplo:

 

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

editar

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 Neumann ordinal "1"),
  •  ,
  •   y luego también   (es decir Neumann ordinal "2"),
  •  ,   tanto 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

editar

Teorías de conjuntos finitos

editar

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 en   y 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 de   con axiomas dados por Extensionalidad, Conjunto Vacío y Adjunción.

En efecto,   tiene axiomatizaciones constructivas que involucran estos axiomas y, por ejemplo, Establecer inducción y Reemplazo.

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 de 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.

 
  representado con círculos en lugar de llaves     

Los conjuntos finitos hereditariamente son una subclase del universo de Von Neumann. Aquí, todos los conjuntos finitos hereditariamente bien fundados se denotan Vω. Tenga en cuenta que este 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 = ℘ (V0), V 2 = ℘ (V1) ,..., Vk = ℘ (Vk−1), ... y así sucesivamente.

Por tanto, Vω se puede expresar como  .

Vemos, de nuevo, que solo hay un número contable de conjuntos finitos hereditariamente: Vn es finito para cualquier n finito. Su cardinalidad es n−1 2, ver tetración. La unión de innumerables conjuntos finitos es contable.

De manera equivalente, un conjunto es hereditariamente finito si y solo si su cierre transitivo es finito.

Modelos gráficos

editar

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 superior   y cada borde conduce a un elemento (otro conjunto similar) que puede actuar como un 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 (por ejemplo,  , 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. Dichos modelos tienen una estructura de borde más intrincada.

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

Véase también

editar

Referencias

editar
  1. «A004111 - OEIS». oeis.org. Consultado el 7 de febrero de 2021. 
  • Ackermann, Wilhelm (1937), «Die Widerspruchsfreiheit der allgemeinen Mengenlehre», Mathematische Annalen 114 (1): 305-315, doi:10.1007/BF01594179 .