Recursive sets

A set can be defined recursively if we can specify a starting point (base) and a rule (recursive step) for how new elements are included. In this way, an infinite set can be built step by step.

 

Example: Numbers divisible by 3

We define the set \( \large M \) of positive integers divisible by 3 recursively:

 

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

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

 

First step

The base says that 3 is in the set. By applying the rule we get:

 

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

 

Second step

Knowing that 6 is in the set immediately gives a new member:

 

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

 

Further steps

Repeating the process, we obtain:

 

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

 

In the end, we see that the whole set is

 

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

 

Other examples

In the same way, one can define the set of even numbers by starting with 0 and repeatedly adding 2. Or the set of odd numbers by starting with 1 and adding 2. Recursive definitions of sets are also used for more advanced constructions, such as when building tree structures or determining linguistic patterns in formal languages.

 

Summary

A recursive set is defined with a clear base element and a rule for creating new elements. By repeating the rule infinitely many times, one obtains the whole set. This method makes it possible to describe large or infinite sets with a simple definition.