Читать онлайн «Критические теории многообразий полугрупп с перестановочным тождеством»

Сибирский математический журнал Январь—февраль, 2001. Том 42, № 1 УДК 512:519. 4 КРИТИЧЕСКИЕ ТЕОРИИ МНОГООБРАЗИЙ ПОЛУГРУПП С ПЕРЕСТАНОВОЧНЫМ ТОЖДЕСТВОМ В. Ю. Попов Аннотация: Доказано, что произвольное конечно базируемое периодическое мно- гообразие полугрупп, удовлетворяющее перестановочному тождеству, либо имеет пустую границу разрешимости (т. е. его элементарная теория разрешима), либо его граница разрешимости равна {∃∀¬ ∧ ∨}. Библиогр. 7. Многообразия полугрупп с разрешимой элементарной теорией описаны в [1]. В [2] доказана разрешимость позитивной теории произвольного конечно базируемого многообразия полугрупп с перестановочным тождеством. Эти ре- зультаты делают актуальной задачу описания всех, в рамках некоторой иерар- хии [3], разрешимых теорий многообразий полугрупп. В работах [4, 5] указан- ная задача решена в терминах границы разрешимости (см. [6]) для многообра- зия всех полугрупп и периодических многообразий коммутативных полугрупп. Следующая теорема обобщает результат работы [5] на случай многообразий с перестановочным тождеством. Теорема. Произвольное конечно базируемое периодическое многообразие полугрупп X, удовлетворяющее перестановочному тождеству, либо имеет пу- стую границу разрешимости (т. е. его элементарная теория разрешима), либо его граница разрешимости равна {∃∀¬ ∧ ∨}. Заметим, что имеются примеры многообразий, упомянутых в теореме, как с пустой границей разрешимости, так и с границей разрешимости {∃∀¬ ∧ ∨} (см. [1]). Доказательство. Напомним, что граница разрешимости класса K ал- гебраических систем — это список всех языков L из схемно-альтернативной иерархии SA таких, что теория LK является критической, т. е. минимальной в иерархии SAK неразрешимой теорией. Описание границы разрешимости да- ет описание всех в рамках иерархии SA разрешимых теорий данного класса K : теория LK для L ∈ SA разрешима тогда и только тогда, когда L не включает ни одного из языков, принадлежащих границе разрешимости класса K . Допустим, что многообразие X имеет неразрешимую элементарную теорию. Убедимся, что теория ∃∀¬ ∧ ∨X неразрешима. Пусть C — многообразие комму- тативных полугрупп. Тогда в силу [1] элементарная теория многообразия X ∩ C неразрешима. Поэтому из [2] получаем неразрешимость теории ∃∀¬ ∧ ∨X ∩ C. Обозначим через ϕ произвольное предложение языка ∃∀¬∧∨. Рассмотрим пред- ложение ψ ∃xyxy 6= yx ∨ ϕ. Легко понять, что предложение ψ истинно на c 2001 Попов В. Ю. 154 В. Ю. Попов всех некоммутативных полугруппах, а на коммутативных полугруппах ψ истин- но тогда и только тогда, когда на них истинно предложение ϕ. Следовательно, X |= ψ ⇔ X ∩ C |= ϕ. Так как теория ∃∀¬ ∧ ∨X ∩ C неразрешима, не существует алгоритма, определяющего по предложению ψ истинность его на X. Поскольку ψ является ∃∀¬ ∧ ∨-предложением, теория ∃∀¬ ∧ ∨X неразрешима.