deducibility relation See DEDUCTION, Appendix of. Special Symbols. deduction, a finite sequence of sentences whose last sentence is a conclusion of the sequence (the one said to be deduced) and which is such that each sentence in the sequence is an axiom or a premise or follows from preceding sentences in the sequence by a rule of inference. A synonym is ‘derivation’. Deduction is a system-relative concept. It makes sense to say something is a deduction only relative to a particular system of axioms and rules of inference. The very same sequence of sentences might be a deduction relative to one such system but not relative to another. The concept of deduction is a generalization of the concept of proof. A proof is a finite sequence of sentences each of which is an axiom or follows from preceding sentences in the sequence by a rule of inference. The last sentence in the sequence is a theorem. Given that the system of axioms and rules of inference are effectively specifiable, there is an effective procedure for determining, whenever a finite sequence of sentences is given, whether it is a proof relative to that system. The notion of theorem is not in general effective (decidable). For there may be no method by which we can always find a proof of a given sentence or determine that none exists. The concepts of deduction and consequence are distinct. The first is a syntactical; the second is semantical. It was a discovery that, relative to the axioms and rules of inference of classical logic, a sentence S is deducible from a set of sentences K provided that S is a consequence of K. Compactness is an important consequence of this discovery. It is trivial that sentence S is deducible from K just in case S is deducible from some finite subset of K. It is not trivial that S is a consequence of K just in case S is a consequence of some finite subset of K. This compactness property had to be shown.
A system of natural deduction is axiomless. Proofs of theorems within a system are generally easier with natural deduction. Proofs of theorems about a system, such as the results mentioned in the previous paragraph, are generally easier if the system has axioms.
In a secondary sense, ‘deduction’ refers to an inference in which a speaker claims the conclusion follows necessarily from the premises.
See also AXIOMATIC METHOD, COMPACT- NESS THEOREM , EFFECTIVE PROCEDURE , FOR – MAL SEMANTICS , PROOF THEORY. C.S.