Здравствуйте. Возникли сложности с пониманием теоремы Трахтенброта (
https://archive.org/details/a-concise-i ... 5/mode/1up). Попробую разбить вопросы на пункты(не по порядку):
1. В доказательстве применяется упражнение 1 пятого параграфа третьей главы (
https://archive.org/details/a-concise-i ... 1/mode/1up). Нужно доказать, что получившееся расширение будет разрешимым. Алгоритм построить достаточно легко, при условии известности всех новых формул теории: чтобы узнать, принадлежит ли любая формула получившейся теории

, сначала нужно понять, принадлежит ли она

(это возможно, так как

разрешима). Если формула принадлежит

, то она будет принадлежать и

(алгоритм останавливается). Если же нет, то достаточно её "сверить" с конечным множеством

на предмет принадлежности. Как я уже говорил, такой алгоритм можно построить при условии, что мы можем определить(алгоритмически) множество

. А можно ли это сделать(каким алгоритмом найти это множество(также понять, что к этому множеству больше не присоединить конечное количество неких формул)), если по условию лишь известно, что расширение теории

конечно?
2. Также используется упражнение 2 шестого параграфа третьей главы (
https://archive.org/details/a-concise-i ... 6/mode/1up). Не смог понять, какое решение предлагает автор в пункте a) (
https://page.mi.fu-berlin.de/raut/logic3/hint.pdf) (страница 9, 3.6). Как пишет автор, на шаге

нужно записать лишь те формулы(с индексом меньшим или равным

), которые не будут удовлетворять энной модели

. Не может ли произойти случая, когда, например, формуле

не будет удовлетворять лишь конечная модель

(остальные будут)?(т.к. согласно построению автора , как я понял, для

на предмет удовлетворимости моделям можно будет лишь проверить модели с порядковым номером "больше или равно 10" (на предмет удовлетворимости модели

можно лишь проверить формулы с индексом

))
3. Автор указывает, что если теория

(также

) аксиоматизируема, то она разрешима(из-за свойства конечных моделей), согласно упражнению 2. Но для применения упражнения 2 эти теории должны удовлетворять ещё одному условию: все конечные модели этих теорий должны быть эффективно перечислимы, а как для них это доказать?
4. Упражнением 1 доказывается, что если бы

была разрешима, то это бы влекло разрешимость теории FSG(теории конечных полугрупп), так как она конечно расширяется (добавляется формула ассоциативности). Как в данном случае показать, что теория

(где

- закон ассоциативности) будет конечным расширением? (под конечным расширением теории(могу неправильно переводить) я понимаю теорию, которая, при добавлении конечного множества формул, увеличится на конечное множество элементов).