3
$\begingroup$

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$:

$ |xy| = |x| + |y| $

with $x, y \in \Sigma^*$.

To prove this, I am expected to make use of the following two definitions:

  1. for $x=\epsilon$ we have $|x|=0$
  2. for $x=au$, being $u \in \Sigma^*$ and $a \in \Sigma$ we have $|x|=1+|u|$

Intuitively it is easy to understand what is being asked here. The idea is to prove that the length of the concatenation of any two strings is equal to the sum of their individual lenghts.

What I am failing to realise is how to tackle the problem. Should I make use of induction? Just algebraic manipulation?

Any pointers would be welcome.

  • 0
    @Didier: (cont) By "layer" I mean that you can view $\Sigma^*$ as a union of sets, the $k$-th set being $\Sigma^k$. This is the $k$th layer. I'm doing induction on $k$. I do **not** assume that if $x\in\Sigma^k$, then $|x|=k$. I only assume that if $x\in\Sigma^k$, then $|xy| = |x|+|y|$. The inductive step uses only the *definitions* of $\Sigma^{k+1}$ and of $|\cdot|$, and not any derived properties like the converse of the definition. I do not assume *anything* about $|x|$ or $|u|$, except what is in the definitions. It's not induction on $|x|$.2011-03-27

3 Answers 3

4

See this answer and this one for general advice and discussion on induction. Your argument above is, alas, neither very clear nor correct.

So, we have that $|\epsilon|=0$, and that if $x=au$ with $a\in\Sigma$, $u\in\Sigma^*$, then $|x|=1+|u|$. We want to prove that for all $x,y\in\Sigma^*$, we have $|xy|=|x|+|y|$.

What you really need here is an explicit definition of $\Sigma^*$, because you need to be able to handle elements of $\Sigma^*$. I'm guessing, pending you posting the definition, that you have a certain "alphabet" $\Sigma$, and then define $\Sigma^*$ as the collection of all strings of letters from $\Sigma$ in some way.

Assuming the intended definition is the definition in this page, we can proceed as follows.

For all $n$, if $y\in \Sigma^*$ and $x\in\Sigma^n$, then $|xy|=|x|+|y|$.

If we can prove this, it will follow that for all $x$ in $\cup\Sigma^n = \Sigma^*$, we have $|xy|=|x|+|y|$, which is what we want to prove.

We will prove the proposition above by induction on $n$.

Base. $n=0$. Let $x\in\Sigma^0$. Then $x=\epsilon$, so $xy = y$ and $|x|=0$ by definition of $|\epsilon|$. Therefore, $|xy|=|y|=0+|y| = |x|+|y|$, so the equality holds.

Inductive step. We want to prove that if it is true that for all $z\in \Sigma^k$, $|zy|=|z|+|y|$, then it is true that for all $x\in\Sigma^{k+1}$, we also have $|xy|=|x|+|y|$.

Induction hypothesis. If $z\in\Sigma^k$, then $|zy|=|z|+|y|$.

Let $x\in\Sigma^{k+1}$. We want to prove that $|xy|=|x|+|y|$.

Since $x\in\Sigma^{k+1}$, then $x=au$ with $a\in\Sigma$ and $u\in\Sigma^k$.

Then we have by the definition of $|\cdot|$ that $|xy| = |(au)y| = |a(uy)| = 1 + |uy|.$ And by the Induction Hypothesis, since $|u|\in\Sigma^k$, we get $|xy| = 1+|uy| = 1+(|u|+|y|) = (1+|u|)+|y|.$ But by the definition of $|\cdot|$ we have $|x| = |au| = 1+|u|$, so $|xy| = (1+|u|)+|y| = |x|+|y|,$ as desired.

Thus, if for every $z\in\Sigma^k$ we have $|zy|=|z|+|y|$, then for every $x\in\Sigma^{k+1}$ we have $|xy|=|x|+|y|$.

By induction, we conclude that for all $n$, if $x\in\Sigma^n$ then $|xy|=|x|+|y|$.

Therefore, we have that for all $x\in\mathop{\cup}\limits_{n=0}^{\infty}\Sigma^n$, $|xy| = |x|+|y|$.

Thus, for all $x\in \Sigma^*$, $|xy|=|x|+|y|$.

Since $y\in\Sigma^*$ is arbitrary, we conclude that

For all $x,y\in \Sigma^*$, $|xy|= |x|+|y|$

as claimed. QED

  • 0
    @Didier: The second definition of the Kleene closure/ Kleene star given in WP is, likewise, **precisely** the "bottom up" approach I gave, using **precisely** the sets $\Sigma_n$, which are defined **recursively**. http://en.wikipedia.org/wiki/Kleene_star . Since WP invokes the Kleene star in its *formal* definition of $\Sigma^*$ (as opposed to the informal definition as "all strings"), the definition is only "all at once" if you choose to ignore the meaning of "Kleene star", or if you choose to think that an informal definition is a substitute for a mathematical one.2011-03-27
1

I have upvoted Arturo Magidin's answer. But aren't we shooting with cannons on sparrows here? A fundamental principle of counting is that it is additive on disjoint sets. Now count the number of cells that are occupied by your strings.

0

So, I will only cover here how to solve this for the inductive step, as the other is rather easy (not that the inductive step one isn't!).

Considering a string $x'=\lambda x$ we have

$\begin{align} |x'y| &= |x'|+|y| \\ |\lambda xy| &= |\lambda x| + |y| \\ |\lambda z| &= 1 + |x| + |y| \\ 1 + |z| &= 1 + |x| + |y| \\ 1+|xy| &= 1 + |xy| \end{align}$

  • 4
    OK (but next time you could spare us this *us noobs* thing). As I said, *A proof by induction begins with stating precisely an induction hypothesis $H_n$*, so what is your $H_n$? Hint: the answer is in my first comment to your post.2011-02-23