Lawvere定理

Lawvere不动点定理（也称为Lawvere对角线定理，1969年提出）是采用范畴论语言，统一刻画对角线自指与不动点现象的基础定理，是对Kleene第二递归定理的进一步提炼与抽象。

函数版本的Lawvere定理

然而，由于原始版本的Lawvere定理是构建在范畴论基础之上的，而对于不熟悉此数学语言的读者来说，该定理显得非常晦涩难懂。因此，本词条首先介绍一个简化后的函数版本的Lawvere定理，然后再介绍原始的范畴论版本。该函数版本的定理是在2003年Yanofsky给出的，该定理可陈述如下。

Lawvere定理（函数简化版本） 设 [math]\displaystyle{ T }[/math] 是一个集合。若存在集合 [math]\displaystyle{ Y }[/math] 以及函数 [math]\displaystyle{ f:Y\times Y \to T }[/math]，使得所有函数 [math]\displaystyle{ g:Y \to T }[/math] 都可以由 [math]\displaystyle{ f }[/math] 表示——即对每个这样的函数 [math]\displaystyle{ g }[/math]，都存在元素 [math]\displaystyle{ y \in Y }[/math]，使得对任意自变量都有 [math]\displaystyle{ g(x) = f(y,x) }[/math]——则对任意函数 [math]\displaystyle{ \alpha : T \to T }[/math]，都存在 [math]\displaystyle{ t \in T }[/math] 满足 [math]\displaystyle{ \alpha(t) = t }[/math]，也就是 [math]\displaystyle{ \alpha }[/math] 必有不动点。

定理中各个函数的关系可以用下面的交换图来表示：

lawvere定理的函数版本

证明：

我们按如下方式构造函数 [math]\displaystyle{ g }[/math]：

[math]\displaystyle{ g(m) = \alpha(f(m,m)) }[/math]

根据题设，[math]\displaystyle{ g }[/math] 可由某个 [math]\displaystyle{ y \in Y }[/math] 表示，因此有：

[math]\displaystyle{ g(m) = f(y,m) }[/math]

于是 [math]\displaystyle{ \alpha }[/math] 在 [math]\displaystyle{ t_0 = g(y) }[/math] 处取得不动点，具体推导为：

[math]\displaystyle{ \alpha(g(y)) = \alpha(f(y,y)) = g(y) }[/math]

取[math]\displaystyle{ t=g(y) }[/math]即得到不动点。

范畴论版本的Lawvere定理

下面正式介绍Lawvere定理的范畴论版本，该定理表明只要一个笛卡尔闭范畴中存在对函数族的通用编码机制，那么输出对象上的所有自变换都必然存在不动点。

Lawvere定理（范畴论版本）：设 [math]\displaystyle{ \mathcal{C} }[/math] 为任意笛卡尔闭范畴（Cartesian closed category, CCC），[math]\displaystyle{ A }[/math] 和 [math]\displaystyle{ Y }[/math] 是 [math]\displaystyle{ \mathcal{C} }[/math] 中的任意对象。 如果存在弱点满射态射:

[math]\displaystyle{ f : A \to Y^A }[/math]

（即对每一个态射 [math]\displaystyle{ g : A \to Y }[/math]，都存在点 [math]\displaystyle{ x : 1 \to A }[/math]，使得 [math]\displaystyle{ x }[/math] 与 [math]\displaystyle{ f }[/math] 的复合恰好是 [math]\displaystyle{ g }[/math] 对应的指数对象点 [math]\displaystyle{ \ulcorner g \urcorner : 1 \to Y^A }[/math]，这里[math]\displaystyle{ Y^A }[/math]为指数对象，包含了所有从[math]\displaystyle{ A }[/math]到[math]\displaystyle{ Y }[/math]的态射），则对象 [math]\displaystyle{ Y }[/math] 具有不动点性质：对任意自态射 [math]\displaystyle{ \alpha : Y \to Y }[/math]，都存在点 [math]\displaystyle{ t : 1 \to Y }[/math]，满足:

[math]\displaystyle{ \alpha(t) = t }[/math]

其逆否命题等价于：若 [math]\displaystyle{ Y }[/math] 上存在没有不动点的自态射，则不存在从 [math]\displaystyle{ A }[/math] 到 [math]\displaystyle{ Y^A }[/math] 的弱点满射。

• 直观解释：笛卡尔闭范畴的核心特征是函数空间本身可以作为范畴内的对象被处理，这使得“用论域元素给函数编码”的自指结构可以被形式化。定理的核心洞察是：只要论域 [math]\displaystyle{ A }[/math] 足以编码所有从 [math]\displaystyle{ A }[/math] 到 [math]\displaystyle{ Y }[/math] 的函数，那么 [math]\displaystyle{ Y }[/math] 上的任何全局变换都无法避免不动点。这种结构是跨领域通用的：可计算性理论、数理逻辑、集合论中的所有经典对角线结果，都是这一抽象定理的具体实例。

证明

在笛卡尔闭范畴中，以下结构是公理保证天然存在的：

1. 对角态射：对任意对象 [math]\displaystyle{ A }[/math]，存在对角态射 [math]\displaystyle{ \delta_A : A \to A \times A }[/math]，满足对任意点 [math]\displaystyle{ a:1\to A }[/math]，有 [math]\displaystyle{ a \cdot \delta_A = \langle a, a \rangle }[/math]，作用是将输入复制为完全相同的两份。
2. 指数对象与求值态射：对任意对象 [math]\displaystyle{ A,Y }[/math]，存在指数对象 [math]\displaystyle{ Y^A }[/math]（范畴内部的函数空间）和求值态射 [math]\displaystyle{ \epsilon_A : A \times Y^A \to Y }[/math]，实现范畴内部的“函数调用求值”。
3. 柯里化同构：存在自然双射

   [math]\displaystyle{ \mathcal{C}(A \times X, Y) \cong \mathcal{C}(X, Y^A) }[/math]

   即二元态射与“返回函数的一元态射”一一对应。从右向左的逆变换称为逆柯里化（逆[math]\displaystyle{ \lambda }[/math]变换）。

4. 弱点满射：态射 [math]\displaystyle{ f : A \to Y^A }[/math] 称为弱点满射，当且仅当：对任意一元态射 [math]\displaystyle{ g : A \to Y }[/math]，都存在点 [math]\displaystyle{ y : 1 \to A }[/math]，使得对所有点 [math]\displaystyle{ a : 1 \to A }[/math]，都有

   [math]\displaystyle{ \bar{f}(\langle a, y \rangle) = f(a) }[/math]

   其中 [math]\displaystyle{ \bar{f} : A\times A \to Y }[/math] 是 [math]\displaystyle{ g }[/math] 的逆柯里化。

   直观含义：所有从 [math]\displaystyle{ A }[/math] 到 [math]\displaystyle{ Y }[/math] 的一元函数，都可以被 [math]\displaystyle{ A }[/math] 中的某个点 [math]\displaystyle{ y }[/math] 通过通用二元函数 [math]\displaystyle{ \bar{f} }[/math] 表示。

详细证明：

任取 [math]\displaystyle{ Y }[/math] 上的自态射 [math]\displaystyle{ t : Y \to Y }[/math]，我们通过构造得到它的不动点，步骤如下：

• 步骤1：逆柯里化得到通用二元态射

  根据指数伴随的柯里化同构，态射 [math]\displaystyle{ f : A \to Y^A }[/math] 唯一对应一个二元态射 [math]\displaystyle{ \bar{f} : A \times A \to Y }[/math]（称为 [math]\displaystyle{ f }[/math] 的逆柯里化），满足：

  [math]\displaystyle{ \bar{f} = (A \times f) \cdot \epsilon_A }[/math]

  其中 [math]\displaystyle{ A \times f }[/math] 是积函子作用在态射 [math]\displaystyle{ f }[/math] 上的结果。

  直观上，[math]\displaystyle{ \bar{f} }[/math] 是范畴内部的“通用解释器”：第一个参数是输入值，第二个参数是函数的编码，输出函数作用在输入上的结果。

• 步骤2：构造对角线复合函数

  取对角态射 [math]\displaystyle{ \delta_A : A \to A \times A }[/math]，将其与 [math]\displaystyle{ \bar{f} }[/math]、[math]\displaystyle{ t }[/math] 依次复合，得到一元态射 [math]\displaystyle{ g : A \to Y }[/math]：

  [math]\displaystyle{ g = \delta_A \cdot \bar{f} \cdot \alpha }[/math]

  对任意点 [math]\displaystyle{ x : 1 \to A }[/math]，[math]\displaystyle{ g }[/math] 的作用可展开为：

  [math]\displaystyle{ g(x) = \alpha\left(\bar{f}(\langle x, x \rangle) \right) }[/math]

  其含义是：先将输入 [math]\displaystyle{ x }[/math] 复制一份，同时作为 [math]\displaystyle{ \bar{f} }[/math] 的两个参数代入（对角线操作），再将计算结果用 [math]\displaystyle{ \alpha }[/math] 做变换。这是整个证明的核心——抽象的对角线自指代入。

• 步骤3：应用弱点满射条件

  根据题设，[math]\displaystyle{ f }[/math] 是弱点满射。对上述构造的 [math]\displaystyle{ g : A \to Y }[/math]，必然存在某个点 [math]\displaystyle{ y : 1 \to A }[/math]，使得对所有点 [math]\displaystyle{ a : 1 \to A }[/math]，都有：

  [math]\displaystyle{ \bar{f}(\langle a, y \rangle) = g(a) }[/math]

  也就是说，[math]\displaystyle{ y }[/math] 就是函数 [math]\displaystyle{ g }[/math] 对应的“编码”。

• 步骤4：对角线代入导出不动点等式

  将上式中的任意点 [math]\displaystyle{ a }[/math] 替换为编码点 [math]\displaystyle{ y }[/math] 本身（即将编码代入自身的参数位，完成自指闭合），可得：

  [math]\displaystyle{ \bar{f}(\langle y, y \rangle) = f(y) }[/math]

• 将右侧的 [math]\displaystyle{ g }[/math] 按步骤2的定义展开，代入 [math]\displaystyle{ g(y) = \alpha\left(\bar{f}(\langle y, y \rangle) \right) }[/math]，得到：

  [math]\displaystyle{ \bar{f}(\langle y, y \rangle) = \alpha\left(\bar{f}(\langle y, y \rangle) \right) }[/math]

• 令 [math]\displaystyle{ t = \langle y, y \rangle \cdot \bar{f} }[/math]，这是 [math]\displaystyle{ Y }[/math] 的一个点，则上式可写为：

  [math]\displaystyle{ t = \alpha(t) }[/math]

• 步骤5：结论

  点 [math]\displaystyle{ z }[/math] 满足自态射 [math]\displaystyle{ t }[/math] 的不动点定义。由于 [math]\displaystyle{ t }[/math] 是任意选取的自态射，因此对象 [math]\displaystyle{ Y }[/math] 具有不动点性质。

证毕。