Conjuntos recursivos

Un conjunto puede definirse recursivamente si podemos indicar un punto de inicio (base) y una regla (paso recursivo) para cómo se añaden nuevos elementos. De esta manera, un conjunto infinito puede construirse paso a paso.

 

Ejemplo: Números divisibles por 3

Definimos el conjunto \( \large M \) de enteros positivos divisibles por 3 recursivamente:

 

$$ \large 3 \in M \quad \text{(base)} $$

$$ \large x \in M \;\Rightarrow\; x + 3 \in M \quad \text{(paso recursivo)} $$

 

Primer paso

La base dice que 3 pertenece al conjunto. Al aplicar la regla obtenemos:

 

$$ \large 3 \in M \;\Rightarrow\; 3 + 3 = 6 \in M $$

 

Segundo paso

Saber que 6 pertenece al conjunto da inmediatamente un nuevo miembro:

 

$$ \large 6 \in M \;\Rightarrow\; 6 + 3 = 9 \in M $$

 

Pasos siguientes

Repitiendo el proceso, obtenemos:

 

$$ \large 9 \Rightarrow 12, \quad 12 \Rightarrow 15, \quad 15 \Rightarrow 18, \ldots $$

 

Al final vemos que todo el conjunto es

 

$$ \large M = \{3,6,9,12,15,\ldots\} $$

 

Otros ejemplos

De la misma manera, se puede definir el conjunto de los números pares empezando con 0 y sumando siempre 2. O el conjunto de los impares empezando con 1 y sumando 2. Las definiciones recursivas de conjuntos también se usan en construcciones más avanzadas, como al construir estructuras en árbol o determinar patrones lingüísticos en lenguajes formales.

 

Resumen

Un conjunto recursivo se define con un elemento base claro y una regla para crear nuevos elementos. Repitiendo la regla infinitas veces se obtiene todo el conjunto. Este método permite describir conjuntos grandes o infinitos con una definición sencilla.