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

Schulz, Christian Carl

Permalink

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

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