A recursive definition of a set defines the elements of a set in terms of the elements already defined for the set.
A recursive definition consists of two parts:
Recall that (transitive) closure creates a new set S (the closure) from an existing set T under an operation o, by giving S all of T's elements plus all entities that can be obtained by applying o to elements already in S, continuing until o produces no elements not already in S or forever, whichever comes first. A recursive definition defines a set that is the (transitive) closure of the set of basis elements under the recursive rules. The resulting set contains
The factorial function n! can be defined by a set of mappings recursively defined by
This recursive definition uses a single basis element, and a single recursive rule.
The Fibonacci sequence f_{0}, f_{1}, f_{2}, … can be defined by
This definition uses two basis elements and a single recursive rule.
Finite binary strings.
In the examples above, we defined a totally ordered, well-ordered set in which the elements corresponded to the non-negative integers, so that we can talk of j! or the kth Fibonacci number as though they were functions of the non-negative integers. This is possible because their definitions used a single recursive rule.
The set {0,1}^{*} of finite binary strings.
This definition uses one basis element and two recursive rules. Consequently, the resulting set is well ordered but not totally ordered — there is no uniquely-appropriate mapping from the non-negative integers to it, as there was for the preceding examples. Instead, this set is partially ordered by the prefix relation (s<t iff s is a prefix of t).
(Recall that the definition of partial order
includes all total orders,
so that every total order is also a partial order,
just like every integer is also a rational number.)
How is the prefix relation related to the recursive rules?
Finite strings over an alphabet.
The set Σ^{*} of finite strings over an alphabet Σ, where Σ is a finite set of symbols.
This definition uses one basis element and |Σ| recursive rules.
Is Σ^{*} totally or only partially ordered? Why? Is any recursively defined set neither totally nor partially ordered?
Well-formed formulae of propositional logic.
The set of well-formed formulae (WFF_{PL}) of propositional logic using ¬, ∧, ∨, ( ), T, F, a, b, … , z.
This definition uses 28 basis elements and four recursive rules.
Is Σ^{*} partially ordered? What is the order relationship?
We can also define functions recursively. Under mathematical induction, we showed how to recursively define some functions on the positive or non-negative integers — the sum of consecutive positive integers up to n, and the sum of consecutive positive odd integers up to n. We can also define functions on recursively-defined sets.
l(w), the length of string w in Σ^{*}.
Basis step: l(ε) ≜ 0.
Inductive step: if l(w)=k for some string w, then for any c∈Σ, l(wc) ≜ k+1.
This inductive step represents the application of the length function for each of the |Σ| recursive rules for Σ^{*}.
The height of a binary tree.
What is the basis set?
What is the inductive step?
A derivation of an element E of a recursively defined set S is a sequence of applications of rules from S's definition, starting from one or more of S's basis elements, and ending with E; or in the opposite direction.
Derivation of 5!, using the recursive definition above (basis set 0!, recursive rule n!⇒n((n-1)!)).
5! ⇒ 5*(4!) ⇒ 5*4*(3!) ⇒ 5*4*3*(2!) ⇒ 5*4*3*2*(1!) ⇒ 5*4*3*2*1*(0!) ⇒ 5*4*3*2*1*1
Since n! uses only a single rule, it is easy to write the derivation as a linear list.
Derivation of the binary string 00101, using the recursive definition above (basis set ε, recursive rules s'⇒s0 and s'⇒s1). Here · represents catenation.
00101 | ⇒ | 0010·1 | rule for 1 |
⇒ | (001·0)·1 | rule for 0 | |
⇒ | ((00·1)·0)·1 | rule for 1 | |
⇒ | (((0·0)·1)·0)·1 | rule for 0 | |
⇒ | ((((0)·0)·1)·0)·1 | basis element 0 |
Although Σ^{*} uses more than one rule, each of them recurses singly (with only a single variable), so it is still easy to write the derivation as a linear list.
Derivation of WFF_{PL} of propositional logic ¬a∧(b∨c), using the recursive definition above (basis set T, F, a, b, … , z;, recursive rules for ¬, ∧, ∨, and parentheses).
From basis elements to the formula:
1) | a_{PL} | basis set |
2) | ¬a_{PL} | rule for ¬ applied to 1) |
3) | b_{PL} | basis set |
4) | c_{PL} | basis set |
5) | b∨c_{PL} | rule for ∨ applied to 3) and 4) |
6) | (b∨c)_{PL} | rule for parens applied to 5) |
7) | ¬a∧(b∨c)_{PL} | rule for ∧ applied to 2) and 6) |
In the opposite direction, from the formula to basis elements:
¬a∧(b∨c) | ⇒ | ¬a ∧ (b∨c) | rule for ∧ |
⇒ | ¬ a ∧ (b∨c) | rule for ¬ | |
⇒ | ¬ a ∧ (b∨c) | basis set | |
⇒ | ¬a ∧ ( b∨c ) | rule for parens | |
⇒ | ¬a ∧ ( b ∨ c ) | rule for ∨ | |
⇒ | ¬a ∧ ( b ∨ c ) | basis set | |
⇒ | ¬a ∧ ( b ∨ c ) | basis set |
WFF_{PL} uses two rules (for ∧ and for ∨) that recurse multiply, with two variables. Derivations using multiply-recursive rules are easy to write in the form of trees. It is perhaps easiest to make them linear by working from basis set elements to the final formula, and listing which previous results are used in each rule application.