1
$\begingroup$

Description logic is a fragment of first order logic, but description logic is decidable and first order logic not decidable. Why is that? what is the role of variables in first order logic to make it undecidable?

$\endgroup$
1
$\begingroup$

This has to do with the fact that you can define arithmetic inside the axiomatic system or not. In description logic you cannot speak about arithmetic sentences and in first order logic you do.

if you look at the proof of incompleteness you will understand this in depth. This demonstration depends on an arithmetic coding of statements, and this representation is fundamental to obtain the conclusion.

$\endgroup$
  • $\begingroup$ This seems like a good answer, but it would be a lot more useful if it cited references. Could you edit your answer to include relevant links? $\endgroup$ – Philip Raeisghasem Apr 1 at 20:00
  • $\begingroup$ Sorry its not clear to me yet... can you give examples? $\endgroup$ – shah Apr 4 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.