On the coprimeness relation from the viewpoint of monadic second-order logic

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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}$.

作者简介

Stanislav Speranski

Steklov Mathematical Institute of Russian Academy of Sciences

Email: katze.tail@gmail.com
Candidate of physico-mathematical sciences, no status

Fedor Pakhomov

Steklov Mathematical Institute of Russian Academy of Sciences; Ghent University

Email: pakhfn@gmail.com
Candidate of physico-mathematical sciences, Senior Researcher

参考

  1. D. Richard, “What are weak arithmetics?”, Theoret. Comput. Sci., 257:1-2 (2001), 17–29
  2. J. Y. Halpern, “Presburger arithmetic with unary predicates is $Pi_1^1$ complete”, J. Symbolic Logic, 56:2 (1991), 637–642
  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
  4. A. Bès, D. Richard, “Undecidable extensions of Skolem arithmetic”, J. Symbolic Logic, 63:2 (1998), 379–401
  5. J. Robinson, “Definability and decision problems in arithmetic”, J. Symbolic Logic, 14:2 (1949), 98–114
  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
  7. S. O. Speranski, “Some new results in monadic second-order arithmetic”, Computability, 4:2 (2015), 159–174
  8. Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, М., 1972, 624 с.
  9. J. R. Büchi, “Weak second-order arithmetic and finite automata”, Z. Math. Logik Grundlagen Math., 6:1-6 (1960), 66–92
  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

补充文件

附件文件
动作
1. JATS XML

版权所有 © Speranski S.O., Pakhomov F.N., 2022

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».