|
|
|
|
Math 160 Syllabus (Mathematical Logic 1) Winter 2006, 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, even "easy" ones like number theory. 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. This mathematical concept is called "consistency" and we will discuss it at length. 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? This mathematical concept is called "decidability" and we will discuss it at length also. The young austrian logician Kurt Goedel was able to settle these questions in the early 1930s with his famous incompleteness theorems. These results are stunning, beautiful and far-reaching. Some consider Goedel as the most important logician since Aristotle. Goedel even made the Time Magazine Most influential 100 person list for the 20th century as the most influential mathematician of the 20th century. Adding to the interest in Goedel are compelling personal stories about him and his life. From the algorithmic nature of proofs also arises the notion of computability and it really was logicians like Goedel, Turing, Church, Kleene, Rosser and von Neumann who are the fathers of modern computer science. We will discuss all these issues and hopefully have a lot of fun tracing some of the most interesting and intriguing developments in mathematical logic and mathematics during the last century. Your Teachers
Class Meetings
More formally speaking: Course Goals This is the first of a two quarter sequence. The goal is to get to Goedel's Incompleteness Theorems. This means we will cover 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 is alot more intricate and 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. This is cool stuff. 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. If all goes as planned, Math 161 will be offered in Spring of 2007. 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. For those of you that like to investigate on your own and like to write, I am open to have a major component of your grade be based on a written paper. Ask me if you are interested. 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 There are some books placed on reserve for Math 160 at the science library reserves desk. I will also regularly give you additional materials to read.
|
Copyright © 1997-2008 by Frank
Bäuerle, Ph.D., UC Santa Cruz.
|
| You are visitor # | since the beginning of winter quarter 2002 |
