Mathematical Logic (Math 570) Lecture Notes

1 Mathematical Logic (Math 570) Lecture NotesLou van den DriesFall Semester 2019 Contents1 Mathematical Logic : a brief overview .. Sets and Maps ..52 Basic Concepts of Propositional Logic .. Completeness for Propositional Logic .. Languages and Structures .. Variables and Terms .. Formulas and Sentences .. Models .. Logical Axioms and Rules; Formal Proofs .. 383 The Completeness Another Form of Completeness .. Proof of the Completeness Theorem.

2 Some Elementary Results of Predicate Logic .. Equational Classes and Universal Algebra .. 544 Some Model L owenheim-Skolem; Vaught s Test .. Elementary Equivalence and Back-and-Forth .. Quantifier Elimination .. Presburger Arithmetic .. Skolemization and Extension by Definition .. 745 Computability, Decidability, and Computable Functions .. The Church-Turing Thesis .. Primitive Recursive Functions .. Representability.

3 Decidability and G odel Numbering .. Theorems of G odel and Church .. A more explicit incompleteness theorem .. Undecidable Theories .. 111 Chapter 1 PreliminariesWe start with a brief overview of Mathematical Logic as covered in this we review some basic notions from elementary set theory, which providesa medium for communicating mathematics in a precise and clear way. In thiscourse we develop Mathematical Logic using elementary set theory as given,just as one would do with other branches of mathematics, like group theory orprobability more on the course material, seeShoenfield, J.

4 R., Mathematical Logic , Reading, Addison-Wesley, additional material in Model Theory we refer the reader toChang, C. C. and Keisler, H. J.,Model Theory, New York, North-Holland, 1990,Poizat, B.,A Course in Model Theory, Springer, 2000,and for additional material on Computability, toRogers, H.,Theory of Recursive Functions and Effective Com-putability, McGraw-Hill, Mathematical Logic : a brief overviewAristotle identified some simple patterns in human reasoning, and Leibniz dreamtof reducing reasoning to calculation.

5 As a viable Mathematical subject, however, Logic is relatively recent: the 19th century pioneers were Bolzano, Boole, Cantor,Dedekind, Frege, Peano, Peirce, and E. Schr oder. From our perspectivewe see their work as leading to boolean algebra, set theory, propositional Logic ,predicate Logic , as clarifying the foundations of the natural and real numbersystems, and as introducing suggestive symbolic notation for logical , their activity led to the view thatlogic + set theorycan serve as a basis for12 CHAPTER 1.

6 PRELIMINARIESall of mathematics. This era did not produce theorems in Mathematical logicof any real depth,1but it did bring crucial progress of a conceptual nature,and the recognition that Logic as used in mathematics obeys Mathematical rulesthat can be made fully the period 1900-1950 important new ideas came from Russell, Zermelo,Hausdorff, Hilbert, L owenheim, Ramsey, Skolem, Lusin, Post, Herbrand, G odel,Tarski, Church, Kleene, Turing, and Gentzen. They discovered the first realtheorems in Mathematical Logic , with those of G odel having a dramatic (in G ottingen), Lusin (in Moscow), Tarski (in Warsaw and Berkeley),and Church (in Princeton) had many students and collaborators, who made upa large part of that generation and the next in Mathematical Logic .

7 Most ofthese names will be encountered again during the early part of the 20th century was also marked by the so-calledfoundational crisis in strong impulse for developing Mathematical Logic came from the attemptsduring these times to provide solid foundations for mathematics. Mathematicallogic has now taken on a life of its own, and also thrives on many interactionswith other areas of mathematics and computer the second half of the last century, Logic as pursued by mathematiciansgradually branched into four main areas:model theory,computability theory(orrecursion theory),set theory, andproof theory.

8 The topics in this course arepart of the common background of mathematicians active in any of these distinguishes Mathematical Logic within mathematics is thatstatements about Mathematical objects and structuresare taken seriously as Mathematical objects in their own right. More generally,in Mathematical Logic we formalize (formulate in a precise Mathematical way)notions used informally by mathematicians such as: property statement(in a given language) structure truth(what it means for a given statement to be true in a given structure) proof(from a given set of axioms) algorithm1In the case of set theory one could dispute this.

9 Cantor s discoveries were profound, buteven so, the main influence of set theory on the rest of mathematics was to enable simpleconstructions of great generality, like cartesian products, quotient sets and power sets, andthis involves only very elementary set Mathematical Logic : A BRIEF OVERVIEW3 Once we have Mathematical definitions of these notions, we can try to provetheorems about these formalized notions. If done with imagination, this processcan lead to unexpected rewards. Of course, formalization tends to caricaturethe informal concepts it aims to capture, but no harm is done if this is keptfirmly in The notorious Goldbach Conjecture asserts that every even integergreater than 2 is a sum of two prime numbers.

10 With the understanding thatthe variables range overN={0,1,2,..}, and that 0,1,+, ,<denote theusual arithmetic operations and relations onN, this assertion can be expressedformally as(GC) x[(1 + 1< x even(x)) p q(prime(p) prime(q) x=p+q)]where even(x) abbreviates y(x=y+y) and prime(p) abbreviates1< p r s(p=r s (r= 1 s= 1)).The expressionGCis an example of a formal statement (also called asentence)in thelanguage of arithmetic, which has symbols 0,1,+, ,<to denote arithmeticoperations and relations, in addition to logical symbols like =, , , , , , ,and variablesx,y,z,p,q,r, Goldbach Conjecture asserts that this particular sentenceGCistrueinthestructure(N; 0,1,+, ,<).