Ensembles récursifs

Un ensemble peut être défini de manière récursive si l’on peut indiquer un point de départ (base) et une règle (étape récursive) pour savoir comment de nouveaux éléments sont ajoutés. De cette façon, un ensemble infini peut être construit pas à pas.

 

Exemple : Nombres divisibles par 3

Nous définissons l’ensemble \( \large M \) des entiers positifs divisibles par 3 de manière récursive :

 

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

$$ \large x \in M \;\Rightarrow\; x + 3 \in M \quad \text{(étape récursive)} $$

 

Première étape

La base dit que 3 appartient à l’ensemble. En appliquant la règle, nous obtenons :

 

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

 

Deuxième étape

En sachant que 6 appartient à l’ensemble, la règle donne immédiatement un nouveau membre :

 

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

 

Étapes suivantes

En répétant le processus, on obtient :

 

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

 

Finalement, on voit que l’ensemble complet est

 

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

 

Autres exemples

De la même manière, on peut définir l’ensemble des nombres pairs en commençant par 0 et en ajoutant toujours 2. Ou l’ensemble des nombres impairs en commençant par 1 et en ajoutant 2. Les définitions récursives d’ensembles sont aussi utilisées pour des constructions plus avancées, comme lorsqu’on construit des structures arborescentes ou qu’on détermine des motifs linguistiques dans les langages formels.

 

Résumé

Un ensemble récursif est défini avec un élément de base clair et une règle pour créer de nouveaux éléments. En répétant la règle une infinité de fois, on obtient l’ensemble complet. Cette méthode permet de décrire de grands ensembles ou des ensembles infinis avec une définition simple.