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

Мы продолжим обсуждение метода интерпретаций и его применений. В ходе настоящего доклада будет показано, что класс всех конечных двудольных графов является $\Sigma_1$-интерпретируемым (без параметров) в классе всех пар эквивалентностей на общем конечном носителе. Отсюда будет следовать наследственная неразрешимость $\Sigma_2$-теории второго класса, а также, по модулю $\Sigma_1$-интерпретации из предыдущего доклада, наследственная неразрешимость $\Sigma_2$-теории класса всех пар, состоящих из линейного порядка и эквивалентности на общем конечном носителе.