{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121510"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121510","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Decidability bounds for extensions of Presburger arithmetic","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":["Blanchard, Eion"],"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","van den Dries, Lou","Parthasarathy, Madhusudan","Kishida, Kohei"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:25:00Z","subjects":["Mathematical Logic","Model Theory","Theoretical Computer Science","Decidability","Undecidability","Presburger Arithmetic"],"languages":["en","eng"],"rights":["Copyright 2023 Eion Blanchard"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121510","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hieronymi, Philipp","van den Dries, Lou","Parthasarathy, Madhusudan","Kishida, Kohei"]},{"key":"dc:creator","label":"Author","values":["Blanchard, Eion"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-07-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":["Mathematical Logic","Model Theory","Theoretical Computer Science","Decidability","Undecidability","Presburger Arithmetic"]}]},{"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 Eion Blanchard"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121510"]}]},{"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, Eion Blanchard, accepted the attached license on 2023-07-12 at 09:48.","The student, Eion Blanchard, submitted this Dissertation for approval on 2023-07-12 at 09:55.","This Dissertation was approved for publication on 2023-07-14 at 07:06.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19647 on 2023-12-04 at 17:02:16","This thesis considers undecidable logical theories extending or closely related to Presburger arithmetic, the decidable first-order theory of the natural numbers with order and addition. Through the primary lens of quantifier complexity rather than computational complexity, we develop explicit bounds for the threshold between decidable and undecidable fragments of such theories. In Chapter 2, we consider a generalized setting with the fragment of the first-order theory of a structure over the ordered real numbers with quantification restricted to a fixed subset. When the structure defines functions with sufficiently wild properties, we demonstrate how to encode the weak monadic second-order theory of the grid. With this, we simulate a Turing machine and thus encode the halting problem, which is undecidable, as a first-order sentence in the language at hand. This yields an upper bound for decidable fragments of such theories in terms of the quantifier complexity for defining a few basic tools. In each of Chapter 3, Chapter 4, and Chapter 5, we consider a particular theory and instantiate the main theorem from Chapter 2 to conclude that the set of sentences with four alternating quantifier blocks of a given minimum length is undecidable. In Chapter 3, we consider sine-Presburger arithmetic (sin-PA), which is the fragment of the first-order theory of (R, <, 0, 1, +, sin, N) in which quantification is restricted to N. We provide a decision procedure for the existential sentences in this theory that is conditioned by a positive answer to Schanuel’s conjecture, an open problem in number theory. In Chapter 4, we consider μ_{2,3}-linear real arithmetic (μ_{2,3}-LRA), which is the fragment of the first-order theory of (R, <, 0, 1, +, μ_{2,3}, 2^N) in which quantification is restricted to 2^N and μ_{2,3} : 2^N → [1, 3) is the function that divides a power of 2 by its preceding power of 3. We provide a decision procedure for the existential sentences in this theory that is conditioned by a positive answer to an open conjecture that the finitely many nondegenerate solutions to any linear equation over the multiplicative group B_{2,3} := 2^Z 3^Z are computable; this is deemed the effective Mann property of B_{2,3}. In Chapter 5, we consider A_{2,3}-real arithmetic (A_{2,3}-RA), which is the fragment of the first-order theory of (R, <, 0, 1, +, ·, A_{2,3}) in which quantification is restricted to A_{2,3} := 2^N ∪ 3^N. While we do not provide a full decision procedure for the existential sentences in this theory, we do conjecture its existence, again under assumption of the effective Mann property of B_{2,3}. As partial progress toward a positive answer to this conjecture, we reduce the decision problem for existential sentences in this theory to the decision problem for open existential sentences in the same signature with quantification restricted to 2^N and 3^N."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Decidability bounds for extensions of Presburger arithmetic"]}]}],"canonical_facts":{"dc:contributor":["Hieronymi, Philipp","van den Dries, Lou","Parthasarathy, Madhusudan","Kishida, Kohei"],"dc:creator":["Blanchard, Eion"],"dc:date":["2023-08","2023-07-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, Eion Blanchard, accepted the attached license on 2023-07-12 at 09:48.","The student, Eion Blanchard, submitted this Dissertation for approval on 2023-07-12 at 09:55.","This Dissertation was approved for publication on 2023-07-14 at 07:06.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19647 on 2023-12-04 at 17:02:16","This thesis considers undecidable logical theories extending or closely related to Presburger arithmetic, the decidable first-order theory of the natural numbers with order and addition. Through the primary lens of quantifier complexity rather than computational complexity, we develop explicit bounds for the threshold between decidable and undecidable fragments of such theories. In Chapter 2, we consider a generalized setting with the fragment of the first-order theory of a structure over the ordered real numbers with quantification restricted to a fixed subset. When the structure defines functions with sufficiently wild properties, we demonstrate how to encode the weak monadic second-order theory of the grid. With this, we simulate a Turing machine and thus encode the halting problem, which is undecidable, as a first-order sentence in the language at hand. This yields an upper bound for decidable fragments of such theories in terms of the quantifier complexity for defining a few basic tools. In each of Chapter 3, Chapter 4, and Chapter 5, we consider a particular theory and instantiate the main theorem from Chapter 2 to conclude that the set of sentences with four alternating quantifier blocks of a given minimum length is undecidable. In Chapter 3, we consider sine-Presburger arithmetic (sin-PA), which is the fragment of the first-order theory of (R, <, 0, 1, +, sin, N) in which quantification is restricted to N. We provide a decision procedure for the existential sentences in this theory that is conditioned by a positive answer to Schanuel’s conjecture, an open problem in number theory. In Chapter 4, we consider μ_{2,3}-linear real arithmetic (μ_{2,3}-LRA), which is the fragment of the first-order theory of (R, <, 0, 1, +, μ_{2,3}, 2^N) in which quantification is restricted to 2^N and μ_{2,3} : 2^N → [1, 3) is the function that divides a power of 2 by its preceding power of 3. We provide a decision procedure for the existential sentences in this theory that is conditioned by a positive answer to an open conjecture that the finitely many nondegenerate solutions to any linear equation over the multiplicative group B_{2,3} := 2^Z 3^Z are computable; this is deemed the effective Mann property of B_{2,3}. In Chapter 5, we consider A_{2,3}-real arithmetic (A_{2,3}-RA), which is the fragment of the first-order theory of (R, <, 0, 1, +, ·, A_{2,3}) in which quantification is restricted to A_{2,3} := 2^N ∪ 3^N. While we do not provide a full decision procedure for the existential sentences in this theory, we do conjecture its existence, again under assumption of the effective Mann property of B_{2,3}. As partial progress toward a positive answer to this conjecture, we reduce the decision problem for existential sentences in this theory to the decision problem for open existential sentences in the same signature with quantification restricted to 2^N and 3^N."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121510"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Eion Blanchard"],"dc:subject":["Mathematical Logic","Model Theory","Theoretical Computer Science","Decidability","Undecidability","Presburger Arithmetic"],"dc:title":["Decidability bounds for extensions of Presburger arithmetic"],"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:25:00Z"}