Advanced Mathematical Logic Fall 2013:Course Aims and Assessment

Distinguishing two levels in studying logic is customary. At the sentential or truth-functional level, simple declarative sentences are the basic units of analysis. Complex statements are built up from these basic units by means of truth-functional connectives. Symbolically, simple statements are represented by sentence letters and the connectives through special symbols. At the first-order predicate level, most symbolic representations of statements are built up from predicate letters, constants, and variables as the basic units, by means of connectives and quantifiers. At both the sentential and predicate level, we may define semantic concepts and explicate such basic notions as logical truth, consistency, and validity with respect to these semantic concepts. Also at each level we may construct formal derivation systems containing inference rules licensing inferring a conclusion of a certain form (as analyzed at that level) from one or more premises of a certain form (again as analyzed at that level). These are syntactic notions. We may thus, for example, speak both of an argument as being truth-functionally valid and its conclusion being derivable from the premises in a system of sentential logic. Likewise, we may speak both of an argument’s being quantificationally valid and its conclusion being derivable from its premises in a system of first-order predicate logic.

               Do the semantic and syntactic families of concepts match up? If we may derive the conclusion of an argument from its premises, is the argument truth-functionally valid? Conversely, if the argument is truth-functionally valid, may we derive the conclusion from the premises? A positive answer to the first question for a given sentential derivation system shows that system sound. A positive answer to the second question shows the system complete. Analogous conditions hold at the first-order predicate level.

               The Soundness and Completeness Theorems for sentential and first-order predicate logic constitute the core results we shall present in this course. We shall be proving theorems about logic and so our subject is properly called metalogic. Mathematical induction (especially strong induction) is an indispensable proof technique in metalogic. The first course goal then is to develop facility in applying mathematical induction in metalogical contexts. Establishing the expressive power of fragments of sentential and first-order predicate languages greatly simplifies the task of showing soundness and completeness. Our second goal is to establish certain results about expressive completeness. We shall then turn to showing soundness and completeness at the sentential and then predicate levels. At the conclusion of the course, we shall extend these results to predicate logic with identity. Our goal is not only to present these results but to develop facility in proving lemmas, corollaries, and theorems associated with these results.