Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems

This thesis establishes several new results in the study of the tameness of expansions of various forms of arithmetic. Here \textit{arithmetic} roughly means the ordered additive structure of a familiar set of numbers, specifically as pertains to encodings of the elements of the structure. So this is a field of study that lies at the intersection of \textit{model theory,} the study of structures as related to their first-order definable relations, and \textit{automata theory,} the study of computationally simple means of encoding and processing information. The purpose of this thesis, largely, is to examine the properties of structures on the natural numbers, integers, and real numbers defined via encodings recognizable by finite and B\"uchi automata. The first two chapters provide a more detailed overview of the work and a review of the necessary background. In Chapter 3, we examine the structure (\N, +, a₁^\N, \dots, a_n^\N). This structure is a significant starting point in the study of \textit{$k$-automatic sets,} sets of natural numbers defined by their base-$k$ representations. We prove that the first-order theory of this structure is never decidable in nontrivial cases; however, unlike earlier results in this direction that proceeded by defining the multiplication function, here we prove that this structure cannot define multiplication either. This thus gives it an intermediate level of tameness not formerly seen in the study of $k$-automatic sets of integers. In Chapter 4, we shift our attention to $k$-automatic subsets of [0, 1]^d. These sets often have fractal properties, and in fact several well-known fractals, such as the ternary Cantor set, are $k$-automatic. So in this thesis we produce algorithmic methods for computing the fractal properties of $k$-automatic fractals, including box-counting dimension and Hausdorff dimension and measure. Leveraging our work, we are then able to prove a model-theoretic result characterizing which $k$-automatic expansions of the real additive group give rise to sets for whom different definitions of fractal dimension disagree. In Chapter 5, we move on from $k$-representations and instead consider the \textit{Ostrowski representations,} a set of number encodings based on the continued fractions of irrational numbers. Using B\"uchi automata on Ostrowski representations, we are able to prove decidability results about structures of the form (\R, <, +, \Z, α \Z). These structures have a strong connection to \textit{Sturmian words,} which are a common object of study in the field of combinatorics on words. Using these results, we are able to implement our decision procedures in an automated theorem prover called Pecan, using it to reprove several results about Sturmian words and extend them to new cases. Lastly, Chapter 6 gives some detail about potential directions for future work.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Schulz, Christian Carl

Contributors dc:contributor

• Hieronymi, Philipp C. K.
• van den Dries, Lou P. D.
• Kishida, Kohei
• Bell, Jason P.

• Model Theory
• Logic
• Presburger Arithmetic
• Definability
• Decidability
• Ostrowski Numeration
• Automata
• Finite Automata
• Buchi Automata
• Fractals
• Hausdorff Dimension
• Box-counting Dimension

Statement dc:rights

• Copyright 2023 Christian Schulz

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121415

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121415