# Math 457, Introduction to Mathematical Logic, Spring 2014

## Course details

 Instructor: Jason Rute Email: To reduce unsolicited e-mail this address is javascript encoded. Note to self: Use JavaScript Escape Unescape Converter Tool on the web. Lecture: MWF 10:10 am - 11:00 am 208 Thomas Building Textbook: A Mathematical Introduction to Logic, 2nd Edition by Herbert B. Enderton(Note, there is an errata list.) Office Hours: MWF 11:10 - 12:00 pm (after class) By appointment (email me to set up a meeting). 421 McAllister Building (feel free to drop by unannounced).

See the course syllabus for additional details. Grades will be recorded on ANGEL.

## Supplementary resources

### Mathematical Logic (Fun)

Mathematical logic has captured the public interest. These popular science resources are not mathematically deep, but they are interesting, fun, and provide a general overview.
• Logicomix (highly recommended, although not entirely historically accurate.)
• Gödel, Escher, and Bach (a meandering path through logic, zen koans, art, music, and meta-ness)

## Homework Assignments

• Homework #1, Due Wed, Jan 29
• Learn and write both proofs of the Induction Principle (p. 18),
• p. 19, Exercises 1, 2, 3, 4, 5
• Homework #2, Due Mon, Feb 3
• Homework #3, Due Mon, Feb 10
• Section 1.3 #1, 2, 3
• State and prove the recursion theorem
• Homework #4, Due Mon, Feb 17
• Section 1.5 #6, 9
• Section 1.7 #1, 2, 3, 4, 5, 6, 7
• State and prove the compactness theorem
• (Note: Some parts of the compactness theorem are HW problems. Just say "by HW problem #... it follows that ...".)
• Homework #5, Due Mon, Mar 3
• Homework 5
• Note: There was an error in the original assignment. I meant #8, 9, 10, 11, not #7, 8, 9, 10
• Homework #6, Due Mon, Mar 17 (after Spring Break)
• Section 2.1 (p.79) #1 - 10
• #1-8 are all about translating sentences to and from first order logic.
• As for #10, just say which variables are free and why). (I honestly don't know what the first part of the problem is asking.)
• Homework #7, Due Mon, Mar 24
• Section 2.2 #1 - 10
• Homework #8, Due Mon, Mar 31
• Section 2.2 #11, 13, 14, 15, 16, 28.
• Give proof of homomorphism theorem.

## Schedule

The schedule below is an aproximation to the true schedule. The topics, course notes, and book sections may not line up exactly. Future topics are tentative and may change.
 Week Date Topics Book Sections Lecture Notes Remarks 1 01/13/14 Monday Introduction, language of sentential logic 1.1 notes 01/15/14 Tuesday Language of sentential logic 1.1 -- Substitute teacher 01/17/14 Friday Truth assignments 1.2 -- Substitute teacher 2 01/20/14 Monday MLK Jr Day (No class) 01/22/14 Wednesday Truth assignments 1.2 notes 01/24/14 Friday Truth tables, Polish notation, omitting parenthesis 1.2, 1.3 notes 3 01/27/14 Monday Some facts about |=, induction 1.2, 1.4 notes 01/29/14 Wednesday Induction 1.4 notes 01/31/14 Friday Induction 1.4 notes 4 02/03/14 Monday Induction and recursion 1.4 notes 02/05/14 Wednesday Recurion Theorem 1.4 notes 02/07/14 Friday Sequential connectives 1.6 notes 5 02/10/14 Monday Compactness, effectiveness 1.5 notes 02/12/14 Wednesday Effectiveness, basic set theory 1.7, 0, other notes 02/14/14 Friday Cardinality 0, other notes 6 02/17/14 Monday Cardinality and Axiom of Choice 0, other notes 02/19/14 Wednesday Review notes 02/21/14 Friday Midterm 1 (in class) solutions 7 02/24/14 Monday Languages of first order logic 2.0, 2.1 notes 02/26/14 Wednesday Languages of first order logic 2.1 02/28/14 Friday Structures and satisfiability 2.2 8 03/03/14 Monday Satisfiability of structures 2.2 03/05/14 Wednesday Models and Logical Implication 2.2 notes 03/07/14 Friday Logic Puzzles! N/A SB SPRING BREAK. NO CLASSES THIS WEEK. 9 03/17/14 Monday Definability within a structure 2.2 notes 03/19/14 Wednesday Definability within a structure 2.2 03/21/14 Friday Definability of classes of structures 2.2 notes 10 03/24/14 Monday Homomorphisms 2.2 notes 03/26/14 Wednesday Homomorphism theorem, non-definable relations 2.2 notes 03/28/14 Friday Deduction 2.4 notes 11 03/31/14 Monday Deduction 2.4 Combined with previous notes 04/02/14 Wednesday Review notes 04/04/14 Friday Midterm 2 (in class) solutions 12 04/07/14 Monday Deduction Examples 2.4 04/09/14 Wednesday Deduction rules 2.4 04/11/14 Friday Deduction examples and strategy 2.4 notes 13 04/14/14 Monday Deduction strategy and equality 2.4 notes 04/16/14 Wednesday Additional deduction rules 2.4 notes 04/18/14 Friday Soundness 2.5 notes 14 04/21/14 Monday Soundness 2.5 notes 04/23/14 Wednesday Completeness 2.5 notes 04/25/14 Friday Completeness 2.5 notes 15 04/28/14 Monday Compactness 2.5 notes 04/30/14 Wednesday Halting problem and Godel's incompleteness notes 05/02/14 Friday Review notes FW 05/05/2014 Monday Final Exam (6:50pm - 8:40pm, 208 THOMAS)