Is First Order Logic + Arithmetic semi-decidable?

Question

I understand that it is not complete, but is it decidable, semidecidable or not decidable? Also, does something have to be complete for it to be considered decidable or semidecidable? Meaning, can something be decidable but not complete?

Answer 1

First, you haven't specified what theory you are talking about. When you say "first order logic + arithmetic" I see that we must be talking about a theory in the first order language of arithmetic, but I don't know which one. True arithmetic, Peano arithmetic, Robinson arithmetic?

Let's review definitions. A theory is a set of sentences (here sentences in the first order language of arithmetic) that is closed under logical consequence. A typical theory is a set of logical consequences of some set of axioms. (Sometimes, the set of axioms - rather than the full set of consequences - is what is called the theory. I will use the first definition.) A theory is decidable if there is an effective algorithm that takes a sentence and accepts if it is in the theory and rejects if not. A theory is semi-decidable if there is an effective algorithm that takes a sentence and accepts if it is in the theory, and rejects or loops if not. A theory is complete of for any sentence, either the sentence or its negation is in the theory. Note that complete and semi-decidable implies decidable since one can make an algorithm that simultaneously tests the statement and its negation.

True arithmetic is the set of all true statements. It is obviously complete since any statement is true or its negation is. However, its decidability would solve the halting problem (since the halting problem is arithmetically expressible) so it isn't decidable. And since complete and semi-decidable would imply decidable, it isn't semi-decidable either.

Peano arithmetic is the set of consequences of the first order Peano axioms. Here since a sentence being an axiom is decidable, we can enumerate all possible proofs and thus if the sentence is in the theory and we wait long enough, we will find a proof of it eventually. So it is semi-decidable. It is not decidable, however, by the famous diagonalization argument. If it were complete, its semi-decidability would imply its decidability, so it's not complete either. (This paragraph is just paraphrasing one version of the standard results on Godel's incompleteness theorem.)

Neither of these is decidable and incomplete, but this is a possibility. We would need a theory that is ambiguous about some statements (so that neither the statement nor its negation are in the theory), while we can still effectively sort out which statements are true (i.e. in the theory), false (i.e. their negation is in the theory) and ambiguous (i.e. neither is). A classic example is the theory of algebraically closed fields. It can be shown decidable by quantifier elimination, but the characteristic of the field is a first-order property left completely unspecified, so the theory has no answers to sentences whose truth depends on the characteristic and so is incomplete.

Edit: Come to think of it, a much more basic example is the theory of propositional tautologies, which is decidable via truth tables but is incomplete since there are many propositional sentences that are neither tautologies nor contradictions, like the sentence "$A$", for instance. Also this is a good example to emphasize that the completeness of a theory is a different thing from the completeness of a deductive system. The standard deductive systems of propositional logic are complete in the sense that every logically valid formula can be proven.

Edit 2: (sorry, I keep coming back to this one and wanting to add stuff for some reason...) It occurs to me you could mean the theory of logically valid sentences in the language of arithmetic (i.e. with no non-logical axioms so that totally arbitrary interpretations are possible). In fact this seems the most literal reading of your question. This theory is obviously incomplete (there is surely an interpretation where, say, $0+1=0$ holds... just switch the meaning of plus and times). The easiest way to show it is undecidable is to observe that if it were, it could decide any finitely axiomatized theory $T,$ since we could decide if an arbitrary sentence $\phi$ is in $T$ by deciding the validity of $\psi\to \phi,$ where $\psi$ is the conjunction of $T$'s axioms. The fact that there are finitely axiomatized undecidable theories (like Robinson arithmetic) finishes the argument. It is semi-decidable, by the same argument as for Peano arithmetic.