?
О наследственно неразрешимых фрагментах базовых элементарных теорий
Математические заметки. 2025. Т. 118. № 1. С. 77–90.
Карпов В. Е., Сперанский С. О.
Строится $\Sigma_1$-интерпретация класса BiG-fin всех конечных двудольных графов в классе 2Eq-fin всех пар отношений эквивалентности на общем конечном носителе; это даёт наследственную неразрешимость $\Sigma_2$-теории 2Eq-fin. Далее, строится $\Sigma_1$-интерпретация 2Eq-fin в классе LEq-fin всех пар, состоящих из линейного порядка и отношения эквивалентности на общем конечном носителе; это даёт наследственную неразрешимость $\Sigma_2$-теории LEq-fin. Полученные результаты являются в известном смысле оптимальными, поскольку $\Pi_2$-теории рассматриваемых классов разрешимы.