Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-18T04:51:43.932Z Has data issue: false hasContentIssue false

The theory of all substructures of a structure: Characterisation and decision problems1

Published online by Cambridge University Press:  12 March 2014

Kenneth L. Manders*
Affiliation:
Group in Logic and Methodology of Science, University of California, Berkeley, California 94720
*
Department of Philosophy and Mathematics, University of Pittsburg, Pittsburg, PA 15260

Abstract

An infinitary characterisation of the first-order sentences true in all substructures of a structure M is used to obtain partial reduction of the decision problem for such sentences to that for Th(M). For the relational structure 〈R, ≤, + 〉 this gives a decision procedure for the ∃x∀y-part of the theory of all substructures, yet we show that the ∃x1x2∀y-part, and the entire theory, is Π11-complete. The theory of all ordered subsemigroups of 〈R, ≤, + 〉 is also shown Π11-complete. Applications in the philosophy of science are mentioned.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1979

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable