1
$\begingroup$

I am currently working on ways to prove this and got stuck proving it with induction.

Any tips?

How could i prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ?

$\endgroup$
2
  • $\begingroup$ Is it necessary to use induction, or are other proof methods allowable? $\endgroup$ Feb 2, 2020 at 12:29
  • $\begingroup$ others are welcome as well $\endgroup$
    – user128226
    Feb 2, 2020 at 13:53

1 Answer 1

0
$\begingroup$

One way would be to show an isomorphism between strings and ordered sets, then the result is a direct consequence of properties of set cardinalities (namely that $|A \times B| = |A|\cdot|B|$ for any two sets $A$ and $B$).

Let's assume that you don't want to do that (for a start it's probably more work to do it properly - but very quick to do it in a hand-waving manner).

The first step is that we need to show that for a set of string $S$ and an alphabet $\Sigma$, $|S\circ \Sigma| = |S|\cdot|\Sigma|$, where $\circ$ is the concatenation operator (overloaded for sets as well as strings). This is not hard of course: each string $s \in S$ and each $\sigma \in \Sigma$, the string $s \circ \sigma$ is in $S \circ \Sigma$ and this string is different for every choice of $s$ and $\sigma$.

Next we can inductively show that $|\Sigma^{n}| = |\Sigma|^{n}$.

Base Case:

$\Sigma^{0}$ is the set of strings obtained by concatenating elements of $\Sigma$ $0$ times, i.e., just the empty string $\varepsilon$ (or $\lambda$ if you're that way inclined :D). So $|\Sigma^{0}| = 1$. Of course $\alpha^{0} = 1$ for any $\alpha \in \mathbb{N}$, so $|\Sigma^{0}| = 1 = |\Sigma|^{0}$.

Inductive Hypothesis

Assume that $|\Sigma^{k}| = |\Sigma|^{k}$.

Inductive Step

$\Sigma^{k+1} \ = \Sigma^{k}\circ\Sigma$, therefore $|\Sigma^{k+1}| = |\Sigma^{k}\circ\Sigma|$, which we have established is $|\Sigma^{k}|\cdot|\Sigma|$, by the inductive hypothesis (and power laws) $|\Sigma^{k}|\cdot|\Sigma| = |\Sigma|^{k}\cdot|\Sigma| = |\Sigma|^{k+1}$, which is what we wanted to show.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.