🍈 Zettelkasten

❯

Structural Induction

Structural Induction

Sep 13, 20252 min read

proofs
math

Proof method used widely in Graph Theory Used to prove some Logical Predicate $P (x)$ holds for all $x$ of some recursively defined structure.

Structure

Define $P (x)$

Base Case

With $x$ as a recursive structure
1. Prove $P (x)$

Induction Step

Suppose $P (x)$ holds for sub-structures used in recursive step of definition
1. Prove $P$ holds for the recursively constructed structure

Example

With a well-formed set of expressions comprised of:

Variables $x, y, z, \dots$
Operations $+, -, \times, \dots$ Define the Alphabet for the expressions ${x, y, z, +, -, x, \div, (,)}$ Let $E$ be the smallest set.

Base Case

Let our base case be $x, y, z \in E$

Induction Step

Assume $e_{1}, e_{2} \in E$ then, $(e_{1} + e_{2}), (e_{1} - e_{2}), (e_{1} \times e_{2}), (e_{1} \div e_{2}) \in E$ …

Example 2

Given a string $e \in Σ^{*}$ For example, $e = x yz + x y + x () \div$ we define:

$v r (e)$ be the number of occurrences of variables in $e$
- For example, $v r (x yz + x y + x () \div) = 6$
$o p (e)$ be the number of occurrences operators in $e$
- For example, $o p (x yz + x y + x () \div) = 3$ We define $P (e) : v r (e) = o p (e) + 1$ Prove that $\forall e \in E, P (e)$

Base Case

Consider 3 cases:

$e = x$
$e = y$
$e = z$ Then, notice that for all cases $v r (e) = 1 = 0 + 1 = o p (e) + 1$

Induction Step

Let $e_{1}, e_{2} \in E$ Suppose $P (e_{1}), P (e_{2})$ Induction Hypothesis Then, given four cases:

$e_{1} + e_{2}$
- Note that $v r (e_{1} + e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} + e_{2}) + 1$
$e_{1} - e_{2}$
- Note that $v r (e_{1} - e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} - e_{2}) + 1$
$e_{1} \times e_{2}$
- Note that $v r (e_{1} \times e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} \times e_{2}) + 1$
$e_{1} \div e_{2}$
- Note that $v r (e_{1} \div e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} \div e_{2}) + 1$ Thus, we get $\forall e \in E, P (e)$

Graph View

Structure
Example
Example 2

Backlinks

Theory of Computation

Created with Quartz v4.4.0 © 2025

GitHub
Discord Community