How do i start this inductive proof on Languages? $| L_1L_2 |$ = $| L_1 |$ $| L_2 |$

Question

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.

• Rob Arthan: Good question, but please use MathJax systematically for the formulas in your MSE questions. I suspect you were having problems with the braces: to get $L_1 = \{\epsilon\},ドル you type L_1 = \{\epsilon\} between two dollar signs.

Answer 1

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$.

• Lmath320: Ohhhh, you're totally right,Thank you very much, Now i see, i didn't think about this"i f we have two finite sets A,B and a surjection f:A→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.".It makes sense. This is very helpful, thanks for your time
• Mark Saving: @Lmath320 You’re welcome. I could have just given the example at the very end, but I wanted to provide some sort of motivation so you can see how I came up with the answer.