# Enderton Logic Homework

## Math 457, Introduction to Mathematical Logic, Spring 2014

## Course details

Instructor: | Jason Rute |

Email: | |

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

### 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)
- More to be added...

### Mathematics in general

## Homework Assignments

Please read my instructions for 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
- p. 27, Exercises 2, 3, 4, 6, 7, 8, 9, 10, 12, 14
- Notes on HW 2

- 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
- 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) |

Exercises listed in parentheses ( ) are recommended but be handed in.

*Section 1.1:* (1), (2), 5; *Section 1.2:* (2), 3, (4), 5, 8a, (9), (12), 15;

*Section 1.3:* 1 only for group 3, 2, (4), (6); *Section 1.4:* (2)*Section 1.5:* 1a, 3, (5), (6), 9a, (9b), (10)

*Section 1.7:* 12a,b, (12c); *Section 1.7*:* A: Prove that soundness is equivalent to the statement "every satisfiable set of formulas is consistent."

B: Prove that completeness is equivalent to the statement "every consistent set of formulas is satisfiable".*Section 2.1:* 2, 3

*Section 2.2 to hand in:* 3, 5, 8, 9, 18 a; *Section 2.2 recommended:* (1), (2), (4), (11), (12), (14), (15), (16), (18 b), (21), (26), (28)

*Section 2.5:* 4, 6*Connecting chapter 2 and ZFC:* The Axiom of Extensionality (AxI) can be written as

.

Prove that the converse is always true. Namely, prove that for any structure for the language of set theory, the sentence

is satisfied in the structure.*Chapter 3 of Moschovakis on page 30: x3.1, x3.2 parts 1-3 *

## 0 Replies to “Enderton Logic Homework”