Аннотация:
Хорошо известны примеры групп и полугрупп как обладающих алгоритмически
разрешимыми элементарными теориями так и таких, для которых
соответствующие элементарные теории неразрешимы. Настоящий доклад
посвящен вопросу о разрешимости теорий полугрупп в языке с большими
выразительными возможностями. Рассматривается язык первого порядка в
сигнатуре с бинарной операцией умножения, равенством и дополнительным
одноместным предикатным символом $P$. Элементарная теория полугруппы $S$ со
свободным одноместным предикатом есть множество всех предложений этого
языка истинных в полугруппе $S$ при интерпретации бинарной операции как
умножения в $S$ и при интерпретации символа $P$ как любого одноместного
предиката на множестве $S$. Будет изложен общий результат о том, что для
всякой бесконечной полугруппы $S$ с сокращением элементарная теория со
свободным одноместным предикатом неразрешима. Также будет
обсуждаться вопрос о возможных степенях неразрешимости таких теорий.
|
