2
$\begingroup$

Prove, that $A^+\subseteq A^*$, where $A$ is a formal language.

The definition of $A^+$ is $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i$, which would be $A^1 \cup A^2 \cup \dots \cup A^i$. Likewise, $A^*$ is $\bigcup_{i\in\mathbb{N}}A^i$ and therefore $A^0 \cup A^1 \cup \dots \cup A^i$.

Suppose, $x\in A^+$. By definition $x\in A^+ \land x\in A^*$ for all $x\neq A^0$, which is the set of the empty word. We can conclude, that $A^1\cup A^2\cup \dots \cup A^i \subseteq A^0\cup A^1\cup \dots \cup A^i$ and $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i \subseteq \bigcup_{i\in\mathbb{N}}A^i$, that's why $A^+\subseteq A^*$.

Is this "proof" ok?

$\endgroup$
3
$\begingroup$

It seems you have hit the reasoning correctly: A set $S$ is a subset of another set $A$ if $w\in S\implies w\in A$. Since you are trying to show that $\forall w \in A^+ \implies w \in A^*$, you are proving that $ A^+ \subseteq A^*$.

One more legant way to formally do this is by finding a bijection between the two sets. Since $|A^*|$ = $|\Bbb N|$ you need to prove that $|A^+|$ is a subset of $|\Bbb N|$. So you need to find a Bijection (left to you since we dont do Homework for the OP's) from these two sets. Note that there exists $2^{\aleph_0}$ such functions, so you have a large selection space :)

$\endgroup$
  • $\begingroup$ Should I add, that I want to show $\forall w \in A^+ \implies w \in A^*$? $\endgroup$ – Doesbaddel Oct 18 at 12:30
  • 1
    $\begingroup$ @Doesbaddel, well if you want yes but it is the implicit definition of subset. In general we dont want to add ripetitions in proof. $\endgroup$ – Yamar69 Oct 18 at 12:37
  • $\begingroup$ Ok, so ... everything is correct? I'm just wondering, because you used the phrase "almost fine" and I don't really know what's still wrong. $\endgroup$ – Doesbaddel Oct 18 at 12:59
  • 1
    $\begingroup$ @Doesbaddel i am going to edit my answer a bit, indicating what I would do to prove this. $\endgroup$ – Yamar69 Oct 18 at 13:08
2
$\begingroup$

The "$x\in A^{+}$. By definition $x\in A^{+} \wedge x\in A^{*}$ for all $x\neq A^{0}$" is a bit weird. Not even from a computer science point of view but from a set theory or general mathematical point of view. First, you're saying the same thing again with "$x\in A^{+}$" which you shouldn't. Then, you're saying $x\in A^{*}$ which is the desired result.

I think a better way to write would be as follows: let $w\in A^{+}$. Then, by definition, there is $i\in \mathbb{N}\setminus{\{0\}}$ such that $w\in A^{i}$. However, $A^{i}\in \bigcup_{j=0}^{\infty} A^{j}=A^{*}$ so $w\in A^{*}$.

Conceptually not different than your answer, just written differently.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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