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}
}