1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ So in your constructor step, you assume s,t is in RecMatch from the def. But what is meant by tb is in RecMatch? Or how did you get to this step in your answer? $\endgroup$
    – aBitwise
    Sep 22, 2018 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.