Recursively Define Sets

To recursively define a set,
Basis Step: An initial collection of elements is specified.
Recursive Step: Rules for forming new elements in the set from those already known to be in the set are provided.

Example

Basis Step: 0 is in N. Recursive Step: If n is in N, then n + 1 is also in N.

Consider the set M of all even-length mirror-image strings on {a,b}. An even-length mirrorimage string is a string that can be divided into two halves, with the right half a mirror-image reversal of the left half (a “palindrome”). Examples: abba, babbab, aaaa. 

Basis Step:
1. aa ∈ M & bb ∈ M

Recursion Step:
2. (∀x)(x ∈ M → (axa ∈ M & bxb ∈ M))

An obligatory restriction that is often omitted:
3. Nothing is in M except by virtue of rules 1 and 2.

To prove by induction that a statement P(x) is true for all the elements x of a recursively defined set S, proceed as follows:

Basis Step: Prove that P(x) is true for all the elements x in the basis of S.
Induction Step: Prove that for any element x of S if P(x) is true, then P(y) is true for any element y obtained from x by the induction step of the recursive definition of S.

In the Induction, we try to prove that if a parent has the property then all of its children also have that property. In the process we need the relationship between the parent and the children. That relationship is found in the Inductive Clause of the recursive definition of the set in question.
As a first step for general induction proof, it is often a good idea to express y in terms of x so that P(x) can be used.