150.421 Mathematical Logic II |
||
Instructor
Robert Rynasiewicz Course ContentMathematical Logic II is the second semester of a year long course. The first semester, 150.420 Mathematical Logic I, introduces the notions of logical validity and provability for first-order predicate logic (a.k.a. elementary logic) showing that there is a sound and complete system of derivation. (In fact, two systems are introduced, a Hilbert system of direct derivation using logical axioms and a system of natural deduction using other derivational strategies but no logical axioms.) Soundness is the result that whatever is provable from a set of formulas is a logical consequence of those formulas. Conversely, a system of derivation is complete if any logical consequence of a set of formulas is provable from those formulas in that system of derivation. The notions of effective procedure, decidability, and effective enumerability are also introduced and explored. In particular, it is shown that the set of logical consequences of a decidable set of sentences is effectively enumerable. This result can be rephrased as follows. A theory, by definition, is a set of sentences closed under logical consequence. A theory T is axiomatizable if and only if (iff) there is a deciable set of sentences whose set of logical consequences is T itself. Thus, any axiomatizable theory is effectively enumerable. Furthermore, a theory is said to be complete iff for any sentence of the language in question, either it or its negation is a theorem (i.e., an element of the theory). It's easy to show that any complete axiomatizable theory is decidable, i.e., that there is a decision procedure for determining whether any given sentence is a theorem. Mathematical Logic II continues these investigations for arithmetic theories, culminating in Gödel's two incompleteness theorems. The first states that any axiomatization of arithmetic leaves some arithmetic propositions undecided. In other words, the set of all arithmetic truths is not axiomatizable. This immediately entails that the set of all arithmetic truths is undecidable. Since it can also be shown that there is a finitely axiomatizable subtheory of arithmetic that is undecidable, it follows that the set of logical validities is also undecidable (Church's Theorem). The second Gödel incompleteness theorem states that if a system is strong enough to talk about its own consistency, as is Peano Arithmetic, then it cannot prove its own consistency unless it is inconsistent. In covering these Gödel theorems, we also introduce the notions of recursive functions and sets. Church's Thesis states that the class of recursive functions is the class of effectively computable functions. This also coincides with the class of Turing computable functions (functions computable by means of a Turing machine). We conclude with the halting problem, i.e., that there is no Turing maching that can tell us when a given Turing machine with a given input will eventually halt. Texts
Online ResourcesPeter Smith has a web page for his book as a part of his website, Logic Matters. In case you're interested, there you can find an introduction to the Introduction, called "Gödel W/O (Too Many) Tears." Smith's site also has a "Teach Yourself Logic" section, which leads to a pdf "Study Guide" containing many references to logic books at the advanced level. For a really brief synopsis of Smith's Introduction, see my Synopsis of Smith. This might serve you as a handy reference and review resource. If you're not familiar with Fitch-style natural deduction, the rules are set out in this digest. This can come in handy in attempting to derive consequences of Peano Arithmetic or of Robinson's Q, but the principles of reasoning also apply in the metalanguage. There is also a freshly written article on Gödel's Theorems in the Stanford Encyclopedia of Philosophy. I haven't scourged through the internet for other links, though. Should you happen across something that looks interesting/illuminating (and is not bungled), please tell me. Lecture SlidesI also have a batch of lecture slides interweaving material from Enderton and Smith, but also starting with a brief review of elementary logic and basic properties of mathematical theories.
HomeworkI will try to give assignments as frequently as possible. For the nitty-gritty of the two theorems, we will first follow Smith. Unfortunately, the Smith text contains no exercises, and Enderton and Smith differ enough in their choice of systems that many if not most of the problems from Enderton cannot be taken over directly to Smith. There are a few homework problems intended to accompany the text on Smith's website for the book, but these are only for the first few chapters, material that we will largely presuppose. (Besides, he gives the solutions.) Consequently, I'll have to invent homework exercises as we go along. ExamsThere will be an individual oral final exam TBA during reading period - final's week. Grading PolicyThe policy is to be fair. The Riot Act re Academic EthicsFrom me: Although you should not be barred from discussing issues and problems in this course with fellow students, homework shall not be done collaboratively. From the University: “The strength of the university depends on academic and personal integrity. In this course, you must be honest and truthful. Ethical violations include cheating on exams, plagiarism, reuse of assignments, improper use of the Internet and electronic devices, unauthorized collaboration, alteration of graded assignments, forgery and falsification, lying, facilitating academic dishonesty, and unfair competition Report any violations you witness to the instructor. You may consult the associate dean of students and/or the chairman of the Ethics Board beforehand. See the guide on "Academic Ethics for Undergraduates" and the Ethics Board web site http://ethics.jhu.edufor more information.” |
||
|
|