Prove that RecMatch is closed under string concatenation - Structural Induction

Question

Let RecMatch be the set of strings of matched brackets of Definition 7.2.1. Prove that RecMatch is closed under string concatenation via structural induction. Namely, if s and t are strings in RecMatch, then s * t are in RecMatch. [7.2.1 ReMatch Definition][1]: https://i.stack.imgur.com/oT2ZZ.jpg

I'm a little stuck on this question. So far, I have stated the predicate and set some strings s & t to be the empty string to satisfy the base case. For the constructor case, I assume I would use the constructor case in the def. of RecMatch to prove this, but I don't know how to word that without saying the exact same thing. Could someone help me better formulate my constructor case?

Answer 1

The claim is

If $a,b\in\text{RecMatch}$, then $ab\in\text{RecMatch}$.

We can prove this by structural induction on $a$. That is, we let $$ S=\{\,a\in\text{RecMatch}\mid\forall b\in\text{RecMatch}\colon ab\in\text{RecMatch}\,\}$$ and show that $S$ is all of RecMatch.

• As $\lambda b=b$, we clearly have $\forall b\in\text{RecMatch}\colon \lambda b\in\text{RecMatch}$ and hence $\lambda \in S$.

• If $a=[s]t$, we may assume that already $s,t\in S$. Let $b\in\text{RecMatch}$ be arbitrary. As $t\in S$, we find $tb\in\text{RecMatch}$. But from $s\in \text{RecMatch}$ and $tb\in\text{RecMatch}$, we also get $[s]tb\in\text{RecMatch}$. As this is $ab$ and $b$ was arbitrary, we see that $a\in S$.