paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Constraint satisfaction problems, compactness and non-measurable sets

约束满足问题、紧致性与不可测集
LMCS vol.Volume 22, Issue 32026匹配度 0/10 · 该论文属于数理逻辑、集合论与约束满足问题的元数学研究，讨论紧致性在 ZF 中的可证明性及其与不可测集的关系，与用户关注的 PL/AI、静态分析、Agent、浮点程序分析、贝叶斯程序分析及 LLM 交叉方向没有交集。引用 2 inbox
Claude Tardif
逻辑与自动机逻辑与约束编程
crossref: 2026-09-10

AI 速览

一句话：证明宽度为一的有限关系结构在 ZF 中紧致，否则其紧致性蕴含 3 维空间存在不可测集。

论文研究有限关系结构 A 的紧致性：若对任意同类型无限关系结构 B，B 到 A 的同态存在当且仅当其所有有限子结构到 A 的同态存在，则称 A 紧致。作者考察这一性质在集合论公理系统中的强度。结果表明，当 A 的宽度为一（width one）时，其紧致性可在 Zermelo-Fraenkel 公理系统 ZF 中证明；而对其他结构，A 的紧致性会蕴含 3 维空间中不可测集的存在。该结果将约束满足问题的紧致性与选择公理、不可测集等集合论现象联系起来，揭示了宽度条件对逻辑强度的决定性作用。

问题
研究有限关系结构 A 的紧致性——即无限 B 到 A 的同态存在性是否等价于其所有有限子结构到 A 的同态存在性——在 Zermelo-Fraenkel 公理系统中的可证明性与逻辑强度。
方法
按结构的宽度分类，在 ZF 内分析宽度为一情形的紧致性证明，并考察非宽度为一情形的紧致性所蕴含的集合论后果。
评估
以 ZF 中的可证明性和蕴含关系作为评估标准，证明宽度为一结构的紧致性可在 ZF 中证明，而其余结构的紧致性蕴含 3 维不可测集存在。
原文摘要（Abstract）

A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A. We show that if A has width one, then the compactness of A can be proved in the axiom system of Zermelo and Fraenkel, but otherwise, the compactness of A implies the existence of non-measurable sets in 3-space.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@article{abs-2508-14838,
  title = {Constraint satisfaction problems, compactness and non-measurable sets},
  author = {Claude Tardif},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 3},
  year = {2026},
  doi = {10.46298/lmcs-22(3:1)2026}
}