How to approach a proof where the answer can be both false and true?

43 Views Asked by At

Definition of symbols:

Given $E = \{a,b\}$ an alphabet, $E^*$ denotes all strings over the alphabet i.e. $E^* = \{a,b,aa,ab,\dots\}$.

I have to answer: Given $A\subseteq E^*$, is $AA \subseteq A$?

If I define $A = \{a,b,aa,ab\}$, then by definition $AA$ is the concatenation of $A+A$, thus $$AA = \{aa,bb,aaaa,abab\}$$ Since not every element in $AA$ is an element in $A$ that proves $AA$ is not a subset of $A$.

Whereas if I define $A = \{\epsilon\}$, then $AA = \{\epsilon +\epsilon\}=\{\epsilon\}=A$. This proves AA is indeed a subset of A.

What should I do here? I got a true case and a false case

1

There are 1 best solutions below

0
On

First as @HagenvonEitzen said you got your $AA$ wrong.

However you indeed have a case which is false and the other one which is true.

But the question as it is asked, ask whether the property hold for every $A\subseteq E^*$. And since you have found a counter example you can conclude that the property is false.