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 $\langle\mathbf{R}, \leq, +\rangle$ this gives a decision procedure for the ∃ x∀ y-part of the theory of all substructures, yet we show that the ∃ x 1x 2 ∀ y-part, and the entire theory, is Π 1 1 -complete. The theory of all ordered subsemigroups of $\langle\mathbf{R}, \leq, +\rangle$ is also shown Π 1 1 -complete. Applications in the philosophy of science are mentioned