Geodesic
On the coprimeness relation from the viewpoint of monadic second-order logic
Izvestiya. Mathematics , Tome 86 (2022) no. 6, pp. 1225-1239

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {86},
     number = {6},
     year = {2022},
     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
PB  - mathdoc
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
%I mathdoc
%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/