求证非空有限语言L与正自然数k满足|Lᵏ|=|L|ᵏ

这是个基础但核心的形式语言基数问题，我来帮你把思路落地成严谨的证明：

先明确符号与前置定义 #

避免歧义，先把关键符号说清楚：

• 设L是非空有限语言，记它的基数为 $n = |L|$，也就是L包含n个不同的字符串：$L = {s_1, s_2, ..., s_n}$
• $L^k$ 是L的k次连接：所有形如 $s_{i_1}s_{i_2}...s_{i_k}$ 的字符串集合，其中每个 $s_{i_j} \in L$
• $|L|^k = n^k$，这里是自然数n的k次幂，本质等价于所有长度为k的索引元组的个数：${(i_1, i_2, ..., i_k) \mid 1 \leq i_j \leq n, j=1..k}$

按你的思路构造双射证明 #

你的方向完全正确，核心就是通过双射建立两个集合的一一对应，从而证明基数相等：

1. 定义索引元组集合B
   令 $B = {(i_1, i_2, ..., i_k) \mid 1 \leq i_j \leq n, j=1,2,...,k}$，根据自然数幂的定义，显然 $|B| = n^k = |L|^k$。

2. 构造映射 $h: B \to L^k$
   对任意元组 $(i_1, i_2, ..., i_k) \in B$，定义：

   h((i_1, i_2, ..., i_k)) = s_{i_1}s_{i_2}...s_{i_k}
   

   简单说就是把元组里的每个索引，对应到L中的字符串，再按顺序拼接起来。

3. 证明h是单射（Injective）
   假设存在两个不同的元组 $(i_1,...,i_k) \neq (j_1,...,j_k)$，那至少有一个位置 $t$（$1≤t≤k$）满足 $i_t \neq j_t$。
   因为L里的字符串都是唯一的，所以 $s_{i_t} \neq s_{j_t}$。那么拼接后的字符串：

   • $h((i_1,...,i_k)) = s_{i_1}...s_{i_t}...s_{i_k}$
   • $h((j_1,...,j_k)) = s_{j_1}...s_{j_t}...s_{j_k}$
     由于第t个位置的子串不同，拼接后的整体字符串必然不同，因此h是单射。

4. 证明h是满射（Surjective）
   任取任意字符串 $w \in L^k$，根据 $L^k$ 的定义，w一定能拆成 $w = t_1t_2...t_k$，其中每个 $t_m \in L$。
   因为L是有限集，每个 $t_m$ 都对应L中的某个索引 $i_m$（也就是 $t_m = s_{i_m}$），所以元组 $(i_1,...,i_k) \in B$，且 $h((i_1,...,i_k)) = w$。这说明h是满射。

最终结论 #

因为h是从B到 $L^k$ 的双射，而 $|B|=|L|^k$，根据双射的定义，两个集合的基数必然相等，因此：
$$|L^k| = |L|^k$$

内容的提问来源于stack exchange，提问作者Raton