# How to prove that these formulas are uniquely readable.

We have the inductively defined set, M, as follows(this is a language over the alpabet $$(e,a,\bar{a},b,\bar{b})$$:

We let $$M$$ be the smallest set so that

$$e\in M$$

If $$x,y\in M$$ then $$xy\in M$$

If $$x \in M$$ then $$ax\bar{a}\in M$$

If $$x \in M$$ then $$bx\bar{b}\in M$$

How to I prove that this set is uniquely readable? That is, if $$f\in M$$. Then F is either $$xy$$ for uniquely x and y. Or f is $$ax\bar{a}$$ for uniquely x. Or f is $$bx\bar{b}$$ for uniquely x. Or f is e.

I tried using the proof that the formulaes in proposition logic are uniquely readable. There we are supposed to show that no formula is an initial segment of another formula. But I couldn't get that to work.

• What is the context here? You have used the logic and recursion tags, but the question seems more to do with parsing or grammar theory. Commented Jun 4, 2023 at 22:37
• Unless I'm misunderstanding something, what you're trying to prove is false. $eee$ is $xy$ with $x=ee$ and $y=e$, and it's also $xy$ with $x=e$ and $y=ee$. So the uniqueness requirement fails. Commented Jun 5, 2023 at 0:04
• @AndreasBlass Thank you very much! Commented Jun 5, 2023 at 14:24