# Prove that RecMatch is closed under string concatenation - Structural Induction

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?

• Welcome to math.SE. Please make the question self-contained and not reliant on links to external sites that might break. Sep 22, 2018 at 21:01
• Apparently, I need 10 rep to make the pic inline. Sep 22, 2018 at 21:21

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$$.