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.

It is a classical result of Mortimer that $L^2$ , first-order logic with two variables, is decidable for satisfiability. We show that going beyond $L^2$ by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.¶(i) transitive closure operations¶(ii) (restricted) monadic fixed-point operations¶– weak access to cardinalities, through the Härtig (or equicardinality) quantifier¶– a choice construct known as Hilbert's $\epsilon$ -operator.In fact all these extensions of $L^2$ prove to be undecidable both for satisfiability, (...) and for satisfiability in finite structures. Moreover most of them are hard for $\Sigma^1_1$ , the first level of the analytical hierachy, and thus have a much higher degree of undecidability than first-order logic. (shrink)