Expressive power versus decidability
share
In this note we prove that there exists no fragment of first-order logic which satisfies simultaneously the following requirements: a) it has a recursive syntax b) it is equi-expressive with first-order logic over finite models c) it has a decidable finite satisfiability problem d) it is effectively closed under conjunction. We also point out that there exists a fragment of first-order logic which satisfies requirements a), b) and c) simultaneously.
READ FULL TEXT