1
$\begingroup$

I'm trying to get a better grasp of the relationship between these concepts so I have a few questions about them.

Does a consistent theory have to be (or have to not be) axiomatizable?

Does an inconsistent theory need to be axiomatizable? (Is the answer yes because all inconsistent theories are the same in that anything is provable?)

Does an axiomatizable have to be decidable?

And are decidable theories always complete/what's their relation?

A specific example for some of these is robinson arithmetic which I know is axiomatized and incomplete. Is it decidable? Could it be extended to be decidable or complete? Would this be an example of an axiomatizable theory that's not decidable?

Sorry if this is scattered, there are a lot of relationships here I'm not sure how to connect.

$\endgroup$
3
  • $\begingroup$ A theory $T$ is axiomatizable iff there is a decidable set $\Sigma$ of sentences such that $T = \text {Cn}(\Sigma)$.. $\endgroup$
    – Mauro ALLEGRANZA
    Apr 27, 2017 at 11:39
  • $\begingroup$ If $T$ is axiomatizable and complete, then it is decidable. $\endgroup$
    – Mauro ALLEGRANZA
    Apr 27, 2017 at 11:40
  • $\begingroup$ Yes, this is scattered and you have asked about "a lot of relationships" here. Rather than setting forth so many "unsolved" problems, you should do some spade work to locate what the definitions are. What is (in your text book or other source materials) a theory? Most authors would insist a formal theory has (among other characteristics) a decidable set of axioms (as Mauro Allegranza comments above), but this is a separate issue from whether the theory is decidable. Which issues are a result of not knowing the defintions and which a result of not knowing the implications of them? $\endgroup$
    – hardmath
    Apr 27, 2017 at 16:27

2 Answers 2

Reset to default
4
$\begingroup$

Does a consistent theory have to be (or have to not be) axiomatizable?

No a consistent theory may or may not be axiomatizable. First order Peano Arithmetic is consistent (we hope) and axiomatized. First order True Arithmetic (all the truths of the first order language of arithmetic) is consistent but not axiomatizable.

Does an inconsistent theory need to be axiomatizable?

In a classical setting, an inconsistent theory proves everything (in the relevant language). So is axiomatized by the theory which has every sentence (of the relevant language) as an axiom.

Does an axiomatizable theory have to be decidable?

No. First-order Peano Arithmetic is, if consistent, not decidable.

Are decidable theories always complete.

No. The empty theory with no axioms is decidable (no sentence is a thoerem!) but not complete.

A specific example for some of these is robinson arithmetic which I know is axiomatized and incomplete. Is it decidable?

No it isn't.

Could it be extended to be decidable or complete?

It can be extended to a complete theory, complete True Arithmetic -- but that is neither axiomatizable nor decidable.

It can be extended to the inconsistent theory which is decidable, complete, and axiomatizable ... but sadly useless.

No axiomatizable consistent extension of Robinson Arithmetic is complete.

The usual textbooks will spell this out for you. (See §4.2 of the Teach Yourself Logic Study Guide for relevant recommended texts.)

$\endgroup$
2
  • 1
    $\begingroup$ minor quibble, the empty theory does have theorems like $\forall x (x=x) $. $\endgroup$
    – Noah Schweber
    Apr 27, 2017 at 19:08
  • $\begingroup$ Depends how generously you are using "theory" I guess! Suppose a theory is a set of sentences closed under some consequence relation. Take the null consequence relation .... $\endgroup$
    – Peter Smith
    Apr 27, 2017 at 21:31
0
$\begingroup$

Just an addendum to Peter Smith's answer:

Does an inconsistent theory need to be axiomatizable? (Is the answer yes because all inconsistent theories are the same in that anything is provable?)

Any inconsistent theory can be axiomatized by the following axiom set: $\{ \bot \}$

Does an axiomatizable have to be decidable?

No. The fact that a theory is axiomatizable means that there exists a recursive set of axioms whose logical consequences make up that theory. As such, the set of axioms themselves is decidable. However, first-order logical consequence is not decidable, and so the theory as a whole may not be decidable. In fact, since the very set of first-order logical tautologies is undecidable (that is: since first-order logic itself is undecidable), and since all first-order logic tautologies are first-order logical consequences of any theory, no first-order logic theory is decidable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .