University of Illinois Urbana-Champaign

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

Schulz, Christian Carl

Content Files
SCHULZ-DISSERTATION-2023.pdf

Permalink

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

Description

Title
Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems
Author(s)
Schulz, Christian Carl
Issue Date
2023-06-14
Director of Research (if dissertation) or Advisor (if thesis)
Hieronymi, Philipp C. K.
Doctoral Committee Chair(s)
van den Dries, Lou P. D.
Committee Member(s)
  • Kishida, Kohei
  • Bell, Jason P.
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • model theory
  • logic
  • Presburger arithmetic
  • definability
  • decidability
  • Ostrowski numeration
  • automata
  • finite automata
  • Buchi automata
  • fractals
  • Hausdorff dimension
  • box-counting dimension
Abstract
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_1^\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, \alpha \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.
Graduation Semester
2023-08
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/121415
Copyright and License Information
Copyright 2023 Christian Schulz

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois