{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121415"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121415","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled &#x27;Open Access&#x27;. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_has_math":false,"creators":["Schulz, Christian Carl"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Hieronymi, Philipp C. K.","van den Dries, Lou P. D.","Kishida, Kohei","Bell, Jason P."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:24:57Z","subjects":["Model Theory","Logic","Presburger Arithmetic","Definability","Decidability","Ostrowski Numeration","Automata","Finite Automata","Buchi Automata","Fractals","Hausdorff Dimension","Box-counting Dimension"],"languages":["en","eng"],"rights":["Copyright 2023 Christian Schulz"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121415","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hieronymi, Philipp C. K.","van den Dries, Lou P. D.","Kishida, Kohei","Bell, Jason P."]},{"key":"dc:creator","label":"Author","values":["Schulz, Christian Carl"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-06-14"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Model Theory","Logic","Presburger Arithmetic","Definability","Decidability","Ostrowski Numeration","Automata","Finite Automata","Buchi Automata","Fractals","Hausdorff Dimension","Box-counting Dimension"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Christian Schulz"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121415"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Christian Schulz, accepted the attached license on 2023-06-12 at 15:52.","The student, Christian Schulz, submitted this Dissertation for approval on 2023-06-12 at 15:59.","This Dissertation was approved for publication on 2023-06-14 at 15:32.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19418 on 2023-12-04 at 16:59:56","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems"]}]}],"canonical_facts":{"dc:contributor":["Hieronymi, Philipp C. K.","van den Dries, Lou P. D.","Kishida, Kohei","Bell, Jason P."],"dc:creator":["Schulz, Christian Carl"],"dc:date":["2023-08","2023-06-14"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Christian Schulz, accepted the attached license on 2023-06-12 at 15:52.","The student, Christian Schulz, submitted this Dissertation for approval on 2023-06-12 at 15:59.","This Dissertation was approved for publication on 2023-06-14 at 15:32.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19418 on 2023-12-04 at 16:59:56","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121415"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Christian Schulz"],"dc:subject":["Model Theory","Logic","Presburger Arithmetic","Definability","Decidability","Ostrowski Numeration","Automata","Finite Automata","Buchi Automata","Fractals","Hausdorff Dimension","Box-counting Dimension"],"dc:title":["Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}