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 ∈ ℕ. |Σⁿ| = |Σ|ⁿ?

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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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