# How to prove structural induction theorem

I'm currently looking for how to prove the structural induction theorem which states that when you want to prove a statement on every elements of a set defined by induction you have to prove that each element of the base set match with the statement, and then that each rule of construction also holds the statement. I don't know how to prove that kind of induction which seems to be the root of languages definition. Any Idea ? I heard that fixed point theorem from Kleene could be useful for that.

Let's make the claim precise: let $(A, (f_i)_{i\in I})$ be a set and a family of functions $f_i : A \to A$.

Let $B\subset A$ be any subset and let $C$ be the smallest subset of $A$ containing $B$ and stable under each of the $f_i$.

Then : 1. $C$ is well-defined.

1. For any property $P$ of elements of $A$, to prove $\forall x \in C, P(x)$, it suffices to prove $\forall x\in B, P(x)$ and $\forall i \in I, \forall x \in A, P(x) \implies P(f_i(x))$.

Well for 1., it's pretty easy: $A$ is a subset of $A$ that is closed under the $f_i$'s, and so $C:=\bigcap \{ E\subset A \mid B\subset E$ and $E$ is closed under the $f_i\}$ is well defined. It is obvious that this set is included in any subset of $A$ closed under the $f_i$, and it is also clear that $C$ itself is closed under the $f_i$'s, which establishes the claim.

1. is easily established from 1: let $P$ be any such property, and assume we know $\forall x\in B, P(x)$ and $\forall i \in I, \forall x \in A, P(x) \implies P(f_i(x))$. Let $K:= \{x\in C \mid P(x)\}$. Then clearly, from the assumption, $B\subset K$. Moreover the assumption implies that $K$ is closed under the $f_i$. Therefore $C\subset K$, by definition of $C$. But by definition, $K\subset C$, so $K=C$. Therefore, $\forall x\in C, P(x)$. This establishes claim 2.

Now what you can easily see is that having the $f_i : A\to A$ or $f_i : A^{E_i} \to A$ for some $E_i$ doesn't change anything, the argument can be as easily carried out. Usually, the case will be that the $E_i$'s are some integers (for instance for propositional logic, you'll have $f_{\land} : (P,Q) \to (P\land Q)$ etc.) I'll let you prove this variant if you think that it's not so trivial.

Now applying this to languages gives you what you want.

EDIT: To answer to the comments below :

Claim 1: $C$ is closed under the $f_i$'s: indeed, let $x\in C$. Then for all $E\subset A$ such that $B\subset E$ and $E$ is closed under the $f_i$'s, $x\in E$. THerefore, for all these sets, $f_i(x) \in E$. Therefore, $f_i(x)$ belongs to their intersection, which is $C$, so that $C$ is closed under the $f_i$'s.

Claim 2: $K$ is closed under the $f_i$'s. Let $x\in K$. Then by definition, $x\in C$ and $P(x)$. Therefore, since $\forall y\in A, \forall i\in I, P(y)\implies P(f_i(y))$ (that was our assumption), we have $\forall i\in I, P(x) \implies P(f_i(x))$. Therefore, since $P(x)$ is true, for all $i\in I$,$P(f_i(x))$. Moreover, by claim 1 $C$ is closed under the $f_i$ so that for all $i\in I$, $f_i(x) \in C$ and $P(f_i(x))$. But by definition this implies $f_i(x) \in K$. Therefore, $K$ is closed under the $f_i$'s

• Just a question, you said that C is the intersection of all the subparts of A where this subpart is closed under f_i. It means that C is the smallest subset closed under f_i ? – toto Jun 11 '17 at 20:39
• Sorry, I edited : smallest subset containing $B$ and closed under the $f_i$. It's important that it has both these properties. It's in a sense the subset "spanned" by $B$ under the $f_i$. If all the $E_i$'s are finite you can actually give a description of $C$ as a countable union as well. – Max Jun 11 '17 at 20:43
• is this way of thinking by an intersection also valid to speak about minimum integer of a subset of natural number sets when they are built using Von Newmann system ? like : B = {0}. And f_0 : N->N : n->{n} U n. Because 0 := {} 1:={0} 2:={0,1} 3:={0,1,2} 4:={0,1,2,3} and so on. – toto Jun 11 '17 at 20:48
• Intersection is always the minimum with respect to inclusion. As it happens, Von Neumann integers, which are finite ordinals, are ordered by $\leq = \subset$. So the minimum of a (nonempty) set of integers is their intersection. For instance, $2\cap 3= 2$ (using Von Neumann integers) – Max Jun 11 '17 at 20:52
• Ok so, using that structural induction we can prove some statements about formal languages through non contextual grammar rules which could be associated with f_i rules in the discussion below ? – toto Jun 11 '17 at 20:55

There is really no separate proof for that. It is really just relying on the recursive definition of a set of objects. That is, if a set of objects $S$ is defined in the folowing way:

1. A set $A$ of 'atomic' objects is in $S$

2. If objects $o_1, ... , o_n$ are in $S$ then objects $f_1(o_1,...,O_n), ...f_m(o_1,...,o_n)$ are in $S$ as well, where $f_i$ is some operator or function that maps objects to objects.

3. Nothing else is in $S$ (Or: $S$ is the smallest set satisfying 1 and 2)

Then it is really just obvious that a proof by structural induction that follows this same recursion works. That is, if you can show that:

1. All the 'atomic' objects in $A$ have some property $P$

2. If objects $o_1,...,o_n$ have property $P$ then objects $f_1(o_1,...,o_n), ..., f_m(o_1,...,o_n)$ have property $P$ as well

then that will prove that all objects in $S$ have property $P$.

• You say that it's obvious, but are you sure that there does not exist a theorem about that ? – toto Jun 11 '17 at 20:13
• @toto I suppose one could do some kind of proof of contradiction. That is, if you have completed the structural inductive proof, assume that there are still objects in $S$ that do not have property $P$. Such an object cannot be an 'atomic' objects, since you just showed they all have property $P$. Now, since every object was constructed from atomic objects and applying the recursive step some finite number of times, take the 'smallest' (in the sense of how many steps it took to create that object) that does not have property $P$, Since the ones that it was constructed from do have property ... – Bram28 Jun 11 '17 at 20:20
• And actually, what do you mean by "S is the smallest set satisfying 1 and 2". I don't get the idea of smallest set. Can you explain ? – toto Jun 11 '17 at 20:21
• (..continued) $P$, this 'smallest' object must have $PQ$ as well, since you just showed that. But really, I don't think that such a proof by contradiction adds any further insight ... – Bram28 Jun 11 '17 at 20:21
• @toto OK, say you define a set of objects as follows: 1. String $a$ is in $S$. 2. If $\varphi$ is a string in $S$, then $a \varphi$ is a string in $S$ as aell. Now, the smallest set of objects that satisfies1 and 2 is $\{ a,aa,aaa,...\}$. The set $\{ b,a,aa,aaa,...\}$ satisfies 1 and 2 as well, but clearly the first set is the smallest or 'minimal' one ... It does not have objects that you can't get thrpugh 1 and 2. – Bram28 Jun 11 '17 at 20:25