2022/09/14 by Deacon Linkhorn, Linkhorn, Deacon
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2209.06655
openalex publication_date 2022/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a streamlined and (hopefully) accessible proof of the model-completeness of the weak monadic second order version of a dense linear order with left-endpoint but no right-endpoint in a particular finite signature. We also show how this can be used to establish model-completeness of the lattice of finite unions of closed intervals of a dense linear order, i.e. the lattice of closed definable subsets in a (densely ordered) o-minimal structure, in a particularly simple signature (comprising binary functions for union and intersection together with two constant symbols and four unary function symbols).