А.В. Ильев. Письмо в редакцию... С. 298

УДК 510.67, 519.1

В моей статье “Разрешимость универсальных теорий и аксиоматизируемость наследственных классов графов” (Тр. Ин-та математики и механики УрО РАН, 2016, т. 22, № 1), посвященной изучению наследственных классов графов методами теории моделей, имеется погрешность. Она касается условия 2) теоремы 7 о разрешимости универсальных теорий рекурсивно аксиоматизируемых наследственных классов графов. Поскольку сформулированные в статье аксиомы наследственного класса графов соответствуют запрещенным подграфам, то по умолчанию предполагалось, что речь идет о минимальных запрещенных подграфах, но это не было явно сказано. Однако в общем случае существуют классы графов с рекурсивно-перечислимым множеством аксиом, обладающие также и рекурсивным множеством аксиом, при этом универсальные теории данных классов неразрешимы. Примером такого наследственного класса является класс графов, не содержащих циклов длины n, где n ∈ Q — рекурсивно перечислимое, но нерекурсивное множество натуральных чисел.

Для устранения этой погрешности нужно дать определение рекурсивного множества запрещенных подграфов. Множество запрещенных подграфов называется рекурсивным, если существует геделевская нумерация g этих подграфов такая, что множество их номеров является рекурсивным. Затем условие 2) теоремы 7 необходимо уточнить следующим образом:

Универсальная теория произвольного наследственного класса графов, множество минимальных запрещенных подграфов которого рекурсивно, разрешима.

Тогда формулировка теоремы становится корректной, причем ее доказательство остается верным в неизменном виде.

С уважением, А.В.Ильев