Доказательство теоремы Бельтюкова-Липшица квазиэлиминацией кванторов. I. Определения и НОД-лемма

Standard

Доказательство теоремы Бельтюкова-Липшица квазиэлиминацией кванторов. I. Определения и НОД-лемма. / Старчак, Михаил Романович.

в: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ, Том 8(66), № 3, 26.09.2021, стр. 455-466.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

BibTeX

@article{7b1d2e2ad4c7464e81c37b4cc408fc7e,

title = "Доказательство теоремы Бельтюкова-Липшица квазиэлиминацией кванторов. I. Определения и НОД-лемма",

abstract = "анная работа является первой частью нового доказательства разрешимости экзистенциальной теории структуры , где | соответствует двухместному отношению делимости. Разрешимость этой теории была доказана в 1976 г. независимо А.П. Бельтюковым и Л.Липшицем. В 1977 г. В. И.Мартьянов получил эквивалентный результат, рассматривая трехместный предикат НОД вместо отношения делимости (эти предикаты экзистенциально выражаются друг через друга с помощью других символов сигнатуры). В работе вводится понятие алгоритма квазиэлиминации кванторов (квази-ЭК), обобщающее в некотором смысле понятие алгоритма элиминации кванторов, а затем строится алгоритм квази-ЭК для позитивной экзистенциальной теории структуры <...>. К проблеме разрешимости для этой теории сводится проблема разрешимости для экзистенциальной теории структуры <...>. Алгоритм квази-ЭК, осуществляющий такое сведение, будет построен во второй части доказательства. Преобразования формул основаны на обобщении китайской теоремы об остатках для систем вида НОД(ai, bi + x) = di для всех i [1..m], где ai, bi, di - целые числа, такие что ai 6= 0, di > 0.",

keywords = "элиминация кванторов, экзистенциальная теория, делимость, алгоритмическая разрешимость, китайская теорема об остатках",

author = "Старчак, {Михаил Романович}",

note = "Старчак, М. Р. (2021). Доказательство теоремы Бельтюкова-Липшица квазиэлиминацией кванторов. I. Определения и НОД-лемма. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 8(3), 455-466. https://doi.org/10.21638/spbu01.2021.307",

year = "2021",

month = sep,

day = "26",

language = "русский",

volume = "8(66)",

pages = "455--466",

journal = "ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ",

issn = "1025-3106",

publisher = "Издательство Санкт-Петербургского университета",

number = "3",

}

RIS

TY - JOUR

T1 - Доказательство теоремы Бельтюкова-Липшица квазиэлиминацией кванторов. I. Определения и НОД-лемма

AU - Старчак, Михаил Романович

N1 - Старчак, М. Р. (2021). Доказательство теоремы Бельтюкова-Липшица квазиэлиминацией кванторов. I. Определения и НОД-лемма. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 8(3), 455-466. https://doi.org/10.21638/spbu01.2021.307

PY - 2021/9/26

Y1 - 2021/9/26

N2 - анная работа является первой частью нового доказательства разрешимости экзистенциальной теории структуры , где | соответствует двухместному отношению делимости. Разрешимость этой теории была доказана в 1976 г. независимо А.П. Бельтюковым и Л.Липшицем. В 1977 г. В. И.Мартьянов получил эквивалентный результат, рассматривая трехместный предикат НОД вместо отношения делимости (эти предикаты экзистенциально выражаются друг через друга с помощью других символов сигнатуры). В работе вводится понятие алгоритма квазиэлиминации кванторов (квази-ЭК), обобщающее в некотором смысле понятие алгоритма элиминации кванторов, а затем строится алгоритм квази-ЭК для позитивной экзистенциальной теории структуры <...>. К проблеме разрешимости для этой теории сводится проблема разрешимости для экзистенциальной теории структуры <...>. Алгоритм квази-ЭК, осуществляющий такое сведение, будет построен во второй части доказательства. Преобразования формул основаны на обобщении китайской теоремы об остатках для систем вида НОД(ai, bi + x) = di для всех i [1..m], где ai, bi, di - целые числа, такие что ai 6= 0, di > 0.

AB - анная работа является первой частью нового доказательства разрешимости экзистенциальной теории структуры , где | соответствует двухместному отношению делимости. Разрешимость этой теории была доказана в 1976 г. независимо А.П. Бельтюковым и Л.Липшицем. В 1977 г. В. И.Мартьянов получил эквивалентный результат, рассматривая трехместный предикат НОД вместо отношения делимости (эти предикаты экзистенциально выражаются друг через друга с помощью других символов сигнатуры). В работе вводится понятие алгоритма квазиэлиминации кванторов (квази-ЭК), обобщающее в некотором смысле понятие алгоритма элиминации кванторов, а затем строится алгоритм квази-ЭК для позитивной экзистенциальной теории структуры <...>. К проблеме разрешимости для этой теории сводится проблема разрешимости для экзистенциальной теории структуры <...>. Алгоритм квази-ЭК, осуществляющий такое сведение, будет построен во второй части доказательства. Преобразования формул основаны на обобщении китайской теоремы об остатках для систем вида НОД(ai, bi + x) = di для всех i [1..m], где ai, bi, di - целые числа, такие что ai 6= 0, di > 0.

KW - элиминация кванторов

KW - экзистенциальная теория

KW - делимость

KW - алгоритмическая разрешимость

KW - китайская теорема об остатках

UR - https://math-mech-astr-journal.spbu.ru/article/view/11825

M3 - статья

VL - 8(66)

SP - 455

EP - 466

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 3

ER -

ID: 86141154