Inductive Definitions

Motivation

Many important sets are described inductively: we specify:

1. Axioms: certain elements are in the set by fiat
2. Rules: ways to derive new elements from existing ones

This is more flexible than explicit enumeration or comprehension.

Axioms and Rules

Axioms

An axiom is a statement of the form: “element $a$ is in the set”.

We write axioms as horizontal lines with nothing above:

$\frac{}{a}$

Rules

A rule states: if $u_1, \ldots, u_n$ are in the set, then $v$ is in the set.

We write rules as:

$\frac{u_1 \quad u_2 \quad \cdots \quad u_n}{v}$

• The $u_i$ are called premises (or hypotheses)
• $v$ is called the conclusion
• A rule with no premises is an axiom

Closure Conditions

Given a set of rules $R$, each rule defines a closure condition:

$\{S \subseteq X : u_1, \ldots, u_n \in S \Rightarrow v \in S\}$

A set $S$ satisfies all closure conditions iff it is “closed under the rules.”

Defining Sets Inductively

Method

Given a set $X$ and a set of rules $R$:

1. Start with the axioms
2. Repeatedly apply rules to derive new elements
3. The inductively defined set $X_R$ contains all derivable elements

Formal Definition

Let $\text{Cl}_R$ be the collection of all subsets of $X$ closed under $R$.

$X_R = \bigcap_{S \in \text{Cl}_R} S$

This is the smallest subset of $X$ closed under $R$.

Why Smallest?

• $X_R$ itself is closed under $R$ (intersection preserves closure)
• Any $S$ closed under $R$ contains $X_R$ (if not, some element of $X_R$ would be missing from $S$)

Example: Natural Numbers

Define $\mathbb{N}$ inductively with rules:

$\frac{}{0} \qquad \frac{n}{S(n)}$

Interpretation

• $0 \in \mathbb{N}$ (axiom)
• If $n \in \mathbb{N}$, then $S(n) \in \mathbb{N}$ (successor rule)
• Nothing else is in $\mathbb{N}$ (smallest such set)

Derived Elements

$0, S(0), S(S(0)), S(S(S(0))), \ldots$ are all in $\mathbb{N}$.

Example: Binary Trees

Define trees with rules:

$\frac{}{\text{Leaf}} \qquad \frac{T_1 \quad T_2}{\text{Node}(T_1, T_2)}$

Derived Elements

Leaf, Node(Leaf, Leaf), Node(Node(Leaf, Leaf), Leaf), …

Example: A Language

Define $\{a^n b^n : n \geq 0\}$ with rules:

$\frac{}{\varepsilon} \qquad \frac{w}{awb}$

Derived Elements

$\varepsilon \in L$, so $a\varepsilon b = ab \in L$, so $aabb \in L$, so $aaabbb \in L$, …

Inductively Defined Functions

Setup

Given $a \in A$ and $f : \mathbb{N} \times A \to A$, define $\rho_{a,f} : \mathbb{N} \to A$ by:

$\rho_{a,f}(0) = a$ $\rho_{a,f}(n+1) = f(n, \rho_{a,f}(n))$

Existence and Uniqueness

The function $\rho_{a,f}$ exists and is unique.

Proof idea: Define $\rho_{a,f}$ as the intersection of all $(a, f)$-closed relations, then show it is total and functional.

---

Summary

• Inductive definition: specify axioms and rules
• The defined set $X_R$ is the smallest set closed under all rules
• $X_R = \bigcap\{S \subseteq X : S \text{ closed under } R\}$
• Examples: $\mathbb{N}$, trees, languages, recursive functions