LOGIC Course

Structural induction

Go back

Exercise

$A$ a set of strings. A word is defined as a row of strings. $\epsilon$ is an empty row (a word without string). We also define string concatenation which is an operation of joining character strings end-to-end.

For instance, the concatenation of "zoo" and "logic" is "zoologic".

We are defining by induction the set $X$:

  • $\epsilon \in X$
  • If $u \in X$ then $a.u.b \in X$

Prove that $X=\{a^nb^n, n \in \mathbb{N}\}$

Proof by double induction


o $\{a^nb^n, n \in \mathbb{N}\}\subset X$

By mathematical induction, we give a proof that $\forall n \in \mathbb{N}$, $P(n)=$"$a^nb^n \in X$" is true.

Base case: Let's show that the statement holds for the smallest natural number $n=0$
$a^0b^0=\epsilon . \epsilon = \epsilon \in X$ (definition of X)
So $P(0)$ is true.

Inductive step: Let's show that for any $n\geq 0$, if $P(n)$ holds, then $P(n+1)$ also holds

$a^{n+1}b^{n+1}=a.a^nb^n.b$
But, by hypothesis, $P(n)$ is true. So $a^nb^n \in X$.
Then (definition of X) we deduce that $a^{n+1}b^{n+1} \in X$, that is $P(n+1)$.

Conclusion: the statement $P(n)$ holds for every $n \in \mathbb{N}$


o $X\subset \{a^nb^n, n \in \mathbb{N}\}$

By structural induction, we give a proof that $\forall u \in X$, $P(u)=$"$u \in \{a^nb^n, n \in \mathbb{N}\}$" is true.

Base case:
$\epsilon=\epsilon . \epsilon = a^0b^0 \in \{a^nb^n, n \in \mathbb{N}\}$
So $P(\epsilon)$ is true.

Inductive step: $u \in X$
We assume that $P(u)$ is true. Let's show that $P(a.u.b)$ holds.

By hypothesis, $P(u)$ is true. So $\exists k \in \mathbb{N}$, $u=a^kb^k$.
Then $aub=a^{k+1}b^{k+1} \in \{a^nb^n, n \in \mathbb{N}\}$, that is $P(aub)$.

Conclusion: the statement $P(u)$ holds for every $u \in X$

Conclusion: $X=\{a^nb^n, n \in \mathbb{N}\}$