# Relationship of consistency, axiomatizability, and decidability

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.

• A theory $T$ is axiomatizable iff there is a decidable set $\Sigma$ of sentences such that $T = \text {Cn}(\Sigma)$.. – Mauro ALLEGRANZA Apr 27 '17 at 11:39
• If $T$ is axiomatizable and complete, then it is decidable. – Mauro ALLEGRANZA Apr 27 '17 at 11:40
• 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? – hardmath Apr 27 '17 at 16:27

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.)

• minor quibble, the empty theory does have theorems like $\forall x (x=x)$. – Noah Schweber Apr 27 '17 at 19:08
• 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 .... – Peter Smith Apr 27 '17 at 21:31

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