Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914006978002944 |
|---|---|
| author | Brown, Hera Konieczny, Jakub |
| author_facet | Brown, Hera Konieczny, Jakub |
| contents | We study the extension of Presburger arithmetic by the class of sub-polynomial Hardy field functions, and show the majority of these extensions to be undecidable. More precisely, we show that the theory $\mathrm{Th}(\mathbb{Z}; <, +, \lfloor f \rceil)$, where $f$ is a Hardy field function and $\lfloor \cdot \rceil$ the nearest integer operator, is undecidable when $f$ grows polynomially faster than $x$. Further, we show that when $f$ grows sub-linearly quickly, but still as fast as some polynomial, the theory $\mathrm{Th}(\mathbb{Z}; <, +, \lfloor f \rceil)$ is undecidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19206 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions Brown, Hera Konieczny, Jakub Logic in Computer Science Logic Number Theory 11U05, 03B10, 03B25, 11J54 We study the extension of Presburger arithmetic by the class of sub-polynomial Hardy field functions, and show the majority of these extensions to be undecidable. More precisely, we show that the theory $\mathrm{Th}(\mathbb{Z}; <, +, \lfloor f \rceil)$, where $f$ is a Hardy field function and $\lfloor \cdot \rceil$ the nearest integer operator, is undecidable when $f$ grows polynomially faster than $x$. Further, we show that when $f$ grows sub-linearly quickly, but still as fast as some polynomial, the theory $\mathrm{Th}(\mathbb{Z}; <, +, \lfloor f \rceil)$ is undecidable. |
| title | Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions |
| topic | Logic in Computer Science Logic Number Theory 11U05, 03B10, 03B25, 11J54 |
| url | https://arxiv.org/abs/2508.19206 |