Course Title | ## Set Theory and Logic | ||

Course Code | ## MH4301 | ||

Offered | Study Year 3, Sem 1 | Study Year 3, Sem 2 | Study Year 4, Sem 1 | Study Year 4, Sem 2 | ||

Course Coordinator | Ng Keng Meng (Assoc Prof) | kmng@ntu.edu.sg | 6513 8656 |

Pre-requisites | (MH1300 and MH3100) OR (MH1300 and MH2220) | ||

AU | 4 | ||

Contact hours | Lectures: 39, Tutorials: 12 | ||

Approved for delivery from | AY 2023/24 semester 1 | ||

Last revised | 6 May 2022, 14:21 |

This course aims to provide you with a basic understanding of formal mathematical logic and axiomatic set theory. Mathematical logic provides a foundational basis for the practice of mathematics, and axiomatic set theory provides a rigorous justification for the existence of mathematical objects and structures. This course will equip you with the awareness of foundational issues in mathematics. It will allow you to understand how proofs in mathematics are rigorously defined, and how the concepts of “truth” and “provability” interact. It will also enable you to judge which objects and processes in mathematics are well-defined, and which ones require further axiomatic justifications. It is aimed at increasing awareness among mathematics students for why the common practices in mathematics are rigorously grounded, and which ones are ill-defined and should be avoided.

This course is aimed at 3rd and 4th year students interested in learning about the foundations upon which all of mathematics is built upon, particularly mathematics and computer science students who are interested in the theoretical aspects of mathematics. This course is also crucial for students intending to pursue further studies in theoretical mathematics.

Upon successfully completing this course, you should be able to:

- Identify the language of propositional logic.
- Explain how truth and proofs work in propositional logic.
- Explain the soundness and completeness theorems in propositional logic.
- Apply the compactness theorem in propositional logic.
- Explain language of first-order logic.
- Derive the relationship between truth and proofs in first-order logic.
- Relate the concept of a first-order structure to the commonly studied objects in mathematics.
- Explain the workings the compactness theorem in first-order logic, particularly to non-standard structures.
- Discuss the issues of definability and judge how this relates to the definition of objects commonly used in mathematics.
- Describe the formal axioms of Zermelo-Fraenkel set theory.
- Explain Godel’s Incompleteness Theorems and the impact it has on mathematics.
- State the use of ordinals and cardinals, as well as well-orderings.
- Apply transfinite induction and recursion to mathematical problems.
- Apply the Axiom of Choice to different areas of mathematics.
- Justify the existence of the natural numbers, the real numbers, and the other commonly studied objects in mathematics.

The language of propositional logic.

Truth assignments and Boolean functions.

Induction and recursion.

The proof system used in propositional logic.

The Soundness Theorem, Completeness Theorem and compactness Theorem for propositional logic.

The language of first order logic.

Truths and models

The proof system used in first order logic.

The Soundness Theorem, Completeness Theorem and compactness Theorem for first order logic.

The axioms of set theory.

Relations, functions and orderings.

Natural numbers.

Equipotent sets and bijections.

Ordinals and well-orderings.

The axiom of choice.

Component | Course ILOs tested | SPMS-MAS Graduate Attributes tested | Weighting | Team / Individual | Assessment Rubrics |
---|---|---|---|---|---|

Continuous Assessment | |||||

Tutorials | |||||

Homework | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 | 1. a, b, c2. a, b, c3. a5. a | 15 | individual | See Appendix for rubric |

Mid-semester Quiz | |||||

Mid-term Examination 1 | 1, 2, 3, 4, 5, 6, 7, 8, 9 | 1. a, b, c2. a5. a | 25 | individual | See Appendix for rubric |

Examination (2 hours) | |||||

Final Examination | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 | 1. a, b, c2. a5. a | 60 | individual | See Appendix for rubric |

Total | 100% |

These are the relevant SPMS-MAS Graduate Attributes.

## 1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

b. Formulate mathematical statements precisely using rigorous mathematical language

c. Discover patterns by abstraction from examples

## 2. Creativity

a. Critically assess the applicability of mathematical tools in the workplace

b. Build on the connection between subfields of mathematics to tackle new problems

c. Develop new applications of existing techniques

## 3. Communication

a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience

## 5. Character

a. Act in socially responsible and ethical ways in line with the societal expectations of a mathematics professional, particularly in relation to analysis of data, computer security, numerical computations and algorithms

For the midterm and final exams, feedback on the common mistakes are given on NTULearn after the grades are announced. This includes the examiner's report which will be released on NTU Learn after the results are announced. Common mistakes are often repeated and addressing this will be important for achieving the learning outcomes 1-15. For the homework assignment, the solutions will be discussed during the next tutorial session and feedback on common mistakes will be given then.

Lectures (39 hours) | Present the key ideas behind mathematical concepts. Present important steps used to solve different types of problems. |

Tutorials (12 hours) | Develop proficiency in problem solving skills. Reinforce concepts already covered in the lectures. Gives an opportunity for weaker or more reserved students to clarify doubts. |

H. B. Enderton - A Mathematical Introduction to Logic (3rd Edition). Academic Press. ISBN-13:978-0123869777

K. Hrbacek and T. Jech - Introducton to Set Theory (3rd Edition). Marcel Dekker. ISBN-13: 978-0824779153

(1) General

You are expected to complete all assigned pre-class readings and activities, attend all tutorial classes punctually and take all scheduled assignments and tests by due dates. You are expected to participate in all tutorial discussions and activities.

(2) Absenteeism

Absence from the midterm without a valid reason will affect your overall course grade. Valid reasons include falling sick supported by a medical certificate and participation in NTU’s approved activities supported by an excuse letter from the relevant bodies. There will be no make-up opportunities for CA components.

All project assignments must be submitted on time. Failure to do so will affect your score.

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Instructor | Office Location | Phone | |
---|---|---|---|

Ng Keng Meng (Assoc Prof) | MAS-05-09 | 6513 8656 | kmng@ntu.edu.sg |

Week | Topic | Course ILO | Readings/ Activities |
---|---|---|---|

1 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

2 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

3 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

4 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

5 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

6 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

7 | Mathematical Logic | 1, 2, 3, 4, 5, 6, 7, 8, 9 | H.B. Enderton – Sections 1.0 to 2.5 |

8 | Set Theory | 10, 11, 12, 13, 14, 15 | Hrbacek and Jech – Chapters 1-6,8 |

9 | Set Theory | 10, 11, 12, 13, 14, 15 | Hrbacek and Jech – Chapters 1-6,8 |

10 | Set Theory | 10, 11, 12, 13, 14, 15 | Hrbacek and Jech – Chapters 1-6,8 |

11 | Set Theory | 10, 11, 12, 13, 14, 15 | Hrbacek and Jech – Chapters 1-6,8 |

12 | Set Theory | 10, 11, 12, 13, 14, 15 | Hrbacek and Jech – Chapters 1-6,8 |

13 | Set Theory | 10, 11, 12, 13, 14, 15 | Hrbacek and Jech – Chapters 1-6,8 |