The empty theory

  • Thread starter zeberdee
  • Start date
  • #1
zeberdee
2
0
How do you prove the decidability of the empty theory and theory of linear orders?
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
43,021
971
Uh, what is the "empty theory"?
 
  • #3
zeberdee
2
0
By empty theory I mean the theory In the empty language ( ie no non logical symbols ) with no axioms.
 
  • #4
Preno
147
0
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.
 

Suggested for: The empty theory

  • Last Post
Replies
2
Views
189
Replies
12
Views
609
Replies
13
Views
423
  • Last Post
Replies
9
Views
933
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
8
Views
532
  • Last Post
Replies
10
Views
2K
Replies
14
Views
865
Replies
4
Views
231
Replies
9
Views
1K
Top