Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Thanks!

share|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. gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN002268752 –  Colin McLarty Sep 21 '13 at 13:22
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.