Math 125A

Mathematical Logic, Part I.

University of California, Berkeley.
Department of Mathematics.

Fall 2013
Instructor: Antonio Montalbán
E-mail: antonio@math.berkeley.edu
Office hours: Wednesdays 4:30-5:30pm and Thursdays 4-5pm, in either Evans 721, or Evans 727. (See below for schedule during RRR week).

Time and place: Mondays, Wednesdays and Fridays 3:00-4:00pm in 289 Cory.

Textbooks: Peter G. Hinman, Fundamentals of Mathematical Logic.
Joe Mileti, Mathematical Logic for Mathematicians, Part I.
Helbert B Enderton, A mathematical introduction to logic.
Web page: www.math.berkeley.edu/~antonio/math125A

Announcements:

Office hours / Review Sessions during RRR week: Monday December 9 and Friday December 13 at regular class time, in our regular classroom.

Final Exam: The final exam will be on Tuesday December 17th, from 7pm to 10pm

Soultions for Midterm 1

Solutions for Midterm 2.

Homework.

HW1, due on Wednesday September 11th at class time.
HW2, due on Wednesday September 18th at class time. Solutions
HW3, due on Wednesday September 25th at class time. Solutions
HW4, due on Friday October 11th at class time. Solutions
HW5, due on Friday October 18th at class time. Solutions
HW6, due on Friday October 25th at class time. Solutions
HW7, due on Friday November 1st at class time. Solutions, Lemma on Elementary Extensions
HW8, due on Monday November 18th at class time. Here is a list of the rules for proofs in first order logic.
HW9, due on Monday December 2 at class time.
HW10, due on Friday December 6 at class time.

This course provides an introduction to mathematical logic. Topics include propositional and predicate logic and the syntactic notion of proof versus the semantic notion of truth, including soundness and completeness. We also discuss the Gödel completeness theorem, the compactness theorem, and applications of compactness to algebraic problems.

General Policy.

Homework: There will be a new homework set posted in this web page every 7 to 10 days. Homework will be due at the beginning of a class, and not later in the day. (You can always bring them earlier if you wish.) Late homework will NOT be accepted. However, the least grade will be dropped, so you're allowed to miss one homework. You may talk with others about the homework, but you have to write up your own solutions independently on you own words.

Two midterms: The midterms will be on Monday September 30th, and Monday November 4th during class time.

Final Exam: The final exam will be on Tuesday December 17th, from 7pm to 10pm.
These time and dates are not flexible.

The final grade will be calculated using the following proportions: 1/5th from the homework altogether, 1/5th from each midterm and 2/5th from the final exam.

What is a proof?

You are expected to have experience with abstract mathematics before taking this course. If you need to brush up on notation Introduction to math notation by George M. Bergman will help. You also want to make friends with equivalence relations (for example, here) and with basic naive set theory (Chapter 0 of Enderton).

Most of the problems in this course will ask you to "prove" something, that is, to give a convincing explanation of why this something is true. At best, your proofs should look like the ones in your textbook. In particular:

Proofs are made of complete, grammatically correct sentences.
All variables that appear in the proof either appear in the statement being proved, or are clearly introduced somewhere in the proof with a "let".
Each statement either clearly, logically follows from previous statements (and that logic is explained), or is introduced with an explicit purpose (e.g. "suppose towards contradiction that..." or "the inductive hypothesis is...")
Anything that is not proved is cited, by its common name (e.g. the Fundamental Theorem of Arithmetic) or by reference to our textbook (e.g. Proposition 4 on p. 10)

The point of the proof is not to demonstrate to the grader that you understand the ideas in the problem, but to explain the solution to someone else in the class who has not thought about this particular question, and to whom you can only write, not speak. In particular, what I write on the board during lecture does not constitute written proofs - it is quite meaningless without the things I say.

Responsibility. On the most basic level, it is your responsibility to know about all assignments and deadlines and to show up for exams, and to make any special arrangements necessary, from arranging time to meet outside office hours to knowing when your drop deadline is. You are also responsible for your learning, from knowing what material has been covered to making sure you understand that material. The lectures will not cover everything; the homeworks will not cover everything; the textbook is the closest to covering everything. You will certainly have to learn some things on your own, either from the textbook or really on your own. Some of the material this course covers is genuinely difficult: you will probably not get it on the first try; that's ok. To maximize the number of tries, read the textbook before the lecture, noting the parts you don't understand; then come to lecture and pay special attention to those parts and ask lots of questions; then read through the book again and you will discover new subtleties you don't quite get. By this point, two or three weeks after meeting the concept for the first time, you should be comfortable with it. The bottom line is, your job is to acquire knowledge, not simply to follow my instructions. This course is graded on accomplishment, not effort.
Scholarship. Whatever you do with the rest of your life, in this course you are acting as a mathematics scholar, grappling with ideas that are new and confusing to you. Thus, your natural state is confusion: the moment you understand something, you move on to the next topic. Progress is measured by being confused about different ideas over time. So, what do you do with a confusing definition or theorem or proof? First, you make sure you understand each word and symbol that appears in it. Then you try to think of explicit examples. For a definition, look for things that satisfy it, as well as for things that don't. For a theorem, look for an example that satisfies the hypothesis and see that it satisfies the conclusion, and then for some examples that don't satisfy the conclusion and see which hypotheses they fail. Similarly, to understand a proof, it is often helpful to go through it with a specific example in hand; a non-example that fails some of the hypotheses will make it easier to see where the proof needs those hypotheses, i.e. breaks without them. The best way to understand a proof is to completely forget it and then try to prove the result yourself; this is also the slowest way. The next step is to ask why this particular definition was chosen, or why the theorem was stated in this particular way. Varying a definition, you may find equivalent definitions, stupid definitions, or new interesting concepts. Varying a theorem, you will find many false statements, some true generalizations, and occasionally an entirely new result.
Writing. This is a writing-intensive course. Almost all problems on homeworks and exams require explanation and justification; these should be written out in words, in complete sentences. Ideally, your writing should closely resemble the proofs and examples in our textbook.
Cheating. Please don't. If you are writing down ideas somebody else told you and not mentioning this fact, you are cheating. If you are writing down words somebody told you, and you could not rewrite the solution in different words or explain it to another student in the class, you are cheating. Rules around exams are not arbitrary hurdles I place in your way.
Lectures Attendance is not mandatory but strongly recommended. Most of the material covered in lecture is in the textbook (though sometimes in much less detail), and most of the announcements will eventually be posted on this course webpage. However, you are responsible for the exceptions, so if you miss a class, talk to someone who didn't. You will also find the class much much harder if you do not come to lecture. The best use of lecture is to focus all of your attention on it, for the entire duration. If you are not doing this, please do not disturb the people who do. The best way to stay focused in class is to get involved. If something doesn't quite make sense, ask about it! I like questions! I like stupid questions, too - for every brave soul willing to ask one, there's ten shy confused students thinking the same thing. If you think there's a typo on the board, you may well be right - ask about it! And if it's not a typo, your confusion will not get cleared up if you don't ask. Clearing up confusions is what this is all about.