Inexpressiveness of First-Order Fragments

Abstract

It is well-known that first-order logic is semi-decidable. Therefore, first-order logic is less than ideal for computational purposes (computer science, knowledge engineering). Certain fragments of first-order logic are of interest because they are decidable. But decidability is gained at the cost of expressiveness. The objective of this paper is to investigate inexpressiveness of fragments that have received much attention.