Undecidable fragments of elementary theories (Q1906521)

The author introduces a general approach to prove hereditary undecidability of fragments of theories depending on the number of quantifier blocks in formulas. As an application, he proves hereditary undecidability for \(\Sigma_k\)-theories of some natural classes of finite structures like graphs, lattices, partial orders, as well as natural structures arising in recursion theory. In particular, he proves hereditary undecidability for \(\Pi_3\)-theories of p.o. sets of \(m\)-degrees, r.e. \(m\)-degrees, \(\Pi_4\)-theories of p.o. sets of r.e. tt-degrees and btt-degrees.