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

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

Аннотация

Работа является второй частью нового доказательства теоремы Бельтюкова-Липшица о разрешимости экзистенциальной теории структуры . Строится алгоритм квази-ЭК (понятие введено в первой части доказательства), осуществляющий сведение проблемы разрешимости для экзистенциальной теории структуры к проблеме разрешимости для позитивной экзистенциальной теории структуры 0; 1, {a·}a∈Z>0 , НОД>. Так как разрешимость последней теории была доказана в первой части, построенное сведение завершит доказательство теоремы. На шаге отделения переменной для квазиэлиминации используются аналоги двух лемм из доказательства Липшица. Шаг квазиэлиминации основан на НОДлемме, доказанной в первой части.
Язык оригиналарусский
Страницы (с-по)608-619
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Том66
Номер выпуска4
СостояниеОпубликовано - 4 янв 2022

Ключевые слова

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

Цитировать