Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The empty theory

  1. May 23, 2009 #1
    How do you prove the decidability of the empty theory and theory of linear orders?
  2. jcsd
  3. May 23, 2009 #2


    User Avatar
    Science Advisor

    Uh, what is the "empty theory"?
  4. May 23, 2009 #3
    By empty theory I mean the theory In the empty language ( ie no non logical symbols ) with no axioms.
  5. May 23, 2009 #4
    The sentences of the empty theory over the empty language include only the logical connective, quantifiers and equality, so deciding them is quite simple. The empty theory over a language which includes only single-argument predicates is monadic logic, which is also decidable. The empty theory over a language which includes at least one predicate with two arguments is, however, not decidable.

    The theory of linear orders should be decidable using quantifier elimination.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook