Rekursive mængder

En mængde kan defineres rekursivt, hvis vi kan angive et startpunkt (basis) og en regel (rekursivt skridt) for hvordan nye elementer kommer med. På den måde kan en uendelig mængde bygges op trin for trin.

 

Eksempel: Tal delelige med 3

Vi definerer mængden \( \large M \) af positive heltal delelige med 3 rekursivt:

 

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

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

 

Første skridt

Basis siger at 3 er med i mængden. Ved at anvende reglen får vi:

 

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

 

Andet skridt

Når vi ved at 6 er med, giver reglen straks et nyt medlem:

 

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

 

Videre skridt

Gentager vi processen, får vi:

 

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

 

Til sidst ser vi at hele mængden bliver

 

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

 

Andre eksempler

På samme måde kan man definere mængden af lige tal ved at starte med 0 og hele tiden lægge 2 til. Eller mængden af ulige tal ved at starte med 1 og lægge 2 til. Rekursive definitioner af mængder bruges også til mere avancerede konstruktioner, som når man bygger træstrukturer eller bestemmer sproglige mønstre i formelle sprog.

 

Opsummering

En rekursiv mængde defineres med et klart basis-element og en regel for at skabe nye elementer. Ved at gentage reglen uendeligt mange gange får man hele mængden. Denne metode gør det muligt at beskrive store eller uendelige mængder med en enkel definition.