paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Fixed Points Theorems for Non-Transitive Relations

非传递关系的不动点定理
LMCS vol.Volume 18, Issue 12022匹配度 2/10 · 该论文在 Isabelle/HOL 中形式化序论不动点定理,属于定理证明与形式化验证的基础理论工作,但未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,也不属于用户关注的 AI 与 PL 交叉方向。引用 0 inbox
Jérémy Dubut, Akihisa Yamada
crossref: 2026-09-10

AI 速览

一句话:在 Isabelle/HOL 中形式化序论不动点定理,将完备序结果推广到仅需反对称性或吸引性的非传递关系。

论文针对经典序论不动点定理通常依赖传递性(或偏序)的局限,在 Isabelle/HOL 中建立一套尽可能一般的序论不动点定理库。作者以完备关系为框架,仅假设反对称性或吸引性——一种由二者之一蕴含的温和条件——重新证明若干关于完备序的著名结果。核心贡献是将保证单调映射存在拟不动点的系列定理推广到非传递关系,并证明(拟)不动点集合自身也是完备的。该工作统一并加强了 Knaster-Tarski、Bourbaki-Witt、Kleene、Markowsky、Pataraia、Mashburn、Bhatta-George 及 Stouti-Maaden 等定理,所有结果均在 Isabelle/HOL 中机器验证。

问题
经典不动点定理多依赖传递性或偏序假设,限制其在非传递关系上的适用;本文旨在厘清并弱化这些假设。
方法
在 Isabelle/HOL 中开发序论不动点定理库,以完备关系为统一框架,仅用反对称性或吸引性等温和条件重述并证明相关结果。
评估
通过机器化证明在 Isabelle/HOL 中验证全部定理,并展示其推广和加强 Knaster-Tarski、Bourbaki-Witt、Kleene、Markowsky、Pataraia、Mashburn、Bhatta-George、Stouti-Maaden 等已有结果。
原文摘要(Abstract)

In this paper, we develop an Isabelle/HOL library of order-theoretic fixed-point theorems. We keep our formalization as general as possible: we reprove several well-known results about complete orders, often with only antisymmetry or attractivity, a mild condition implied by either antisymmetry or transitivity. In particular, we generalize various theorems ensuring the existence of a quasi-fixed point of monotone maps over complete relations, and show that the set of (quasi-)fixed points is itself complete. This result generalizes and strengthens theorems of Knaster-Tarski, Bourbaki-Witt, Kleene, Markowsky, Pataraia, Mashburn, Bhatta-George, and Stouti-Maaden.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1725,
  title = {Fixed Points Theorems for Non-Transitive Relations},
  author = {Jérémy Dubut and Akihisa Yamada},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 1},
  year = {2022},
  doi = {10.46298/lmcs-18(1:30)2022}
}