Editing Decidability (logic) (section)

==Semidecidability==

A property of a theory or logical system weaker than decidability is '''semidecidability'''.  A theory is semidecidable if there is a well-defined method whose result, given an arbitrary formula, arrives as positive, if the formula is in the theory; otherwise, may never arrive at all; otherwise, arrives as negative. A logical system is semidecidable if there is a well-defined method for generating a sequence of theorems such that each theorem will eventually be generated. This is different from decidability because in a semidecidable system there may be no effective procedure for checking that a formula is ''not'' a theorem.

Every decidable theory or logical system is semidecidable, but in general the converse is not true; a theory is decidable if and only if both it and its complement are semi-decidable. For example, the set of logical validities ''V'' of first-order logic is semi-decidable, but not decidable. In this case, it is because there is no effective method for determining for an arbitrary formula ''A'' whether ''A'' is not in ''V''. Similarly, the set of logical consequences of any [[recursively enumerable set]] of first-order axioms is semidecidable. Many of the examples of undecidable first-order theories given above are of this form.