Logic and Foundations

Code:

M3009

Acronym:

M3009

Level:

300

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2021/2022 - 1S

Active?	Yes
Responsible unit:	Department of Mathematics
Course/CS Responsible:	Bachelor in Mathematics

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	4	Official Study Plan	3	-	6	56	162
L:F	0	Official Study Plan	2	-	6	56	162
			3
L:G	0	study plan from 2017/18	2	-	6	56	162
			3
L:M	31	Official Study Plan	2	-	6	56	162
			3
L:Q	0	study plan from 2016/17	3	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

To get acquainted with basic concepts of logic and set theory. To understand the importance of Gödel's completeness and incompleteness theorems, as well as the need for axiomatic set theory.

Learning outcomes and competences

Capability of solving problems in the area. Autonomy on solving exercises.

Working method

Presencial

Program

1. PROPOSICIONAL CALCULUS: semantics, syntax, completeness and compactness

2. FIRST ORDER LANGUAGES: functional and relational symbols, constants, languages with equality, terms and formulae

3. SEMANTICS: structures, interpretations of variables, semantic consequence, valid formulae

4. SYNTAX: axioms and inference, syntactic consequence, consistency, prenex normal form

5. COMPLETENESS: completeness and compactness theorems for first order logic

6. SECOND ORDER LOGIC: second order logic and monadic second order logic, Rabin's tree theorem

7. GÖDEL'S INCOMPLETENESS THEOREMS: significance of the incompleteness theorems, proof of a simplified version of the first theorem

8. CONSTRUCTION OF THE NATURAL NUMBERS: Peano's axioms, construction of the integers, construction of the rationals

9. CONSTRUCTION OF THE REAL NUMBERS: Dedekind cuts, reference to the construction based on Cauchy sequences

10. AXIOMATIC SET THEORY: paradoxes arising fron the intuitive concept of set, the Zermelo-Fraenkel axioms, the construction of natural numbers under this perspective

11. ORDINALS: well-ordered sets, transfinite induction, ordinals and their properties

12. THE AXIOM OF CHOICE: axiom of choice, several equivalent formulations, a nonconsensual axiom

13. CARDINALS: equipotence, finite and countable sets, the continuum hypothesis, Cantor-Schröder-Bernstein's Theorem, Cantor's Theorem, cardinal of a set

Mandatory literature

Almeida Jorge; Introdução à lógica
Ebbinghaus Heinz-Dieter 1939-; Mathematical logic. ISBN: 978-0-387-94258-2
Enderton Herbert B.; A mathematical introduction to logic
Oliveira A. J. Franco de; Teoria de conjuntos intuitiva e axiomática (ZFC)
Hrbacek Karel; Introduction to set theory. ISBN: 0-8247-8581-9
Mendelson Elliott; Introduction to mathematical logic

Teaching methods and learning activities

Presentation of results and examples by the lecturer. Exercises shall be proposed to the students in advance and discussed in the classroom.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Teste	100,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	106,00
Frequência das aulas	56,00
Total:	162,00

Eligibility for exams

No requisites.

Calculation formula of final grade

The syllabus will be divided into two parts. each one evaluated by a test worth 10 points.

The second test is held simultaneously with the first season exam. In the same occasion, it is possible to repeat the first test, and the marks obrtained prevail for those students wishing it.

First season exam:

1. The final mark is the sum of the marks obtained in each test, except possibly in the following case:

2. Marks above 18 require an extra proof (oral or written).

Second season exam:

1. In the second season exam, students may repeat both tests or just one of them (except when they are just trying to improve their mark).

2.The mark of one (but only one) of the tests may be replaced a posteriori by the mark obtained in the respective test of the first season, in the version which favours most the student (except when they were approved before).

3. The final mark of the second season is the sum of the marks obtained in both tests, rounded to integers, except possibly in the following cases:

4. Students having obtained a mark equal or above 8,0 and below 9,5 have access to a complementary proof to decide if they are approved (with 10 points) or if they fail (with 8 or 9 points).

5. Marks above 18 require an extra proof (oral or written).