Cheat Sheet: Recursive Definitions

Recursive definitions define sets by specifying base cases and rules for constructing new elements from existing ones, offering a powerful, albeit sometimes complex, method for describing mathematical and computational structures.

Core Principles

A recursive definition has three parts: 1) specify basic objects, 2) provide rules to construct more objects from known ones, and 3) declare that only constructed objects are allowed.
Recursive definitions are essential in computer theory for proving the possibility or impossibility of tasks, even when the most efficient algorithms are unknown.
The self-referential nature of recursive definitions allows for elegant proofs of properties, such as the sum of two even numbers being even.

Action Steps

To define a set recursively, first identify the simplest elements (base cases).
Next, formulate rules that generate new elements from existing ones within the set.
Finally, explicitly state that no other elements are part of the set.

Key Terms

Recursive Definition: A method of defining sets where basic elements are specified, and rules are given to construct new elements from existing ones, with the declaration that only constructed elements are included.
Base Case: The initial, simplest objects specified in a recursive definition that form the foundation for constructing other elements.
Recursive Step: The rules provided in a recursive definition that allow for the construction of new elements from previously defined elements.

Pro Tips

While non-recursive definitions might be easier to understand initially, recursive definitions can simplify proofs of properties about the set.
The choice between recursive and non-recursive definitions depends on the ease of understanding and the types of theorems one wishes to prove.

Pitfalls to Avoid

Using recursive definitions can lead to lengthier processes for proving membership, as seen in proving 14 is in EVEN.
Misinterpreting the recursive structure can lead to incorrect conclusions about the set's properties.

Real World Examples

Defining the set of positive even integers.: Rule 1: 2 is in EVEN. Rule 2: If x is in EVEN, then x + 2 is in EVEN. Rule 3: Only elements produced by these rules are in EVEN.
Defining the set of polynomials in one variable x.: Rule 1: Any number is in POLYNOMIAL. Rule 2: x is in POLYNOMIAL. Rule 3: If p and q are in POLYNOMIAL, then p + q and pq are in POLYNOMIAL. Rule 4: Only elements produced by these rules are in POLYNOMIAL.
Defining the set of descendants of Henry VIII.: Rule 1: The children of Henry VIII are DESCENDANTS. Rule 2: If x is a DESCENDANT, then x's children are DESCENDANTS.