LOGIC - Completeness vs Consistent

1.5k Views Asked by At

One of my exams questions were the following (translated from Hebrew)

Course is in Artificial Intelligence, and is about Logic in this question.

What is a consistent logic system?
What is a complete logic system?
If you had the chance to chose a consistent system or a complete system which would you chose and why?

The question in bold is the one i need an answer to, but feel free to define what a consistent / complete system is before answering the question.

Appreciate your help, thanks.

1

There are 1 best solutions below

4
On BEST ANSWER

I'm not sure about how general the term "logic system" is supposed to be, so I'll assume it means a theory — a set of sentences of first order logic, in some particular language (set of constants, predicates, function symbols).

A theory $T$ is inconsistent iff it for some sentence $S$ in its language it proves both $T\vdash S$ and $T\vdash \neg S$. An inconsistent theory proves every sentence. A theory is consistent iff it's not inconsistent.

A theory $T$ is complete iff it's a maximal consistent set of sentences: the theory is consistent, and for every sentence $S$ of its language, $T$ proves either $S$ or $\neg S$: $T\vdash$ or $T\vdash \neg S$ (but, by consistency, not both).

Note on usage: sometimes complete may be defined without the requirement of consistency. According to that definition, a theory $T$ is complete' (let's designate it) iff for every sentence $S$ of its language, $T$ proves either $S$ or $\neg S$: $T\vdash$ or $T\vdash \neg S$ (or, possibly, both! — every inconsistent system is complete'). Since this is an exam question, obviously your course has introduced one definition or the other: you'd know which one, and there's no sense in my guessing. If your working definition is the weaker one, then I would always prefer a consistent theory to an inconsistent one, although the latter is complete'.

I would always prefer a complete consistent theory that extends a merely consistent theory, provided the theories are "recursively axiomatizable", in the sense that it's decidable which sentences are in the theory and which aren't. In that case, the complete theory has a decision procedure, its set of theorems is nontrivial and recursive (decidable), whereas the theorems of a recursively axiomatizable consistent theory are merely recursively enumerable (r.e., semi-decidable).

Note that in the previous paragraph, the requirement of "recursively axiomatizability" is important. Theories are abstract things, arbitrary sets of sentences. If $T$ is the theory consisting of all sentences of arithmetic that are true in the standard model of the integers, then $T$ is complete, but is highly non-decidable (much, much more complex than, for example, the halting problem). In this case, I'd prefer the theory PA (Peano arithmetic): $T$ extends PA, but at least PA is semi-decidable.