ABSTRACT
Our main goal in this chapter is to establish that the deductive system for first-order languages presented in Chapter 4 is both sound and complete. We prove the soundness of the system in this section. Establishing that the system is complete will occupy us for much of the remainder of the chapter. We start then by proving that our deductive system is sound-- that it will only allow us to deduce a formula ~ from a set of formulas r
if~ is a logical consequence ofr. SOUNDNESS THEOREM: For every formula~ of a first-order language L and every set r of L-formulas, if r 1-- ~. then r F= ~· Proof By induction on deducibility in L. In the inductive clauses corresponding to the quantifier rules, we shall invoke a result about substitution which we will only establish after we have completed the present proof.
