The empty theory

  • Thread starter zeberdee
  • Start date
  • #1
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
41,833
961
Uh, what is the "empty theory"?
 
  • #3
2
0
By empty theory I mean the theory In the empty language ( ie no non logical symbols ) with no axioms.
 
  • #4
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.
 

Related Threads on The empty theory

  • Last Post
Replies
15
Views
8K
  • Last Post
Replies
20
Views
5K
Replies
10
Views
1K
  • Last Post
Replies
3
Views
8K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
24
Views
14K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
12
Views
7K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
2K
Top