Section 11.4 Inductive definitions
We can use the idea of recursive definitions in a more general manner.
- inductive definition
a method of defining a collection of objects, where each object in the collection can be constructed from objects assumed or already known to exist in the collection
- base clause
a statement specifying some specific initial objects that belong to the inductively-defined set
- inductive clause
a statement describing a means to determine new objects in the inductively-defined set from those already known to belong
- limiting clause
a declaration that no objects belong to the inductively-defined set unless obtained from a finite number of applications of the base and inductive clauses
Example 11.4.1. Set of all possible logical statements.
Let us define a set \(\mathscr{L}\) with the following inductive definition.
Base clause.
For every \(m \in \N\text{,}\) the statement variable \(p_m\) belongs to \(\mathscr{L}\text{.}\)
Inductive clause.
Given statements \(A,B \in \mathscr{L}\text{,}\) the statements
\begin{equation*}
\lgcnot A, \quad A \lgcand B, \quad A \lgcor B, \quad A \lgccond B, \quad A \lgcbicond B
\end{equation*}
are also elements of \(\mathscr{L}\text{.}\)
Limiting clause.
The set \(\mathscr{L}\) does not contain any elements except those that can be obtained from a finite number of applications of the base and inductive clauses.
For example, the logical statement \(\lgcnot p_2 \lgcand (p_1 \lgccond p_2)\) is in \(\mathscr{L}\) by the following construction.
\begin{equation*}
p_1, p_2 \in \mathscr{L}
\quad \lgcimplies \quad \lgcnot p_2 \in \mathscr{L}, \;\; p_1 \lgccond p_2 \in \mathscr{L}
\quad \lgcimplies \quad \lgcnot p_2 \lgcand (p_1 \lgccond p_2) \in \mathscr{L}
\end{equation*}
Example 11.4.2. Set-theoretic construction of the natural numbers.
We assume that an empty set \(\emptyset\) exists. Let us define a set \(N\) inductively.
Base clause.
The empty set \(\emptyset\) is an element of \(N\text{.}\)
Inductive clause.
If \(X\) is an element of \(N\) and \(X\) itself is a set, then the set \(X^+ = X \cup \{X\}\) is also an element of \(N\text{.}\)
Limiting clause.
The set \(N\) does not contain any other elements except those that can be obtained from a finite number of applications of the base and inductive clauses.
Note that the three clauses together imply that every element of \(N\) must be a set, so the “and \(X\) itself is a set” part of the inductive clause is superfluous.
Since the base clause involves a single initial element of \(N\) and the inductive clause produces one new element of \(N\) from a single old element of \(N\text{,}\) we can explicitly carry out the construction step-by-step. We now define the natural numbers to be the elements in this construction:
\begin{align*}
0 \amp = \emptyset, \\
1 \amp = 0^+ = 0 \cup \{ 0 \} = \emptyset \cup \{ 0 \} = \{ 0 \} \ne 0, \\
2 \amp = 1^+ = 1 \cup \{ 1 \} = \{ 0 \} \cup \{ 1 \} = \{ 0, 1 \} \ne 0,1, \\
3 \amp = 2^+ = 2 \cup \{ 2 \} = \{ 0, 1 \} \cup \{ 2 \} = \{ 0, 1, 2 \} \ne 0,1,2 \\
\amp \;\;\vdots
\end{align*}
We usually write \(\N\) for this set instead of \(N\text{.}\)
Note that the number of elements in each natural number (as a set) is equal to the number defined by that set, and that each natural number \(m\) is defined to be the set that we have previously called \(\natnumlt{m}\text{.}\)
Bonus.
In
Example 11.4.2 above, we constructed the set
\(\N\) inductively using only the axioms of set theory. But how do we do arithmetic with this definition? We can define addition as an infinite collection of inductively-defined functions: for each
\(m \in \N\text{,}\) define a “sum with
\(m\)” function
\(\funcdef{s_m}{\N}{\N}\) as follows.
Base clause.
Set \(s_m(0) = m\text{.}\)
Inductive clause.
For \(n \in \N\) such that \(s_m(n)\) is already defined, set
\begin{equation*}
s_m(n^+) = s_m(n)^+ = s_m(n) \cup \{s_m(n)\} \text{.}
\end{equation*}
That is, if \(s_m(n)\) is defined and \(n^+\) is the next natural number after \(n\) in the inductive definition of \(\N\text{,}\) then define \(s_m(n^+)\) to be the next natural number after \(s_m(n)\text{.}\)
We then use the symbols \(m + n\) to mean \(s_m(n)\text{.}\) In this notation, you can think of the inductive clause above as saying that once \(m+n\) is defined, we can define \(m+(n+1)\) as \((m+n)+1\text{.}\)
If you are bored on a Friday or Saturday night, you can try the following using the above definition of addition in \(\N\text{.}\)
Checkpoint 11.4.3.
Prove that addition in \(\N\) is:
commutative: \(m+n = n+m\text{,}\) i.e. \(s_m(n) = s_n(m)\) for all \(m,n \in \N\text{;}\) and
associative: \((m+n)+\ell = m + (n+\ell)\text{,}\) i.e. \(s_{s_m(n)}(\ell) = s_m\bbrac{s_n(\ell)}\text{,}\) for all \(m,n,\ell \in \N\text{.}\)
Use the idea that every positive integer should have a negative to define \(\Z\) as a subset of the Cartesian product \(\N \times \N\text{.}\) Then define addition and subtraction in \(\Z\text{.}\)
Hint.To define \(\Z\text{,}\) first choose an appropriate one-to-one function embedding \(\N\) into \(\N \times \N\) in such a way that will then allow you to attach an additional second piece of information to each natural number (namely, a designator of the sign of the number).
