Dissertations, Theses, and Capstone Projects
Date of Degree
9-2019
Document Type
Dissertation
Degree Name
Ph.D.
Program
Mathematics
Advisor
Alfred Dolich
Committee Members
Roman Kossak
Phillip Rothmaler
Hans Schoutens
Subject Categories
Logic and Foundations
Keywords
Presburger arithmetic, automorphism, DP-rank, quantifier elimination, expansion
Abstract
It is interesting to consider whether a structure can be expanded by an automorphism so that one obtains a nice description of the expanded structure's first-order properties. In this dissertation, we study some such expansions of models of Presburger arithmetic. Building on some of the work of Harnik (1986) and Llewellyn-Jones (2001), in Chapter 2 we use a back-and-forth construction to obtain two automorphisms of sufficiently saturated models of Presburger arithmetic. These constructions are done first in the quotient of the Presburger structure by the integers (which is a divisible ordered abelian group with some added structure), and then lifted to the full Presburger structure.
The first automorphism we construct has special tightly controlled properties that enable us in Chapters 4 and 5 to prove quantifier elimination, decidability, and axiomatizability for both the quotient and the Presburger structure expanded by this automorphism, with explicit axiomatizations given in Chapter 3. The second automorphism is maximal in the sense that its fixed-point set consists only of the standard integers, and has certain properties in common with those of the first automorphism, but we have not attempted to prove quantifier elimination for structures expanded by this automorphism.
In Chapters 6 and 7, we use the quantifier elimination results to describe the definable sets and algebraic closure of the quotient structure and Presburger structure expanded by the first automorphism. This allows us in Chapter 8 to show that the DP-rank in both cases is 2. Finally, in the concluding chapter, we describe some areas of possible future research.
Recommended Citation
Heller, Simon, "Modest Automorphisms of Presburger Arithmetic" (2019). CUNY Academic Works.
https://academicworks.cuny.edu/gc_etds/3416