Geodesic
On the coprimeness relation from the viewpoint of monadic second-order logic
Izvestiya. Mathematics, Tome 86 (2022) no. 6, pp. 1225-1239 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $\mathfrak{C}$ denote the structure of the natural numbers with the coprimeness relation. We prove that for each non-zero natural number $n$, if a $\Pi^1_n$-set of natural numbers is closed under automorphisms of $\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$ set quantifiers. On the other hand, we observe that even a much weaker version of this property fails for certain expansions of $\mathfrak{C}$.
Keywords: coprimeness, monadic second-order logic, definability, weak arithmetics. 
@article{IM2_2022_86_6_a9,
     author = {S. O. Speranski and F. N. Pakhomov},
     title = {On the coprimeness relation from the viewpoint of monadic second-order logic},
     journal = {Izvestiya. Mathematics},
     pages = {1225--1239},
     year = {2022},
     volume = {86},
     number = {6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2022_86_6_a9/}
}
TY  - JOUR
AU  - S. O. Speranski
AU  - F. N. Pakhomov
TI  - On the coprimeness relation from the viewpoint of monadic second-order logic
JO  - Izvestiya. Mathematics
PY  - 2022
SP  - 1225
EP  - 1239
VL  - 86
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/IM2_2022_86_6_a9/
LA  - en
ID  - IM2_2022_86_6_a9
ER  - 
%0 Journal Article
%A S. O. Speranski
%A F. N. Pakhomov
%T On the coprimeness relation from the viewpoint of monadic second-order logic
%J Izvestiya. Mathematics
%D 2022
%P 1225-1239
%V 86
%N 6
%U http://geodesic.mathdoc.fr/item/IM2_2022_86_6_a9/
%G en
%F IM2_2022_86_6_a9
S. O. Speranski; F. N. Pakhomov. On the coprimeness relation from the viewpoint of monadic second-order logic. Izvestiya. Mathematics, Tome 86 (2022) no. 6, pp. 1225-1239. http://geodesic.mathdoc.fr/item/IM2_2022_86_6_a9/

[1] D. Richard, “What are weak arithmetics?”, Theoret. Comput. Sci., 257:1-2 (2001), 17–29 | DOI | MR | Zbl

[2] J. Y. Halpern, “Presburger arithmetic with unary predicates is $\Pi_1^1$ complete”, J. Symbolic Logic, 56:2 (1991), 637–642 | DOI | MR | Zbl

[3] S. O. Speranski, “A note on definability in fragments of arithmetic with free unary predicates”, Arch. Math. Logic, 52:5-6 (2013), 507–516 | DOI | MR | Zbl

[4] A. Bès and D. Richard, “Undecidable extensions of Skolem arithmetic”, J. Symbolic Logic, 63:2 (1998), 379–401 | DOI | MR | Zbl

[5] J. Robinson, “Definability and decision problems in arithmetic”, J. Symbolic Logic, 14:2 (1949), 98–114 | DOI | MR | Zbl

[6] 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 | MR | Zbl

[7] S. O. Speranski, “Some new results in monadic second-order arithmetic”, Computability, 4:2 (2015), 159–174 | DOI | MR | Zbl

[8] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York–Toronto, ON–London, 1967 ; Russian transl. Mir, Moscow, 1972 | MR | Zbl | MR | Zbl

[9] J. R. Büchi, “Weak second-order arithmetic and finite automata”, Z. Math. Logik Grundlagen Math., 6:1-6 (1960), 66–92 | DOI | MR | Zbl

[10] 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 | MR | Zbl