🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

本文提出了一种全新的、初等的且在计算上有效的构造方法，该方法通过利用函数完备性并将特定的析取转化为存在量化，将有限定义域上的高阶关系分解为二元关系，从而为皮尔斯的还原论（Peirce's reduction thesis）提供了统一证明，并证明了任何谢费尔函数（Sheffer function）的图都能复合所有此类关系。

原作者： Sergiy Koshkin

发布于 2026-06-19

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Sergiy Koshkin

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你有一本关于一台机器的巨大且复杂的说明书。这本手册描述了如何进行需要许多双手同时协作的操作（比如一个 5 人的舞蹈动作）。这篇论文提出了一个简单的问题：我们能否将这种复杂的、多人的指令，分解为一系列简单的、两人的指令？

作者 Sergiy Koshkin 说：“是的，我们可以，”但根据机器运行所在的“领域”（即房间的大小），情况会有一些有趣的转折。

以下是使用日常类比对这篇论文进行的拆解：

1. 核心思想：拆解复杂性

把一个复杂的逻辑关系（比如“A 是 B 的兄弟，而 B 是 C 的父母”）想象成一个巨大的、缠绕在一起的结。这篇论文的研究重点就是如何将这个结解开，变成一个个更小、更简单的环。

在数学和计算机科学中，我们经常处理“关系”（连接事物的规则）：

一元关系 (Unary)： 一个事物（例如：“是红色的”）。
二元关系 (Binary)： 两个事物（例如：“比……高”）。
三元关系 (Ternary)： 三个事物（例如：“在……之间”）。
N 元关系 (N-ary)： 许多个事物。

目标是将一个需要 5 个人才能理解的规则，转化为可以通过串联起只需要 2 或 3 个人就能理解的规则来构建的过程。

2. 无限大的房间 vs. 有限的房间

论文区分了两类世界：

无限世界： 想象一个拥有无限多人的房间。在这里，你可以玩一个叫做**“假设抽象 (Hypostatic Abstraction)”**的魔术。这就像是把一个复杂的 5 人舞蹈变成说：“让我们把这整个群体看作是一个新的个体。”你可以瞬间把任何复杂的规则变成一个简单的两人规则。这很容易，但它需要无限供应的“新的人”来充当占位符。
有限世界： 这是我们的现实世界，人数是有限的。你不能凭空创造出新的“人”来帮忙。这正是论文大显身手的地方。作者证明了即使在一个拥挤的小房间里，你仍然可以拆解复杂的规则，但你需要一种特定的、巧妙的构造方法。

3. 主要技巧：将规则转化为“函数”

作者的秘密武器是一个叫做**“亲属关系 (Relatives)”**的概念。
通常，“函数”就像一台自动售货机：你投入一枚硬币（输入），得到一份零食（输出）。这是一条单行道。
而“关系”更像是一个群聊：每个人都相互连接，但没有人是严格意义上的“老板”或“输出”。

类比：
想象你有一个大家都在说话的群聊。为了简化它，作者说：“让我们假装其中的一个人是‘老板’（输出），而其他人只是在向他发送消息。”
通过假装这个关系是一个“偏函数”（一个有时不回消息的老板），作者可以利用已有的成熟函数拆解技巧。

过程：

确定老板： 在你的复杂规则中选定一个变量作为“输出”。
选择器 (The Selector)： 如果规则允许有多个可能的输出（比如老板可能会发短信，也可能会发电子邮件），作者会使用一个“选择器”来挑选一条特定的路径。
链条： 一旦你拥有了函数，你就可以拆解它。就像你可以用简单的齿轮组装一台复杂的机器一样，你可以用简单的双输入齿轮（接收两个输入并产生一个输出的函数）来构建任何复杂的函数。
结果： 这证明了任何复杂的规则都可以被拆解为三元关系（涉及 3 个事物的规则）。可以把它看作一种“中间人”规则：如果 A 对 B 做了 X，且 B 对 C 做了 Y，那么 A 就与 C 相连。

4. 最后一步：从 3 个人到 2 个人

论文又往前走了一步。我们能否将这些 3 人规则进一步拆解为 2 人规则？

在大型有限领域上（3 人及以上）： 可以！作者使用了一个巧妙的技巧，叫做**“析取存在量化 (Existentialization of Disjunctions)”**。
- 隐喻： 假设你有一条规则说：“如果你戴着帽子、围巾或手套，就可以进入。”
- 在一个小房间里，你很难把“或者 (OR)”这种逻辑转化为简单的链条。但作者展示了，如果你有足够多的人（至少 3 个），你可以把这个“或者”列表转化为一个“谁拿着票？”的问题。你引入一个临时变量（“持票人”），然后询问：“是否有人拿着一张能让规则成立的票？”
- 这将复杂的“或”逻辑转换成了简单的“存在 (Exists)”逻辑，从而允许通过 3 人规则来构建完全由 2 人规则组成的系统。
在小型有限领域上（布尔集/2 个人）： 不行。
- 如果你只有两个人（比如“真/假”或“0/1”），你会撞上一堵墙。存在某些 3 人规则，它们根本无法被拆解为 -2 人规则。
- 隐喻： 这就像试图只用 2D 的平面碎片去搭建一个特定的 3D 立体形状。有些形状就是拼不出来。论文证明了在 2 人世界中，某些复杂的相互关系是“不可约简的”——它们是无法进一步简化的原子构建块。

5. “谢弗 (Sheffer)” 的惊喜

论文还发现了一些很酷的东西：正如逻辑学中存在一个单一的“魔力开关”（谢弗逻辑门，Sheffer stroke）可以构建任何其他逻辑门一样，在有限领域上也存在一个单一的**“谢弗关系 (Sheffer Relation)”**（一种特定的 3 人规则），它可以构建任何其他关系。

这就像是发现了一块特定的乐高积木，只要你有足够的这种积木，你就可以建造任何城堡、汽车或宇宙飞船。

总结“要点”

复杂性是可控的： 你可以把几乎任何涉及许多变量的复杂规则，拆解成仅涉及 2 个或 3 个变量的简单规则。
“中间人”是三元的： 最有效率的拆解方式通常止步于 3 个变量（三元关系）。
规模至关重要： 如果你的世界足够大（3 个或更多项目），你可以把一切都拆解为 2 个变量。如果你的世界非常微小（只有 2 个项目），那么某些 3 变量规则就会卡在那里，无法被简化。
函数有助于关系： 通过把关系假装成函数（有一个老板和若干工人），我们可以利用现有的数学工具来解决关系问题。

这篇论文本质上提供了一份全新的、更简单的“说明书”，指导我们如何解构复杂的数据关系，并证明了即使在有限的世界里，只要拥有一些特定的“辅助”规则，我们也能利用简单的两人交互来构建任何事物。

技术摘要：有限定义域上关系的函数完备性与原初正向分解

问题陈述
本文研究了如何使用原初正向公式（primitive positive formulas, ppfs）将高阶关系分解为低阶关系（特别是二元关系）。原初正向公式由谓词的合取与存在量词组成。这一问题被称为“关系还原论”（Relational Reduction Thesis, RRT），其核心假设是： $n$ 元关系（ $n \ge 2$ ）可以还原为二元关系，但并非所有二元关系都能还原为一元关系。

虽然其函数对应物——函数还原论（Functional Reduction Thesis, FRT）——已得到充分证实（通过 Post 对多值逻辑中 Sheffer 函数的研究），但在有限定义域上的关系情况则尚不明确。以往的研究往往是零散的、非构造性的，或者依赖于扩展定义域（假设抽象/hypostatic abstraction），而后者在不增加新元素的情况下在有限定义域上是不可行的。此外，已知 RRT 在布尔定义域上失效（存在不可约的三元关系），但其失效的结构性原因以及在一般有限定义域上成功的条件，需要一个统一且基础的解释。

方法论
作者采用了一种构造性方法，通过将关系解释为“多值部分定义函数”（即“相对值/relatives”），从而架起了函数完备性与关系分解之间的桥梁。该方法分三个阶段进行：

相对还原（关系到三元）：
本文将 $n$ 元关系 $R$ 处理为一个带有特定输出参数的相对值。它将 $R$ 分解为一个多值函数和一个定义域关系。通过利用值选择器（选取多值函数像中的值的函数），作者将多值函数还原为普通函数 $f(t, x_1, \dots, x_{n-1})$ 。利用已知的 $n$ 输入函数向 2 输入函数的函数还原（通过 Post 在多值逻辑中的规范析取范式），本文证明了任何关系都可以分解为三元关系（2 输入函数的图）及更低阶的关系。
析取项的存在量化（三元到二元）：
为了将三元关系还原为二元关系，本文引入了一种针对“余有限”（cofinite）关系的构造（即补集为有限的关系）。该方法是假设抽象的对偶过程。它不是通过引入新元素来编码元组，而是将余有限关系在补全合取范式（CCNF）中蕴含的析取转化为存在量化。这是通过引入一个索引变量并定义特定的二元谓词来实现的，这些谓词模拟了一元“共文字”（coliterals）的析取。这一步骤仅在阶数 $n$ 不超过定义域大小 $|D|$ 时有效，因为这允许将索引注入到定义域中。
键还原（Bond Reduction）与皮尔士论题：
本文分析了原初正向复合与皮尔士最初的“键结合”（bond，涉及相对积和变量识别的受限复合）之间的关系。证明了对于 $n \ge 4$ ，pp-可约性与键可约性是等价的，前提是允许使用三元“三恒等式”（teridentities, $I_3$ ）。然而，对于三元关系，键可约性严格弱于 pp-可约性。

主要贡献与结果

定理 2（相对还原）： 在任何定义域上，任何 $n$ 元关系都可以分解为一个函数 $f: D^n \to D$ 与一个定义域关系的复合。至关重要的是，如果存在一组函数完备的 2 输入函数集，那么每个关系都可以分解为该集合中函数的图。这意味着在任何有限定义域上，任何 $n$ 元关系（ $n \ge 4$ ）都可以还原为三元关系。
推论 1（Sheffer 关系）： 在任何有限定义域上，都存在三元关系（Sheffer 函数的图），它们本身构成一个原初正向完备系统。这确立了非布尔定义域上“Sheffer 关系”的存在性。
定理 3（余有限关系的二元还原）： 对于 $|D| \ge 3$ 的定义域，任何余有限 $n$ 元关系（其中 $3 \le n \le |D|$ ）都可以还原为二元关系。该构造依赖于将共文字的析取转化为二元谓词上的存在量化。
定理 4（布尔定义域上的不可约性）： 本文提供了一个关于三元关系 $\neg I_3$ （三元恒等关系的补）在布尔定义域上是不可约至二元关系的初等证明。证明过程显示 $\neg I_3$ 不是“双变性”（bijunctive，即不能表示为 2CNF）的，由于 pp-复合保持双变性，因此它无法还原为二元关系（二元关系均为双变性）。
定理 5 与 6（键可约性 vs. pp-可约性）： 本文澄清了对于 $n \ge 4$ ，pp-可约性与使用三恒等式的键可约性是等价的。然而，对于三元关系，键可约性严格较弱；具体而言， $I_3$ 在任何至少包含两个元素的定义域上都是键不可约的。

意义与主张
本文声称通过建立函数还原论（FRT）与关系还原论（RRT）之间直接且基础的联系，为皮尔士的还原论在有限定义域上的证明提供了“统一证明”。

统一性： 它通过展示函数完备系统的图构成了关系上的 pp-完备系统，解决了函数完备性与关系完备性之间的脱节。
构造性： 不同于以往依赖于伽罗瓦连接或定义域扩展的非构造性证明，本构造是计算有效的，并依赖于成熟的函数分解方法（Post 逻辑）。
失效解释： 该构造阐明了 RRT 为何在布尔定义域上失效：即由于定义域元素不足（当 $n > |D|$ 时无法进行索引注入），导致无法将高阶析取转化为存在量化。
新概念： 引入了“Sheffer 关系”的概念，并为“假设抽象”提供了一个新的视角，将其视为“析取存在量化”的对偶过程。

作者谦虚地指出，虽然该构造解释了关系向三元（以及针对余有限情况下的向二元）的还原，但并未提供在任意有限定义域上关系完备性的通用 Post 或 Slupecki 标准的类似物，也未能完全刻画极大 coclone。关于非布尔定义域上是否存在二元 Sheffer 关系的问题，本文留待后续研究。