  We investigate the relationship between recursive enumerability and
elementary frame definability in first-order predicate modal logic. On the one
hand, it is well-known that every first-order predicate modal logic complete
with respect to an elementary class of Kripke frames, i.e., a class of frames
definable by a classical first-order formula, is recursively enumerable. On the
other, numerous examples are known of predicate modal logics, based on
`natural' propositional modal logics with essentially second-order Kripke
semantics, that are either not recursively enumerable or Kripke incomplete.
This raises the question of whether every Kripke complete, recursively
enumerable predicate modal logic can be characterized by an elementary class of
Kripke frames. We answer this question in the negative, by constructing a
normal predicate modal logic which is Kripke complete, recursively enumerable,
but not complete with respect to an elementary class of frames. We also present
an example of a normal predicate modal logic that is recursively enumerable,
Kripke complete, and not complete with respect to an elementary class of rooted
frames, but is complete with respect to an elementary class of frames that are
not rooted.
