11.4: Inductive definitions

We can use the idea of recursive definitions in a more general manner.

Definition: 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

Definition: Base Clause

a statement specifying some specific initial objects that belong to the inductively-defined set

Definition: Indutive Clause

a statement describing a means to determine new objects in the inductively-defined set from those already known to belong

Definition: 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 \(\PageIndex{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 \mathbb{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*} \neg A, \quad A \land B, \quad A \lor B, \quad A \rightarrow B, \quad A \leftrightarrow 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 \(\neg p_2 \land (p_1 \rightarrow p_2)\) is in \(\mathscr{L}\) by the following construction.

\begin{equation*} p_1, p_2 \in \mathscr{L} \quad \Rightarrow \quad \neg p_2 \in \mathscr{L}, \;\; p_1 \rightarrow p_2 \in \mathscr{L} \quad \Rightarrow \quad \neg p_2 \land (p_1 \rightarrow p_2) \in \mathscr{L} \end{equation*}

Example \(\PageIndex{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 & = \emptyset, \\ 1 & = 0^+ = 0 \cup \{ 0 \} = \emptyset \cup \{ 0 \} = \{ 0 \} \ne 0, \\ 2 & = 1^+ = 1 \cup \{ 1 \} = \{ 0 \} \cup \{ 1 \} = \{ 0, 1 \} \ne 0,1, \\ 3 & = 2^+ = 2 \cup \{ 2 \} = \{ 0, 1 \} \cup \{ 2 \} = \{ 0, 1, 2 \} \ne 0,1,2 \\ & \;\;\vdots \end{align*}
We usually write \(\mathbb{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 \(\mathbb{N}_{<m}\text{.}\)

Bonus

In Example \(\PageIndex{2}\) above, we constructed the set \(\mathbb{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 \mathbb{N}\text{,}\) define a “sum with \(m\)” function \(s_m: \mathbb{N} \rightarrow \mathbb{N}\) as follows.

Base clause.

Set \(s_m(0) = m\text{.}\)

Inductive clause.

For \(n \in \mathbb{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 \(\mathbb{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 \(\mathbb{N}\text{.}\)

Checkpoint

1. Prove that addition in \(\mathbb{N}\) is:

 

1. commutative: \(m+n = n+m\text{,}\) i.e. \(s_m(n) = s_n(m)\) for all \(m,n \in \mathbb{N}\text{;}\) and
2. associative: \((m+n)+\ell = m + (n+\ell)\text{,}\) i.e. \(s_{s_m(n)}(\ell) = s_m(s_n(\ell))\text{,}\) for all \(m,n,\ell \in \mathbb{N}\text{.}\)

 

2. Use the idea that every positive integer should have a negative to define \(\mathbb{Z}\) as a subset of the Cartesian product \(\mathbb{N} \times \mathbb{N}\text{.}\) Then define addition and subtraction in \(\mathbb{Z}\text{.}\)

Hint.

To define \(\mathbb{Z}\text{,}\) first choose an appropriate one-to-one function embedding \(\mathbb{N}\) into \(\mathbb{N} \times \mathbb{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).