MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Since relational monadic first-order logic has finite model property, its SAT problem is decidable. In H.Behmann's paper, he extended this result to fragment of SOL where all predicates, free and bound are monadic. I am not familiar with SOL and his paper was not written in English. Can you give me any hint to prove this result?


share|cite|improve this question
Several sources on line describe it briefly, saying it is proved by quantifier elimination. For anyone who wants to look into this, the article is Behmann "Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem" Mathematische Annalen 86 (1922): 163-229. – Colin McLarty Sep 21 '13 at 13:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.