In this course, we will introduce mathematical logic, which is a branch of mathematics. The main goal of this course is to
go through the proof of the Gödel's Completeness Theorem for first-order predicate logic.
We start with an introduction to syntax and semantics of mathematical logic in general and discuss their difference by raising some concrete examples from mathematics such as groups. Next, we introduce the meta-level and object-level of mathematics and mathematical logic and discuss their difference through some paradoxes caused by the confusion of the meta-level and object-level. Then we introduce first-order propositional logic with its proof system and standard semantics, and we prove that the standard semantics of first-order propositional logic is sound and complete to the proof system.
Finally, we introduce first-order predicate logic with its proof system and standard semantics, and we prove the Gödel's Completeness Theorem for first-order predicate logic, i.e., the statement that the standard semantics of first-order predicate logic is sound and complete to the proof system. In the proof of its completeness, we use Henkin's construction, which adds constants with desired properties (so-called Henkin constants) to obtain a model of a given consistent theory. Henkin construction is used in many occasions in model theory, a research area in mathematical logic.
We start with an introduction to syntax and semantics of mathematical logic in general and discuss their difference by raising some concrete examples from mathematics such as groups. Next, we introduce the meta-level and object-level of mathematics and mathematical logic and discuss their difference through some paradoxes caused by the confusion of the meta-level and object-level. Then we introduce first-order propositional logic with its proof system and standard semantics, and we prove that the standard semantics of first-order propositional logic is sound and complete to the proof system.
Finally, we introduce first-order predicate logic with its proof system and standard semantics, and we prove the Gödel's Completeness Theorem for first-order predicate logic, i.e., the statement that the standard semantics of first-order predicate logic is sound and complete to the proof system. In the proof of its completeness, we use Henkin's construction, which adds constants with desired properties (so-called Henkin constants) to obtain a model of a given consistent theory. Henkin construction is used in many occasions in model theory, a research area in mathematical logic.
Through this course, students are expected to be acquainted with basics of mathematical logic such as follows:
1. Syntax and semantics, and the difference and connections between them
2. Meta-level and object-level of mathematics and mathematical logic and the difference between them
3. Proof system and its derivations in first order predicate logic
4. Henkin construction of models of a consistent theory in first order predicate logic
1. Syntax and semantics, and the difference and connections between them
2. Meta-level and object-level of mathematics and mathematical logic and the difference between them
3. Proof system and its derivations in first order predicate logic
4. Henkin construction of models of a consistent theory in first order predicate logic
- The students can make a distinction between syntax and semantics in mathematical logic by raising some examples for the difference.
- The students can make a distinction between the meta-level and the object-level of mathematics and mathematical logic by raising some example for the difference.
- The students can derive proofs of various valid statements in first-order predicate logic using its proof system introduced in the course.
- The students can use Henkin construction to obtain various kinds of models of first-order theories.
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1． | Guidance Syntax and semantics in mathematical logic |
Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 2． | Meta-level and object-level of mathematics and mathematical logic | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 3． | Useful facts about sets | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 4． | 1st-order propositional logic: Its language | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 5． | 1st-order propositional logic: Truth assignments | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 6． | 1st-order propositional logic: Induction and recursion | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 7． | 1st-order propositional logic: Completeness and Compactness | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 8． | 1st-order predicate logic: Languages | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 9． | 1st-order predicate logic: Truth and assignments | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 10． | 1st-order predicate logic: Proof system | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 11． | 1st-order predicate logic: Soundness and Completeness 1 | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 12． | 1st-order predicate logic: Soundness and Completeness 2 | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 13． | 1st-order predicate logic: Models of theories | Review the content of the lecture | 100minutes |
| Preparation of short reports | 90minutes | ||
| 14． | Nonstandard Analysis | Preparation of the final report | 300minutes |
| Total. | - | - | 2770minutes |
| Short reports | Final report | Total. | |
|---|---|---|---|
| 1. | 15% | 10% | 25% |
| 2. | 15% | 10% | 25% |
| 3. | 10% | 20% | 30% |
| 4. | 0% | 20% | 20% |
| Total. | 40% | 60% | - |
Short reports and final report.
The students will obtain the credits of the course if
a) they can make a distinction between syntax and semantics, and a distinction between the meta-level and object-level of mathematics and mathematical logic by raising some examples,
b) they can derive proofs of various valid statements in a given proof system of 1st-order predicate logic, and
c) they can use Henkin construction to obtain various kinds of models of 1st-order theories.
The students will obtain the credits of the course if
a) they can make a distinction between syntax and semantics, and a distinction between the meta-level and object-level of mathematics and mathematical logic by raising some examples,
b) they can derive proofs of various valid statements in a given proof system of 1st-order predicate logic, and
c) they can use Henkin construction to obtain various kinds of models of 1st-order theories.
A Mathematical Introduction to Logic, Second Edition by Herbert Enderton
ISBN-13 : 978-0122384523
ISBN-13 : 978-0122384523
It is required to have knowledge of and familiarity with basic mathematical structures such as groups, rings, and fields.
Also, familiarity and solid understanding of mathematical induction is necessary.
- By appointment. Contact e-mail address: ikegami@shibaura-it.ac.jp
- Course that cultivates an ability for utilizing knowledge
- Course that cultivates a basic problem-solving skills
| Work experience | Work experience and relevance to the course content if applicable |
|---|---|
| N/A | N/A |
Last modified : Fri Sep 03 04:04:56 JST 2021