Same notation/terminology for union of sets and concatenation (Kleene star)?

Question

For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology and operator?

The following is my understanding of the union of sets versus the concatenation of sets (Kleene star). Please correct me if I'm wrong.

Union of sets

For the two sets $\{a,b\}$ and $\{a,b\}$ we have the union \begin{align} \{a,b\}\cup\{a,b\}=\{a,b\} \tag 1 \end{align} Update: For reference I used Union (set theory) from Wikipedia.

Concatenation of sets (Kleene star)

The concatenation of $\{a,b\}$ and $\{a,b\}$ is also a union (same notation?!) of two sets \begin{align} \{a,b\}^*&=\bigcup _{i=0}^{2} \{a,b\} ^2 \tag 2\\ &=\{a,b\} \cup \{a,b\} \tag 3\\ &=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\} \tag 4 \end{align}

Update: For reference I used Kleene star from Wikipedia. And here's where my confusion lies because at Wikipedia they also use the notation with the union operator: $$ V^* = \bigcup_{i\geq 0} V^i = V^0\cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots \tag 4 $$ Which is the same (?!) notation as in my $(2) - (3)$ but with the upper bound $2$. And the notation does not coincide with $(1)$.

Answer 1

Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines $$ V^* = \bigcup_{n \geq 0} V^n = V^0 \cup V^1 \cup V^2 \cup \cdots, $$ it literally means that $V^*$ is the union of the sets $V^0,V^1,V^2,\ldots$

The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \{\epsilon\}$, and $V^{n+1} = \{ xy : x \in V^n, y \in V \}$. In words, $V^n$ is the concatenation of $n$ words from $V$.

Answer 2

The concatenation of two sets of strings is the set formed of all pairwise concatenations of their elements. For instance, the concatenation of $\{a,b\}$ and $\{a,b\}$ is $\{a.a, a.b, b.a, b.b\}$, where $.$ is the string concatenation symbol. (Usually, we use no symbol for concatenation at all, and just write $\{aa, ab, ba, bb\}$.)

So in general, for two sets of strings $A, B$, their concatenation $AB$ is equal to $\{ xy \mid x \in A, y \in B \}$.

Now we can write

• $A^2 = AA$ = all strings that are 2 strings from $A$ concatenated
• $A^3 = AAA$ = all strings that are 3 strings from $A$ concatenated
• $A^4 = AAAA$ = all strings that are 4 strings from $A$ concatenated
• and so forth, and, for consistency,
• $A^1 = A$ = all strings that are 1 string from $A$ concatenated
• $A^0 = \{ \epsilon \}$ = all strings that are 0 strings from $A$ concatenated

Now the Kleene star of a set $A$ is the set $A^*$ formed by all strings consisting of arbitrarily many concatenations of strings from $A$. That is to say: such a string is

• either 0 strings from $A$ concatenated (it is in $A^0$)
• or 1 string from $A$ concatenated (it is in $A^1$)
• or 2 strings from $A$ concatenated (it is in $A^2$)
• or, ...

In other words: $\displaystyle A^* = \bigcup_{n}{A^n}$. The either ... or is where the union comes from.

You also wrote: correct me if I'm wrong. Well, you wrote this:

\begin{align} \{a,b\}^*&=\bigcup _{i=0}^{2} \{a,b\} ^2 \tag 2\\ &=\{a,b\} \cup \{a,b\} \tag 3\\ &=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\} \tag 4 \end{align}

Line (2) is just a weird way of writing $\{ a, b \} \cup \{ a, b \} \cup \{ a, b \}$. This is indeed equal to $\{ a, b \} \cup \{ a, b \}$ (3), which in turn is equal to $\{ a, b \}$. No string concatenation is going on at all here, so you're not getting any other elements than just $a$ and $b$. In (4), suddenly, you have a lot of concatenations. Clearly, that can't be right. You must have miscopied this from a source in which (2) and (3) were different.