О наследственно неразрешимых фрагментах базовых элементарных теорий

Строится $\Sigma_1$-интерпретация класса $BiG_{\mathrm{fin}}$ всех конечных двудольных графов в классе $2Eq_{\mathrm{fin}}$ всех пар отношений эквивалентности на общем конечном носителе; это дает наследственную неразрешимость $\Sigma_2$-теории $2Eq_{\mathrm{fin}}$. Далее, строится $\Sigma_1$-интерпретация $2Eq_{\mathrm{fin}}$ в классе $LEq_{\mathrm{fin}}$ всех пар, состоящих из линейного порядка и отношения эквивалентности на общем конечном носителе; это дает наследственную неразрешимость $\Sigma_2$-теории $LEq_{\mathrm{fin}}$. Полученные результаты являются в известном смысле оптимальными, поскольку $\Pi_2$-теории рассматриваемых классов разрешимы.
Библиография: 11 названий.