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

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

• Is it necessary to use induction, or are other proof methods allowable? – Luke Mathieson Feb 2 at 12:29
• others are welcome as well – 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.