4. Describing sets by recursion

Describing sets by recursion

Recursive set description

A recursive description of a set $S$ consists of three steps: ?

• Basis step: Specify one or more elements of $S$.
• Recursive step: Give one or more rules to construct new elements of $S$ from existing elements of $S$.
• Exlusion rule: State that $S$ consists only of the elements that are specified by the basis step, or generated by successive applications of the recursive step. Nothing else is in the $S$. (This step is usually assumed rather than explicitly stated)

Link to original

title: Example 1
The set $\mathbb N$ of natural numbers can be defined recursively:
- **Basis step**: $0 \in \mathbb N$
- **Recursive step**: If $n \in \mathbb N$ then $n + 1 \in \mathbb N$
 
Eventually, by this rule, we will find each and every number in the set.

title: Example 2
The set $\text{Odd}$ of odd numbers can be defined recursively:
- **Basis step**: $813 \in \mathbb N$
- **Recursive step**: If $n \in \text{Odd}$ then $n + 2 \in \text{Odd}$ and $n - 2 \in \text{Odd}$

title: Example 3
The set $A = \{ 3k + 1 | k \in \mathbb N \}$ can be defined recursively:
- **Basis step**: $1 \in A$
- **Recursive step**: If $x \in A$ then $x + 3 \in A$
 
This is processed as so:
- $k = 0 \rightarrow 1 \in A$
- $k = 1 \rightarrow 4 \in A$
- $k = 2 \rightarrow 7 \in A$

title: Example 4
The set $F$ of all formulas of propositional logic can be defined recursively:
- **Basis step**: every propositional variable is in $F$
- **Recursive step**: If $p \in F$ and $q \in F$, then $(\neg p) \in F$, $(p \land q) \in F$, $(p \lor q) \in F$, $(p \rightarrow q) \in F$ and $(p \iff q) \in F$.