Measuring the Complexity of Countable Models of Presburger Arithmetic

Abstract: We examine two methods for classifying the complexity of countable structures: degree spectra, and Scott analysis. Degree spectra measure how difficult it is to compute copies of structures, while Scott analysis measures the complexity of describing structures up to isomorphism. We examine the possible degree spectra and Scott complexities of countable Presburger groups and compare these results with those for models of Peano Arithmetic. We also discuss how these measures of complexity succeed/fail in distinguishing the intended model of the theory.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic