Monadic Second Order Logic and Linear Orders

Abstract

This thesis presents a model-theoretical analysis of some theories of linear orders in monadic and weak monadic second order logic. In particular, the pseudofinite monadic second order theory of linear order and the weak monadic second order theory of a dense linear order. The analysis of the former plays a key role in the analysis of the latter. We adopt a one-sorted first-order setup for dealing with monadic and weak monadic second order logic, which is described in full detail. In both instances the model-theoretical analysis involves presenting an axiomatisation which gives insight into non-standard models, and obtaining a model-completeness result after suitably enriching the signature. For the pseudofinite monadic second order theory of linear order, we also classify the completions using residue functions and establish a connection to the free profinite monoid on one generator using extended Stone duality. Throughout, an emphasis is placed on non-standard models of monadic and weak monadic second order theories. Towards our analysis of the weak monadic second order theory of a dense linear order, we present a definable composition theorem, inspired by Shelah's composition theorem, which is more easily applied in the case of non-standard models.

Date of Award	31 Dec 2021
Original language	English
Awarding Institution	The University of Manchester
Supervisor	Marcus Tressl (Supervisor) & Gareth Jones (Supervisor)