Construction Techniques

Inductively Defined Sets

Steps needed to define a set inductively
1. There is a starting element
2. There is a construction operation to build new elements from existing elements
3. There is a statement that no other elements are in the set.

Basis: Specify one or more elements of S

Induction: Give one or more rules to construct new elements of S from existing elements of S

Closure: State that S consists exactly of the elements obtained by the basis and induction steps. (usually assumed, not states explicitly)

Note: The basis elements and the induction rules are called constructors.

Example. Find an inductive definition for S = {3, 16, 29, 42, …}.

Solution:  Basis: 3 Î S.

Induction: If x Î S then x + 13 Î S.

Recursive Functions and Procedures

Constructing a Recursively Defined Procedure [or function P(x) =  f(x)]

If S is an inductively defined set, we can construct a procedure P to process the elements of S as follows:

1. For each basis element x ∈ S, specify a set of actions for P(x).

2. Give rules that, for any inductively defined element x ∈ S, will define the actions of P(x) in terms of previously defined actions of P.

Example f(n)=1+3+…+(2n+1) , [Adding odd numbers]

recursive definition of f:

f (0) = 1,

f (n) = f (n — 1) + 2n + 1 for n > 0.

If-then-else

f (n) = if n = 0 then 1 else f (n - 1) + 2n + 1.

Pattern-matching

f(n + 1) = f(n) + 2n + 3.

Recursive definitions vs. Inductively defined sets