Decidability of A Logical System
Each logical system comes with both a syntactic component, which among other things determines the notion of provability, and a semantic component, which determines the notion of logical validity. The logically valid formulas of a system are sometimes called the theorems of the system, especially in the context of first-order logic where Gödel's completeness theorem establishes the equivalence of semantic and syntactic consequence. In other settings, such as linear logic, the syntactic consequence (provability) relation may be used to define the theorems of a system.
A logical system is decidable if there is an effective method for determining whether arbitrary formulas are theorems of the logical system. For example, propositional logic is decidable, because the truth-table method can be used to determine whether an arbitrary propositional formula is logically valid.
First-order logic is not decidable in general; in particular, the set of logical validities in any signature that includes equality and at least one other predicate with two or more arguments is not decidable (provided the finitely axiomatizable theory Robinson Arithmetic is consistent; this provison is implicit in every undecidability claim made in this article). Logical systems extending first-order logic, such as second-order logic and type theory, are also undecidable.
The validities of monadic predicate calculus with identity are decidable, however. This system is first-order logic restricted to signatures that have no function symbols and whose relation symbols other than equality never take more than one argument.
Some logical systems are not adequately represented by the set of theorems alone. (For example, Kleene's logic has no theorems at all.) In such cases, alternative definitions of decidability of a logical system are often used, which ask for an effective method for determining something more general than just validity of formulas; for instance, validity of sequents, or the consequence relation {(Г, A) | Г ⊧ A} of the logic.
Read more about this topic: Decidability (logic)
Famous quotes containing the words logical and/or system:
“The logical English train a scholar as they train an engineer. Oxford is Greek factory, as Wilton mills weave carpet, and Sheffield grinds steel. They know the use of a tutor, as they know the use of a horse; and they draw the greatest amount of benefit from both. The reading men are kept by hard walking, hard riding, and measured eating and drinking, at the top of their condition, and two days before the examination, do not work but lounge, ride, or run, to be fresh on the college doomsday.”
—Ralph Waldo Emerson (1803–1882)
“The pace of science forces the pace of technique. Theoretical physics forces atomic energy on us; the successful production of the fission bomb forces upon us the manufacture of the hydrogen bomb. We do not choose our problems, we do not choose our products; we are pushed, we are forced—by what? By a system which has no purpose and goal transcending it, and which makes man its appendix.”
—Erich Fromm (1900–1980)