Recursively prove that two recursively defined sets are the same

Question

I am reading MIT's Mathematics for Computer Science, and there is a problem where you're asked to prove that two recursively defined sets are the same. I'm not sure how to go about mutual inclusion with recursively defined sets.

Here is the problem: A and B are sets of strings of matched brackets. Define A as the smallest set such that: Base case: $\lambda$, the empty string, is in the set. Constructor cases: 1. $st$ is in A (meaning $s$ concatenate $t$ is in A). 2. [$s$] is in A

Define B as the smallest set such that: Base case: $\lambda$, the empty string, is in the set. Constructor cases: $[s]t$ is in B.

Prove A and B are the same set:

Here is my attempt: Clearly $\lambda$ is in both sets. Now want to show that anything can be constructed by recursive definition of $A$ can be also constructed with recursive definition of $B$. Suppose $s \in A$, I want to show $[s] \in B$ and $st \in B$.

$[s] \in B$ since we can let $t=\lambda$ in B, and thus $[s] \in B$. Is this right? It seems like I'm supposing $s$ the same in both sets. I am stuck at how to show $st \in B$.

Answer 1

Note that all strings are made up of $[$ and $]$ only.

For clarity, call the variables $s, t$ on one side and $x, y$ on the other. As you note, you have to prove both sets of rules give the same end results, you are trying to get an intermediate result. No wonder it won't work.

Answer 2

I think I got it:

I will prove by structural induction.

Base case: The empty string $\lambda \in A, B$ clearly.

Induction step: Let $x,y \in A$ and $s,t \in B$. Assume that $x$ and $y$ can be constructed by the recursive definition of $B$, and assume that $s$ and $t$ can be constructed using the recursive definition of $A$. We want to show that 1) $xy$ and $[x]$ can be constructed with $[s]t$ for suitable $s$ and $t$, and 2) $[s]t$ can be constructed by $xy$ and $[x]$.

1) Clearly $[x]=[s]\lambda$ for any $s=x$ and $t=\lambda$, so $[x]$ can be constructed with $[s]t$. Next, $xy=[s']t'y$ where $s', t' \in B$ by the structural induction assumption. Thus take $s=s'$ and $t=t'y$, so $xy$ can be constructed by $[s]t$.

2) [s]t can be constructed by $xy$, by letting $x=[x']$ where $x'=s$ and $y=t$

Thus we have A=B.