Inductively defined set

From CS2800 wiki
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: [math]\href{/cs2800/wiki/index.php/Z}{Z} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] (We think of Z as standing for "zero")
  • Rule 2: If [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] then [math]\href{/cs2800/wiki/index.php/S}{S}~n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] (S stands for "successor"; you can think of </math>S~n</math> it as representing "1 + n", although we will define + in terms of S instead of the other way around).

Thus the elements of [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] are [math]\{\href{/cs2800/wiki/index.php/Z}{Z}, \href{/cs2800/wiki/index.php/S}{S}~\href{/cs2800/wiki/index.php/Z}{Z}, \href{/cs2800/wiki/index.php/S}{S}~(\href{/cs2800/wiki/index.php/S}{S}~\href{/cs2800/wiki/index.php/Z}{Z}), \href{/cs2800/wiki/index.php/S}{S}\href{/cs2800/wiki/index.php/S}{S}\href{/cs2800/wiki/index.php/S}{S}\href{/cs2800/wiki/index.php/Z}{Z}, \dots\} [/math]. You can then define [math]1 [/math] as [math]1 \href{/cs2800/wiki/index.php?title=%3D&action=edit&redlink=1}{=} \href{/cs2800/wiki/index.php/S}{S}~\href{/cs2800/wiki/index.php/Z}{Z} [/math], [math]2 [/math] as [math]2 \href{/cs2800/wiki/index.php?title=%3D&action=edit&redlink=1}{=} \href{/cs2800/wiki/index.php/S}{S}\href{/cs2800/wiki/index.php/S}{S}\href{/cs2800/wiki/index.php/Z}{Z} [/math], and so on.

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 ([math]\href{/cs2800/wiki/index.php/%5Cmid}{\mid} [/math]).

A BNF definition looks like this:

[math]\begin{align*} var_1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} Set_1 &\href{/cs2800/wiki/index.php/BNF}{::=} \text{rule 1} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \text{rule 2} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \cdots \\ var_2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} Set_2 &\href{/cs2800/wiki/index.php/BNF}{::=} \text{rule 1} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \text{rule 2} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \cdots \\ & \vdots \end{align*} [/math]

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 [math]\href{/cs2800/wiki/index.php/BNF}{::=} [/math] symbol is simply used to indicate that the definition is a BNF definition.

For example, the rules defining the natural numbers say that [math]\href{/cs2800/wiki/index.php/Z}{Z} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and [math]\href{/cs2800/wiki/index.php/S}{S}~n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] for any [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]. These would be written in BNF as follows:

Definition: natural number
The set of natural numbers is given inductively by [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/BNF}{::=} \href{/cs2800/wiki/index.php/Z}{Z} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \href{/cs2800/wiki/index.php/S}{S}~n [/math]

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 [math]\href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] of strings with characters in the alphabet [math]\href{/cs2800/wiki/index.php/%CE%A3}{Σ} [/math] is defined inductively by:


[math]\begin{align*} x &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} \href{/cs2800/wiki/index.php/BNF}{::=} \href{/cs2800/wiki/index.php/%CE%95}{ε} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa} \\ a &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} Σ \end{align*} [/math]

[math]\href{/cs2800/wiki/index.php/%CE%95}{ε} [/math] represents the empty string, while [math]\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa} [/math] represents a string with 1 or more characters, starting with the shorter string [math]x [/math] and ending in the character [math]a [/math].

For example, if [math]\href{/cs2800/wiki/index.php/%CE%A3}{Σ} = \href{/cs2800/wiki/index.php/Enumerated_set}{\{0,1\}} [/math], then [math]\href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} = \{ε, ε0, ε1, ε00, ε01, ε10, ε11, ε000, ε001, \dots\} [/math]

To add further detail, we can show that [math]ε010 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] as follows:

  • [math]\href{/cs2800/wiki/index.php/%CE%95}{ε} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] by rule 1
  • [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] by rule 2, since [math]\href{/cs2800/wiki/index.php/%CE%95}{ε} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] and [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%CE%A3}{Σ} [/math]
  • [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}01 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] by rule 2, since [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] and [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%CE%A3}{Σ} [/math]
  • [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}010 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] by rule 2, since [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}01 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] and [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%CE%A3}{Σ} [/math]


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

Example: trees

The set [math]T [/math] of binary trees with integer nodes is defined inductively by

  • Rule 1: The empty tree is in [math]T [/math]
  • Rule 2: If [math]t_1 [/math] and [math]t_2 [/math] are trees, then the tree with value [math]a [/math], left child [math]t_1 [/math] and right child [math]t_2 [/math] is in T.


We often think of trees pictorially; in this case we might give a BNF definition of [math]T [/math] as follows:

Tree-defn.svg

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

[math]t \href{/cs2800/wiki/index.php/%E2%88%88}{∈} T \href{/cs2800/wiki/index.php/BNF}{::=} nil \href{/cs2800/wiki/index.php/%5Cmid}{\mid} tree(a,t_1,t_2) \qquad a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math]

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

Tree-example.svg

Using the second definition, we would write this as [math]tree(3,tree(0,nil,nil),tree(1,tree(0,nil,nil),nil)) [/math]

Example: expressions

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

[math]\begin{align*} e &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=Expr&action=edit&redlink=1}{Expr} \href{/cs2800/wiki/index.php/BNF}{::=} n \href{/cs2800/wiki/index.php/%5Cmid}{\mid} e_1 + e_2 \href{/cs2800/wiki/index.php/%5Cmid}{\mid} -e \href{/cs2800/wiki/index.php/%5Cmid}{\mid} e_1 * e_2 \\ n &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \end{align*} [/math]

Here, we are treating "+", "*", and "-" as uninterpreted symbols. For example, [math](3 + (4*5)) + (-2) [/math] is an expression, formed from the substructures [math](3+(4*5)) [/math] and [math](-2) [/math] using the "+" rule. Most programming languages have a similar inductive definition, allowing us to formally model programs.