On the coprimeness relation from the viewpoint of monadic second-order logic
- Authors: Speranski S.O.1, Pakhomov F.N.1,2
-
Affiliations:
- Steklov Mathematical Institute of Russian Academy of Sciences
- Ghent University
- Issue: Vol 86, No 6 (2022)
- Pages: 207-222
- Section: Articles
- URL: https://bakhtiniada.ru/1607-0046/article/view/133918
- DOI: https://doi.org/10.4213/im9340
- ID: 133918
Cite item
Open Access
Access granted
Subscription Access
Abstract
Let $\mathfrak{C}$ denote the structure of the natural numbers with thecoprimeness relation. We prove that for each non-zero natural number $n$,if a $\Pi^1_n$-set of natural numbers is closed under automorphismsof $\mathfrak{C}$, then it is definable in $\mathfrak{C}$ by a monadic$\Pi^1_n$-formula of the signature of $\mathfrak{C}$ having exactly $n$ setquantifiers.On the other hand, we observe that even a much weaker version of this property fails for certain expansions of $\mathfrak{C}$.
About the authors
Stanislav Olegovich Speranski
Steklov Mathematical Institute of Russian Academy of Sciences
Email: katze.tail@gmail.com
Candidate of physico-mathematical sciences, no status
Fedor Nikolaevich Pakhomov
Steklov Mathematical Institute of Russian Academy of Sciences; Ghent University
Email: pakhfn@gmail.com
Candidate of physico-mathematical sciences, Senior Researcher
References
- D. Richard, “What are weak arithmetics?”, Theoret. Comput. Sci., 257:1-2 (2001), 17–29
- J. Y. Halpern, “Presburger arithmetic with unary predicates is $Pi_1^1$ complete”, J. Symbolic Logic, 56:2 (1991), 637–642
- S. O. Speranski, “A note on definability in fragments of arithmetic with free unary predicates”, Arch. Math. Logic, 52:5-6 (2013), 507–516
- A. Bès, D. Richard, “Undecidable extensions of Skolem arithmetic”, J. Symbolic Logic, 63:2 (1998), 379–401
- J. Robinson, “Definability and decision problems in arithmetic”, J. Symbolic Logic, 14:2 (1949), 98–114
- A. Bès, “A survey of arithmetical definability”, A tribute to Maurice Boffa, Bull. Belg. Math. Soc. Simon Stevin, suppl., Soc. Math. Belgique, Brussels, 2001, 1–54
- S. O. Speranski, “Some new results in monadic second-order arithmetic”, Computability, 4:2 (2015), 159–174
- Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, М., 1972, 624 с.
- J. R. Büchi, “Weak second-order arithmetic and finite automata”, Z. Math. Logik Grundlagen Math., 6:1-6 (1960), 66–92
- J. R. Büchi, “On a decision method in restricted second order arithmetic”, Logic, methodology and philosophy of science (1960), Stanford Univ. Press, Stanford, CA, 1962, 1–11
Supplementary files
