Class 1 (9/3/09): We learned about the history and motivation behind math logic, defined our first model (sentential logic). We learned its syntax and how its well-formed formulae are built up recursively. We also studied the "truth-value" function, nu, how it is defined using recursion from the truth value of sentence symbols, and the method of truth tables.
Class 2 (9/8/09): We completed the definitions of the syntax and semantics of sentential logic, then introduced tautological implication, did some examples, and proved its relationship to formal implication.
Homework (due Thursday, 9/24/09):
Problems 1.1.2,3,5
1.2.1,3,5,7,8,9,12,13
1.5.1,3,4
Class 3 (9/10/09): We defined a set of sentential connectives as "complete" if it can express a wff corresponding to any boolean function. We showed that {not, and, or} is complete, using disjuctive normal form (DNF), and that {and, implies} is not complete, using induction on formulas to show that every formula is assigned T if every sentence symbol is assigned T.
We then explored the relation of sentential logic to the notion of a computer (algorithm), noting that every algorithm can be thought of as formulas in sentential logic, and introduced the notions of decidable and enumerable (=semidecidable).
Class 4 (9/15/09): We proved compactness: any finitely satisfiable set of wffs is actually satisfiable. The proof used a unique argument involving building up a maximal satisfiable set of wffs, then using induction on formulas.
Class 5 (9/17/09): After proving Corollary 17A to compactness, we used this to show that if a set of wffs is enumerable, then so are it's consequences (we did this by constructting a semidecision procedure).We then did exercises 3,4,5,and 6 (soundness of deductions) from section 1.7
Class 6 (9/22/09): We did exercise 7 from section 1.7 (completeness), then began our study of first-order logic by examining its syntax.
MIDTERM EXAM: In class Thursday, October 8
Class 7 (9/24/09): We practiced some translations from English to a first-order language and back. We then started thinking about the semantics of first-order wffs by developing our intuition about models.
Class 8 (9/29/09): We formally defined what a model is for a first-order language, and what it means for a wff to be "true in a model A with variable assignment s". The first step was to extend s to assign a member of the universe to all terms, not just variables. We also discussed the role of = as a logical symbol, not a predicate.
Class 9 (10/1/09): We proved that whether a wff is satisfied in a model A with a variable assignment s depends only on what s assigns to the free variables in the wff. Therefore, if the wff is a sentence (no free vars), the inclusion of a variable assignment is superfluous.
Homework (due Tuesday, 11/3/09):
Problems 2.1.2,4,5,6
2.2.1-4
(more to come)
Class 10 (10/6/09): We studied logical implication through examples
Class 11 (10/8/09): Midterm
Midterm Solution Key:
Problem 1
Problem 2
Problems 3 and 4
Problems 5 and 6
Class 12 (10/15/09): We studied definability: In a structure and of a class of structures. We also defined homomorphisms between structures.
More homework (due Tuesday, 11/3/09):
Problems 2.2.8,9,11
Problems 2.4.2,6,7,10
Class 13 (10/15/09): We studied the homomorphism theorem, especially the results when h is one-to-one/onto for wffs with quantifiers/equality symbol. We also saw how to use an automorphism h to show a subset of the universe of a structure is not definable in that structure (it is not invariant under h). Finally we began talking about deduction and metatheorems, and listed the 6 groups of logical axioms.
Class 14 (10/120/09): We continued to study deductions in first-order logic, doing some examples
Class 15 (10/22/09): We learned more metatheorems, and formed a general strategy for proving deductions using metatheorems
Class 16 (10/27/09): We prove the soundness of deductions, which followed from the validity of each axiom in the 6 groups, and the fact that Modus Ponens preserves validity.
Class 17 (10/29/09): We understood the first-order compactness theorem, and how it follows easily from completeness.
Class 18 (11/3/09): We spent most of the class doing homework problems, then briefly introduced the (long) proof of the completeness theorem.
Class 19 (11/5/09): Proof of the completeness theorem (cont.).
Homework (due Tuesday, 11/24/09):
Problems 2.5.3,4,6,7
Class 20 (11/10/09): After finishing the proof of completeness, we started thinking about the "big picture": the relationships between axioms, theories (sets of sentences closed under logical implication), models and classes of models. We began by showing that the class of finite models is not defined by any set of axioms, but that the class of infinite sets is defined by a certain infinite set of sentences.
Class 21 (11/12/09): We resumed the study of the last class, showing the LST theorem: any theory (in a countable language) which has an infinite model, also has models of any infinite cardinality. This led to a discussion of the Skolem "paradox". We also showed that the theory of a finite structure is decidable.
More homework (due Tuesday, 11/24/09):
Problems 2.6.2,3,8
Class 22 (11/17/09): We continue from last time by considering the sentences for which there is a finite model, the sentences which are true in every finite model, and so on, for infinite models as well. We saw that these sets of sentences are related by being subsets/complements of each other, which allowed us to deduce their computability properties. We also showed that an axiomatizable theory was e.e., and a complete axiomatizable theory was decidable. Finally we discussed categoricity (having only one model, up to isomorphism, of a given size) and proved the Los-Vaught test. As an example, we showed the theory DLONE (dense linear ordering with no endpoints) was omega-categorical (the ordering of the rationals is the only model).
Class 23 (11/19/09): We breezed through sections 2.7 and 2.8, learning only the ideas behind non-standard analysis and interpretations, and touched on the arithmetical hierarchy of sets of natural numbers (according to the number of alternations of quantifiers). We then began Chapter 3 by seeing three versions of the proof that any decidable set of axioms for the arithmetic of the natural numbers is incomplete. Each version was more detailed than the last, but each constructed a wff which demonstrated its own unprovability from the axioms.
Class 24 (11/24/09): We reviewed the amazing incompleteness theorem from last time, but mostly did homework problems.
Class 25 (12/1/09): I talked about what will be covered in the rest of the course, then introduced the idea of a representable set of natural numbers (given by a wff with one free variable in a finitely axiomatizable theory), and argued that it is equivalent to such a set being decidable (forward direction based on being able to decide if any instance of the wff is a consequence of the axioms, reverse based on empirical evidence). We then studied the theory of the natural numbers with zero and successor (section 3.1), finding a set of axioms for it which is complete, using L-V test, and thus decidable.
Class 26 (12/3/09): We saw another way to prove completeness: the elimination of quantifiers method, which shows that every sentence is DECIDABLY equivalent to one without quatifiers, which we can then decide the truth of. We started discussing the theory of the natural numbers with zero, successor, and their ordering.
Class 27 (12/8/09): We will prove elimination of quantifiers for the theory of the natural numbers with zero, successor, and their ordering, showing it is finitely axiomatizable. We will briefly study other intermediate arithmatics, such as Presburger's and Robinson's, before coming back to the full theory of arithmetic. We will also hear about some paradoxes from the class.
Class 28 (12/10/09): .