一句话：研究 Tarski 关系代数若干语义片段的有限生成性，证明同态安全片段可有限生成，而函数保持等片段不可。
本文研究 Tarski 二元关系代数中若干由语义性质定义的片段，特别是函数保持片段，考察它们是否可由有限操作集生成。作者分析同态安全、函数保持、全函数保持、前向函数保持及前后向单射函数保持等片段，并借助 guarded second-order 可定义性给出正反结果。主要结论是：同态安全片段在有限和任意结构上均可有限生成；函数保持片段与全函数保持片段均不可有限生成，且不能由有限个 guarded second-order 可定义的相应操作表示；前向函数保持片段可由复合、交、反定义域和 preferential union 有限生成；前后向单射函数保持片段可由复合、交、反定义域、逆和单射并有限生成。
We investigate a number of semantically defined fragments of Tarski's algebra of binary relations, including the function-preserving fragment. We address the question whether they are generated by a finite set of operations. We obtain several positive and negative results along these lines. Specifically, the homomorphism-safe fragment is finitely generated (both over finite and over arbitrary structures). The function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable function-preserving operations). Similarly, the total-function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable total-function-preserving operations). In contrast, the forward-looking function-preserving fragment is finitely generated by composition, intersection, antidomain, and preferential union. Similarly, the forward-and-backward-looking injective-function-preserving fragment is finitely generated by composition, intersection, antidomain, inverse, and an `injective union' operation.
@article{paperbot2729,
title = {Preservation theorems for Tarski's relation algebra},
author = {Bart Bogaerts and Balder ten Cate and Brett McLean and Jan Van den Bussche},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 3},
year = {2024},
doi = {10.46298/lmcs-20(3:20)2024}
}