1
$\begingroup$

If I have a set $S$ defined as the smallest set $S$ over an alphabet $A=\left\{ \star, \urcorner,(,), a_0,a_1, \dots \right\}$ ( $S\subseteq \cup_{k \in \mathbb{N}} A^k$) satisfying:

$\bullet \ a_0, a_1, \ldots$ $\in S$

$\bullet $ if $\alpha \in S$ then $ ( \urcorner \alpha) \in S$,

how can I then show for example that $( \alpha \urcorner )$ or $\alpha ()$ is not in the recursively defined set $S$, where $\alpha$ is some element of $S$ (or even $S\subseteq \cup_{k \in \mathbb{N}} A^k$, for greater generality). Of course I can "see" that this is the case, but how can I prove it ?

Maybe because it seems so easy to see that strings like the above can't be in $S$ I can't up with a proof. (Of course, if $\star \alpha$ were in $S$, intuitively it would be clear, that $S$ woulsn't be the smallest set anymore, but how would I then prove this ?)

  • 0
    Maybe. But there isn't a "formal languages" tag and I came up with the question while browsing a chapter on propositional calculus...but feel free to edit the tags, if you want to.2011-05-21

1 Answers 1

0

Added Remark: This is a solution to the previous incarnation of the question, which was quite different (it asked one to show that no word of shape $\star\alpha$ is in the set). This is not a solution of the altered question!

It is obvious, and does not require proof (unless, weirdly, it is demanded that you prove it).

What do we mean by "smallest set $S$"? In the context of this kind of definition, it means the intersection of all the sets satisfying your two bulleted conditions.

Now let $W$ be the set of all words over the alphabet that contains everything except the $\star$, Then $W$ obviously satisfies the bulleted conditions. It follows by the definition of $S$ that $S \subset W$, since $W$ is one of the sets that was intersected to make $S$. And it is clear that no word of the form $\star\alpha$ is in $W$.

Remark about changed question The strategy of a proof does not change much for the altered questions. (But if the question changes again, the strategy might have to change). For example, look at the set $Z$ of words that do not end with $()$ or with $($. It is clear that if $\alpha$ is in $Z$, then the string produced by the second bulleted condition is in $Z$. So $Z$ is one of the sets intersected to produce $S$. This implies that $S$ does not contain any string of shape $\alpha()$.