Modest Automorphisms of Presburger Arithmetic
type: CreativeWork
description: 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.
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.
author: Heller, Simon
keywords: Logic and Foundations, Presburger arithmetic, automorphism, DP-rank, quantifier elimination, expansion
date published: 2019-09-01T07:00:00Z
date modified: 2026-07-24T01:58:49Z
provider: City University of New York - Graduate Center
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: The Graduate School and University Center of The City University of New York