Proving that $|AB| \leq |A| \cdot |B|$

Question

How to prove the inequality of concatenating two languages? $|AB|\leq |A| \cdot |B|$

I know that:

Let $A,B \subseteq \Sigma^*$ and the concatenating of $A,B$ will as following: $AB=\{wx \mid w \in A, x \in B \}$. Hence by definition $\forall x \in w$ will be concatenating with every word in $B$ and vice versa, and if no words are repeated we get the new language which has the length of: $|A|\cdot|B|$. And $AB$ could be less than $|A|\cdot|B|$ because some words which could be repeated are ignored like, $\{aa,aaa\}\in A$, and $\{aa,a\} \in B$ we get: $\{aaaa,aaa,aaaaa,aaaa\} = \{aaa,aaaa,aaaaa\}$.

But I'm not sure if there is more direct way to prove it just using the inequalities with some simplifications like a normal equation?

Answer 1

There is a simple function $f:A\times B\rightarrow AB$ (where $A\times B$ is the cross product of two sets).

Its not hard to show that this function is also onto, and therefore $|A|\cdot |B|=|A\times B|\ge |AB|$ as required.

Answer 2

How about induction on languages?

Proof. Assume that for every subset of $A$ the statement holds. Then there are two cases to consider:

1. Suppose $A = \varnothing$. Then $|A \bullet B| = |\varnothing \bullet B| = |\varnothing| = 0 \leq |\varnothing| \cdot |B| = 0$.
2. Suppose $A = S \cup T$, for any two disjoint subsets $S$ and $T$. Then $$ |A \bullet B| = |(S \cup T) \bullet B| = |(S \bullet B) \cup (T \bullet B)| \leq |S \bullet B| + |T \bullet B| \leq \\ \leq |S| \cdot |B| + |T| \cdot |B| = (|S| + |T|) \cdot |B| = |A| \cdot |B|. $$