Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?)

share|cite|improve this question
Are you sure that propositional calculus and logic fit here? It sounds like an exercise in formal languages. – Asaf Karagila May 21 '11 at 15:48
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. – user10324 May 21 '11 at 19:32
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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