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

Строится $\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$-теории рассматриваемых классов разрешимы.