The following notation $| L_1L_2 |$ = $| L_1 |$ $| L_2 |$ denotes that the number of strings in the $L_1L_2$ concatenation is the same as the product of two numbers $| L_1 |$ and $| L_2 |$. If this statement is always true for any two languages, give formal arguments for proof it and if not, you need to show two languages $L_1$ and $L_2$ such that $| L_1L_2 |$ is not equal to$| L_1 |$ $| L_2 |$.
I tried to solve this by induction proof, but i don't see what is the step base , i'm confuse about what step base .I think in the proof is something like:
$\epsilon$ = void string
L1 = {$\epsilon$} then proof $|\{\epsilon\} L2 |$ = $|\{\epsilon\}|$ $| L_2 |$.
By definition, $\{\epsilon\} L_2 $ = $L_2$, so this is $|\{\epsilon\} L2 |$ = $|L_2|$
Now,it's easy to see |{$\epsilon$}| = 1 therefore $|\{\epsilon\}|$ $| L_2 |$ = 1 $|L_2|$ = $|L_2|$
Well, I don't know if I'm right, but if so, then how can I proceed with the inductive step. Thanks for the help.
Let $+$ be the string catenation operator.
By definition, $L_1 L_2 = \{x_1 + x_2 \mid x_1 \in L_1, x_2 \in L_2\}$.
Consider the fact that by the very definition of $L_1 L_2$, we have the function $+ : L_1 \times L_2 \to L_1 L_2$, and $+$ is a surjective function.
Now in the event that $L_1$ and $L_2$ are both finite, we see that $L_1 \times L_2$ is also finite, and therefore so is $L_1 L_2$. In fact, we have $|L_1 L_2| \leq |L_1 \times L_2| = |L_1| \times |L_2|$ since there is a surjection $+ : L_1 \times L_2 \to L_1 L_2$.
Now keep in mind that if we have two finite sets $A, B$ and a surjection $f : A \to B$, then $|A| = |B|$ if and only if $f$ is a bijection. This is a function between two sets of the same finite cardinality is an injection if and only if it is a surjection.
So in the event that $L_1$ and $L_2$ are both finite, we have $|L_1 L_2| = |L_1||L_2|$ if and only if $+ : L_1 \times L_2 \to L_1 L_2$ is injective.
But we can easily find an example where this isn't the case. Consider, for instance, $L_1 = \{\epsilon, 1\} = L_2$. $\epsilon + 1 = 1 + \epsilon = 1$, so $+$ is not injective. Indeed, we see that $L_1 L_2 = \{\epsilon, 1, 11\}$ has only 3 elements, while $|L_1| |L_2| = 4$.