Gurevich Classifiability Theorem

57 Views Asked by At

I have a question regarding the classification of fragments of first-order logic as presented in The Classical Decision Problem. Page 9 reads:

The classification problem for the prefix-vocabulary fragments admits a complete solution in a form of a finite table. In particular, there are only finitely many minimal undecidable fragments with closed prefix sets, and all these minimal fragments are standard. This follows from the Classifiability Theorem of Gurevich proved in Sect. 2.3. Accordingly, in the main body of the book, the prefix-vocabulary classes of interest will be almost exclusively standard classes. The Classifiability Theorem has provided guidance for re­search and it provides guidance for this book.

The statement suggests that if we focus on minimal classes which have closed prefix-set then we have a finite number of them and they are in standard form.

Question 1: what happens if I lift the closedness condition?

Plus, the statement of the theorem 2.3.40 is technical and I see no mention to maximal fragments.

Let $D$ be a downward closed collection of prefix-vocabulary classes closed under finite unions. Further, let $U$ be the complement of $D$, and $M$ the collection of minimal closed classes in $U$. Then $M$ is finite, every member of $M$ is standard, and $U$ is the upward closure of $M$. In addition, the number of maximal standard members of $D$ is finite.

Question 2: how does the theorem apply to maximal decidable fragments?