Thomas A. Alspaugh
Recursive Definitions and Derivations

Recursive definitions of sets

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:

  1. the basis, in which one or more basis elements of the set are listed, and
  2. the recursive rules, in which one or more rules are given that define additional elements of the set in terms of elements already defined for the set. 

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

  1. every entity that can be derived from the basis elements by a finite (possibly 0-length) chain of applications of the recursive rules, and
  2. no other elements. 

The factorial function n! can be defined by a set of mappings recursively defined by

Basis set
0! ≜ 1. 
Recursive rule
n! ≜ n((n-1)!)

This recursive definition uses a single basis element, and a single recursive rule.

The Fibonacci sequence f0, f1, f2, … can be defined by

Basis set
f0 ≜ 0
f1 ≜ 1
Recursive rule
If n≥2, then fn ≜ fn-2 + fn-1

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. 

Basis set
The empty string, represented by ε
Recursive rules
If s∈{01}*, then
  1. s0∈{01}* (s0 is the string s with 0 appended to it), and
  2. s1∈{01}* (s1 is the string s with 1 appended to it).

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. 

Basis set
The empty string, represented by ε
Recursive rules
If s∈Σ* and c∈Σ, then sc∈Σ* (sc is the string s with c appended to it).

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 (WFFPL) of propositional logic using ¬, ∧, ∨, ( ), T, F, a, b, … , z.

Basis set
{ T, F, a, b, … , z }
Recursive rules
  1. If φ is in WFFPL then ¬φ is in WFFPL.
  2. If φ1 and φ2 are in WFFPL then φ1∧φ2 is in WFFPL.
  3. If φ1 and φ2 are in WFFPL then φ1∨φ2 is in WFFPL.
  4. If φ is in WFFPL then (φ) is in WFFPL.

This definition uses 28 basis elements and four recursive rules. 

Is Σ* partially ordered?  What is the order relationship? 

Recursive definitions of functions

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?

Derivations

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 WFFPL 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) aPL basis set
2) ¬aPL rule for ¬ applied to 1)
3) bPL basis set
4) cPL basis set
5) b∨cPL 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)
parse tree

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

WFFPL 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. 

flip bgunflip