1
$\begingroup$

While it is not the case that the extension of every decidable theory is decidable, is it true that:

the extension of every undecidable theory undecidable?

In other words, given an undecidable theory A, is it enough to show

$$A \subseteq B$$

to prove that B is undecidable?

$\endgroup$
2
  • 3
    $\begingroup$ Cross-posted to computer science and CS theory. Please do not do this. It is against site policy because it fragments answers and wastes people's time when they work on something that has already been answered elsewhere. $\endgroup$ Dec 3 '14 at 9:40
  • 1
    $\begingroup$ Properties like undecidability tend to never be closed against sub- or superset. $\emptyset$ and $\Sigma^*$ are trivial counter-examples to any such claim. $\endgroup$
    – Raphael
    Dec 3 '14 at 11:44
3
$\begingroup$

No. A theory is a set of theorems. The set of all formulas is a decidable theory and it is an extension of all theories, including undecidable ones. It is also very inconsistent and thus useless in practice, but it is a counter-example to your claim.

$\endgroup$
0

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.