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

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?

## 2 Answers

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

• Should I add, that I want to show $\forall w \in A^+ \implies w \in A^*$? – Doesbaddel Oct 18 '19 at 12:30
• @Doesbaddel, well if you want yes but it is the implicit definition of subset. In general we dont want to add ripetitions in proof. – Yamar69 Oct 18 '19 at 12:37
• 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. – Doesbaddel Oct 18 '19 at 12:59
• @Doesbaddel i am going to edit my answer a bit, indicating what I would do to prove this. – Yamar69 Oct 18 '19 at 13:08

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.