May someone help me understand the following inductive definition of concatenation of strings:
We will define $\alpha\cdot\beta$ by induction on $|\beta|.$
- If $|\beta|=0\Rightarrow \beta=\epsilon,$ so then $\alpha\cdot\beta=\alpha\cdot\epsilon=\alpha$
- If $|\beta|=n+1,$ then $\beta=\gamma b,|\gamma|=n.$ Then $\alpha\cdot\beta=(\alpha\cdot\gamma)b$.
I understand the basis of the induction. At least I think I do.
Perhaps I don't understand how inductive definitions work. When $\beta$ is the empty word, then it's obvious that when we concatenate it with $\alpha$, we'll get $\alpha$ again. But then I don't understand what happens next and why we take the length of $\beta$ to be $n+1$. What's the idea? What's the inductive step when using induction to define a new object (how do we use it)?
Thanks!
You would have an inductive definition of "string", which typically has two constructors, one for the "empty" string, and one for the "compound" string with one head character followed by the rest of the string. (In fact, here a "string" isn't but a "list of characters".)
Then you would have a recursive definition of "concatenation of strings" by cases on the structure of one of the operands, not on its length: in your example, we consider $\beta$, with one case for $\beta$ empty, the other for $\beta$ a compound string.
Of course, for an appropriate definition of "size of a string", if $|\beta| = 0$, one can derive $\beta = \operatorname {empty}$, and, if $|\beta| \neq 0$, one can derive $\beta = h :: \gamma$ for some character $h$ and string $\gamma$, but that is an extra preliminary step that is not needed to reason inductively (on inductive strings as well as in general).
The "inductive step" is a step in proof by induction, so it is rather relevant in proving theorems about inductive structures.
More could be said but it gets quickly very technical: I'd rather invite you to consider what I have said above while (re)reading introductory articles and material, especially about "mathematical induction".