Introduction to Mathematical Logic

Catalog description

Propositional logic, first-order predicate logic, axioms and rules of inference, structures, models, definability, completeness, compactness. Logic forms the foundation of all mathematical reasoning. To prove a mathematical theorems, one deduces them step by step from basic principles, called axioms, or from other statements previously deduced. Each step of a proof has to be a logically valid rule, such as, for example, the modus ponens: "If A holds, and A implies B, then B holds." In Math 457, students will learn how concepts such as axiom, theorem, proof, and truth can be formulated as a mathematical theory, that is, logical reasoning will be studied as a mathematical subject. The simplest kind of logical system is propositional logic. Here, the basic components are whole statements which are either true or false, and which can be combined using logical connectives such AND, OR, or NOT to form new statements. Its simple nature makes propositional logic a good system to introduce many of the basic ideas: syntax and semantics, proof systems, completeness and compactness. However, propositional logic does not capture mathematical reasoning adequately. Therefore, one considers (first-order) predicate logic. Students will learn how formulas are formed according to syntactical rules. They will also study how a mathematical theory is defined as a set of formulas, how a proof is formally defined, and what constitutes a proof system. The syntactical notions above are contrasted with mathematical semantics, which considers structures over which formulas can be interpreted. This way, one can rigorously define whether a formal statement is true in a given mathematical structure, in which case we say the structure is a model of the statement. For example, the integers with addition are a model of the statement "for every x there exists a y such that x+y =0". A central goal of mathematical logic is to explore how the syntactical side (formulas, axioms, proof systems) and the semantical side (mathematical structures such as the additive group of integers) interact. Two fundamental results in this regard will be covered: the completeness theorem says that one can prove a statement from a set of axioms if and only if the statement is true in any structure satisfying all axioms. The compactness theorem, in turn, is an important consequence of the completeness theorem. It has profound implications for the existence and construction of mathematical structures. Students who would like to enroll in Math 457 are required to have some knowledge of mathematical proofs as provided in Math 311W.