|
|
|
|
Math 160 Syllabus (Mathematical Logic 1) Winter 2005, UCSC Here's why you should take this course: Statement 1: Both of these two statements are
false. Assuming that a statement is either true or false (and not neither or both), what happens if the first statement is true? What does this imply for the second statement? Little puzzles like the above have profound consequences when one tries to get to the bottom of notions like "truth", "provability" and such. One of the great strengths of Mathematics is that once you have a proof of a statement, it becomes certain, or irrefutable. But what does this certainty rest on? Any proof needs assumptions. Are there, and if so, what are universal truths that can serve as such assumptions? Take an example from Geometry: Do parallel lines intersect? Another basic question regards the correctness of our systems. Can we be sure that we will never be able to prove incorrect statements like "0=1"? Can we possibly even be able to prove that? This is crucial, since once you can prove something that is obviously false, you can prove anything, which of course renders the system useless. Another fundamental question is: Does every mathematical question have an answer in the form of a proof? As an example, can we be sure that a proof or counterexample to Goldbach's conjecture can be found? Could it be that one day a clever programmer invents a machine (theorem prover) that can answer all mathematical questions? From the algorithmic nature of proofs also arises the notion of computability and it really was logicians like Goedel, Turing and von Neumann who are the fathers of computer science. We will address these issues and hopefully have a lot of fun tracing some of the most interesting and intriguing developments in mathematical logic during the last century. Your Teachers
Class Meetings
Course Goals This is the first of a two quarter sequence. This quarter we will get through the first two chapters in the textbook. Time permitting, we will start with Chapter 3 material. Chapter 1 deals with propositional calculus (sentential logic). This should be familiar to you. We will follow the tradition of introducing the main concepts in this arena which is more readily understood (and where it is a lot easier to prove things.) Chapter 2 discusses the main principles of predicate calculus (first-order logic). We will cover the basic definitions, consequences and the soundness, completeness and compactness theorems in detail. We will also discuss some model-theoretic results. The real goal for this part of the sequence lies in Goedel's incompleteness theorem which is discussed in detail in Chapter 3. We will try to get as far as we can to cover some of the details of Goedel's proof. In particular, Chapter 3 is about the limitations of the system. Here we will trace Goedel's ideas that lead to the proof of his incompleteness theorem: If number theory makes sense, then for any finitely axiomatized system for number theory there are true facts that cannot be proven in this system. We will cover as much detail of the proof as our time allows. We will also discuss the meaning and historical importance of this theorem as well as some further incompleteness results. The second quarter, Math 161, will be dedicated to set theory. More details on that when we get closer towards Spring quarter. Requirements To be eligible to enroll in Math 160, you must have taken and passed Math 100 or CSE 101 or get my approval. Talk to me if you have any questions about that. Title: Introduction to Mathematical Logic,
Second Edition Available for purchase at the Bay Tree Bookstore. Exams & Grading Policy There will be a midterm (30%) and a comprehensive final (40%). Weekly homework assignments are also a big part of your grade (30%). Other factors such as participation in class and section will also affect your final grade. Homework Homework is assigned at the end of each lecture from the sections covered. Homework will be collected and returned either in section or in class. See the class web site at http://count.ucsc.edu/~bauerle/Default.htm for the list of problems and other information. Collaboration Collaboration is strongly encouraged in working on problems, but can not be allowed on exams. Therefore it is important (and required) that each student turn in their own homework assignments. Here is a couple of links to the author's web site for the book. Reading I will give you a list of recommended books shortly, and place them at the science library reserves.
|
Copyright © 1997-2008 by Frank
Bäuerle, Ph.D., UC Santa Cruz.
|
| You are visitor # | since the beginning of winter quarter 2002 |
