Composition Theorem for Generalized Sum

Article type: Research Article

Authors: Rabinovich, Alexander

Affiliations: School of of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Israel. E-mail: rabinoa@post.tau.ac.il

Abstract: Composition theorems are tools which reduce sentences about some compound structure to sentences about its parts. A seminal example of such a theorem is the Feferman-Vaught Theorem [3] which reduces the first-order theory of generalized products to the first order theory of its factors and the monadic second-order theory of index structure. Shelah [23] used the composition theorem for linear orders as one of the main tools for obtaining very strong decidability results for the monadic second-order theory of linear orders. The main technical contribution of our paper is (1) a definition of a generalized sum of structures and (2) a composition theorem for first-order logic over the generalized sum. One of our objectives is to emphasize the work-out of the composition method.

Keywords: Composition Theorem, first-order logic, expressibility, decidability

Journal: Fundamenta Informaticae, vol. 79, no. 1-2, pp. 137-167, 2007