Logic and Foundations

Code:

M381

Acronym:

M381

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2014/2015 - 2S

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:M	16	Plano de estudos a partir de 2009	1	-	7,5	-
			2
			3

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

Calculation formula of final grade

Two (optional) tests will be held during the semester. Any student obtaining an average marking equal or superior to 10 at the tests needs not do the final exam. If they choose to do the exam at the normal season and present it for evaluation, their final marking will be the one obtained in the exam (the tests' marking having become irrelevant). All students failing to get over the threshold of 10 at the tests must do the final exam. A minimal mark of 8.0 is required in the exam to apply for a complementary oral exam. On any route (tests or final exam), final markings superior to 18 will require a complementary written exam.