关于ε∈L1时L2⊆L2•L1的反证法证明合理性问询

问题背景 #

设L₁、L₂为语言，且L₂非空。需要证明：若空串ε属于L₁，则L₂是L₂•L₁的子集。现有如下反证法证明：

假设L₂⊈L₂•L₁，那么L₁中包含非空串，否则我们可以将ε与L₂中的每个串连接，由此推出ε∉L₁，与前提矛盾。

证明合理性分析 #

这个证明不合理，核心问题是逻辑链条混乱且错误：

• 反证的正确起点是：假设L₂⊈L₂•L₁，即存在某个串x ∈ L₂，但x ∉ L₂•L₁。
• 根据语言连接的定义，L₂•L₁ = { yz | y∈L₂, z∈L₁ }。已知ε ∈ L₁，那么对任意x ∈ L₂，都有x = x•ε——这里x∈L₂、ε∈L₁，所以x必然属于L₂•L₁，这直接和假设的x ∉ L₂•L₁矛盾，反证即可成立。
• 原证明中的逻辑完全偏离了正确路径：它提到“L₁中包含非空串，否则推出ε∉L₁”，这部分因果倒置且毫无依据。当L₁不包含非空串（即L₁={ε}）时，恰恰是可以通过x=x•ε推出x∈L₂•L₁，和假设矛盾，根本推不出ε∉L₁的结论。

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