Modest Automorphisms of Presburger Arithmetic

<p>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.</p> <p>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.</p> <p>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.</p>

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Mathematics

Grantor

The Graduate School and University Center of The City University of New York

Year dc:date.available

2019

Author dc:creator

• Heller, Simon

Advisor dc:contributor.advisor

• Alfred Dolich

Committee members dc:contributor.committeemember

• Roman Kossak
• Phillip Rothmaler
• Hans Schoutens

• Logic and Foundations
• Presburger arithmetic
• automorphism
• DP-rank
• quantifier elimination
• expansion

Repository record dc:identifier

https://academicworks.cuny.edu/gc_etds/3416

OAI identifier oai:identifier

oai:academicworks.cuny.edu:gc_etds-4461