# Inductively defined set

An inductively defined set is a set where the elements are constructed by a finite number of applications of a given set of rules for creating more complicated objects from simpler ones.

For example, the set of natural numbers is the set of elements defined inductively by the following rules:

• Rule 1: (We think of Z as standing for "zero")
• Rule 2: If then (S stands for "successor"; you can think of [/itex]S~n[/itex] it as representing "1 + n", although we will define + in terms of S instead of the other way around).

Thus the elements of are . You can then define as , as , and so on.

## Contents

### BNF Notation

Backus-Naur form (or BNF) is a convenient syntax for writing down inductively defined sets.

BNF definitions give the name of the set being defined, and the list of rules defining the set in a compact form, separated by a vertical bar ().

A BNF definition looks like this:

The rules define the various ways of constructing objects in the set. Any uses of the variables on the left hand-side of any of the equations, should be replaced by already-constructed elements of the corresponding set.

The symbol is simply used to indicate that the definition is a BNF definition.

For example, the rules defining the natural numbers say that and for any . These would be written in BNF as follows:

Definition: natural number

The second rule says that you can form a new natural number by prepending an S onto an existing natural number.

### Example: strings

Definition: Σ*
The set of strings with characters in the alphabet is defined inductively by:

represents the empty string, while represents a string with 1 or more characters, starting with the shorter string and ending in the character .

For example, if , then

To add further detail, we can show that as follows:

By convention, we leave off the leading "ε" from non-empty strings. For example, we would write "001" instead of "ε001".

### Example: trees

The set of binary trees with integer nodes is defined inductively by

• Rule 1: The empty tree is in
• Rule 2: If and are trees, then the tree with value , left child and right child is in T.

We often think of trees pictorially; in this case we might give a BNF definition of as follows:

However, it is also useful to write trees symbolically; in this case we might define as follows:

Using the first definition, the following is an example tree:

Using the second definition, we would write this as

### Example: expressions

Mathematical expressions of various kinds are often defined inductively. For example, one might define a set of arithmetic expressions by the rules

Here, we are treating "+", "*", and "-" as uninterpreted symbols. For example, is an expression, formed from the substructures and using the "+" rule. Most programming languages have a similar inductive definition, allowing us to formally model programs.