Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
We consider positively existentially definable sets in the structure 〈ℤ; 1, +, ⊥〉 It is well known that the elementary theory of this structure is undecidable while the existential theory is decidable. We show that after the extension of the signature with the unary '-' functional symbol, binary symbols for dis-equality ≠ and GCD(·, ·) = d for every fixed positive integer d, every positive existential formula in this extended language is equivalent in ℤ to some positive quantifier-free formula. Then we get some corollaries from the main result. The binary order ≤ and dis-coprimeness ⊥ relations are not positively existentially definable in the structure 〈ℤ; 1, +, ⊥〉. Every positively existentially definable set in the structure 〈N; S, ⊥〉 is quantifier-free definable in 〈N; S, ≠, 0, ⊥〉. We also get a decidable fragment of the undecidable ∀∃-Theory of the structure 〈ℤ; 1, +, ≤, |〉, where | is a binary predicate symbol for the integer divisibility relation.
Язык оригинала | английский |
---|---|
Название основной публикации | ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation |
Издатель | Association for Computing Machinery |
Страницы | 353–360 |
Число страниц | 8 |
ISBN (электронное издание) | 9781450383820 |
DOI | |
Состояние | Опубликовано - 18 июл 2021 |
Событие | ISSAC 2021 International Symposium on Symbolic and Algebraic Computation - EIMI, Санкт-Петербург, Российская Федерация Продолжительность: 18 июл 2021 → 23 июл 2021 Номер конференции: 46 https://issac-conference.org/2021/ |
Название | Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC |
---|
конференция | ISSAC 2021 International Symposium on Symbolic and Algebraic Computation |
---|---|
Сокращенное название | ISSAC 2021 |
Страна/Tерритория | Российская Федерация |
Город | Санкт-Петербург |
Период | 18/07/21 → 23/07/21 |
Сайт в сети Internet |
ID: 84459010