inductive definition

An inductive definition of mathematical objects consists of a base case, a constructor case, and an exhaustion clause (usually omitted for brevity).

For example, to define a string:

• Base case (S1): The empty string $\lambda$ is a string in ${\Sigma }^{\ast }$.
• Constructor case (S2): If $s$ is a string in ${\Sigma }^{\ast }$ and $a$ is a symbol in $\Sigma$, then $⟨a,s⟩$ is a member of ${\Sigma }^{\ast }$.
• Exhaustion clause (S3): Nothing else is in ${\Sigma }^{\ast }$ except as follows from the base and constructor cases.

Notice how the exhaustion clause is trivial—this means that we can usually omit it from the definition.

From the above definition we can construct a string by building on the empty string, so the string 110 is $⟨1,⟨1,⟨0,\lambda ⟩⟩⟩$.