Semantics Club 24 11 2000

Compositional theorem for generalized sum

Alexander Rabinovich

Abstract

Composition Theorems are tools which reduce sentences about a complex structure to sentences about its parts. A seminal example of such a result is the Feferman-Vaught Theorem (1959) 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. In this talk I explain:

  1. a definition of a generalized sum of structure and
  2. a composition theorem for first-order logic over the generalized sum.
Some applications of the composition theorem to definability will be provided which replace game (or inductive) arguments by transparent reductions.