第3章 从公理到编码

3.1 非唯一编码的矛盾

命题 P3.1（编码唯一性的必然性）

在自指完备系统中，状态编码函数必须是单射：

$$\forall x,y\in S,x\ne y\Rightarrow \mathrm{Code}(x)\ne \mathrm{Code}(y)$$

严格证明（反证法）：

1. 假设：存在非单射编码，即 $\exists x\ne y$, $\mathrm{Code}(x)=\mathrm{Code}(y)=c$
2. 自指执行场景：考虑两次独立的自指执行：
   • 执行 $\alpha$ 记录状态 $x$：${\Sigma }_{t+1}^{\alpha }={\Sigma }_t\cup \{c\}$
   • 执行 $\beta$ 记录状态 $y$：${\Sigma }_{t+1}^{\beta }={\Sigma }_t\cup \{c\}$
3. 状态集合重合：${\Sigma }_{t+1}^{\alpha }={\Sigma }_{t+1}^{\beta }$
4. 熵保持不变：$|{\Sigma }_{t+1}^{\alpha }|=|{\Sigma }_{t+1}^{\beta }|=|{\Sigma }_t|$，因此 $H({\Sigma }_{t+1})=H({\Sigma }_t)$
5. 矛盾：这违反了公理 $A1$ (SRA) 的严格熵增要求

结论：为保证熵增，编码必须是严格单射（唯一性）。$\square$

3.2 合法编码的形式化定义

定义 D3.1（合法串集合）

对长度 $n$，定义合法串集合：

$$B_n=\{w\in \{0,1{\}}^n\mid w\text{ 不含子串 "11"}\}$$

递推构造：

• $B_0=\{\epsilon \}$ （空串）
• $B_1=\{0,1\}$
• 递推生成：

$$B_n=\{s0:s\in B_{n-1}\}\cup \{s10:s\in B_{n-2}\},n\ge 2$$

命题 P3.2（合法串的 Fibonacci 递推）

合法串的基数满足：

$$|B_n|=|B_{n-1}|+|B_{n-2}|$$

且初值 $|B_0|=1$, $|B_1|=2$，因此

$$|B_n|=F_{n+1}$$

证明：

• 若合法串长度为 n，则最后的可能情况：
  • 末尾为 0：前缀是 B_{n-1} 的任意合法串
  • 末尾为 10：前缀是 B_{n-2} 的任意合法串
• 两类不重叠，得递推式
• 由初值归纳可得 $|B_n|=F_{n+1}$ $\square$

3.3 Zeckendorf 表示的必然性

定义 D3.2（Zeckendorf 分解）

任意自然数 $N\in {\mathbb{N}}^{+}$，可以唯一写作若干不相邻 Fibonacci 数的和：

$$N=F_{i_1}+F_{i_2}+\cdots +F_{i_r},i_1>i_2>\cdots >i_r\ge 1,i_j-i_{j+1}\ge 2$$

其中 Fibonacci 数列定义为： $$F_1=1,F_2=2,F_{n+2}=F_{n+1}+F_n(n\ge 1)$$

黄金比例：$\phi =(1+\sqrt{5})/2\approx 1.618$，满足${\phi }^2=\phi +1$，与Fibonacci数渐近相关。

Zeckendorf编码 $Z(N)$：长度足够的二进制串，第 $i_j$ 位为1，其余为0。

关键性质：此编码天然满足“禁11“约束（不相邻条件保证）。

定理 T3.3（Zeckendorf 唯一性定理）

自然数与合法串之间存在双射：

$${\mathbb{N}}^{+}⟷\bigcup _{n\ge 1}{B}_n$$

严格证明：

第一步：映射的良定义性

1. 贪心算法的正确性：

   • 对任意 N>0，设 F_k 是不超过 N 的最大Fibonacci数
   • 剩余值 r = N - F_k 满足：0 ≤ r < F_k
   • 由Fibonacci性质：F_k > F_{k-1}，因此若继续分解r，不会再用到F_k或F_{k-1}
   • 递归应用至r=0，得到分解 N = F_{i₁} + ⋯ + F_{iₘ}，且 i₁ > i₂ > ⋯ > iₘ，相邻索引差≥2

2. 禁11性质：由分解的不相邻性直接保证编码中无连续“11“

第二步：唯一性（严格证明）

• 关键引理：$F_k\ge F_{k-2}+F_{k-3}+\cdots +F_1$（$k\ge 3$时），且差值恒为2
• 证明引理：归纳法，由$F_{k+2}=F_{k+1}+F_k$及初始条件可得$F_k=F_{k-2}+F_{k-3}+\cdots +F_1+2$
• 主证明：假设存在两种不同的分解，设最大索引分别为 $k_1,k_2$且$k_1>k_2$
  • 第一种包含$F_{k_1}$，第二种的最大项为$F_{k_2}$
  • 第二种分解的最大可能和为：F_{k₂} + F_{k₂-2} + F_{k₂-4} + ⋯（最大非连续和）
  • 由引理，F_{k₁} ≥ F_{k₁-2} + F_{k₁-3} + ⋯ + F_1，且F_{k₁} > F_{k₂}
  • 而F_{k₁} ≥ F_{k₂} + F_{k₂-2} + ⋯（F_{k₁}超过第二种分解的最大可能值）
  • 矛盾！因此分解唯一

第三步：满射性

• 任意合法串w∈B_n对应唯一自然数：∑{i: w[i]=1} F_i
• 由Fibonacci数的严格递增性，不同合法串对应不同自然数

理论补充：上述证明得到φ-语言编码理论和完整构造性证明的深层支撑。φ-语言编码理论证明了φ-语言作为禁11约束下的唯一最优编码系统，而完整构造性证明提供了更严格的构造性证明，确保Zeckendorf表示不是偶然，而是φ-结构在数论中的必然表现。

结论：$Z$ 是严格双射。$\square$

3.4 严格验证：前几个自然数的 Zeckendorf 编码

Fibonacci数列：$F_1=1,F_2=2,F_3=3,F_4=5,F_5=8,F_6=13,\dots$

关键观察：任何包含相邻Fibonacci数的“分解“都会产生连续“11“，因此被禁11约束自动排除。

3.5 小结

在本章中，我们从唯一公理A1（自指完备系统必然熵增, SRA）推出：

1. 编码必须唯一，否则可能出现自指执行不增熵
2. 唯一合法的编码 = 禁止连续“11“的二进制串
3. 每个自然数与一个合法串一一对应（Zeckendorf 双射）

由此，建立了：

$${\mathbb{N}}^{+}⟷\bigcup _{n\ge 1}{B}_n⟷\{\text{Hilbert 空间基态}\}$$

这不是巧合，而是$\phi$编码系统在我们内部的自然显现。禁11约束就是宇宙保持动态流动的内在几何。