MATH33001/43001 - 2010/2011

 

Specification

Aims

• To show how reasoning and the notion of a valid argument can be formalized.
• To provide practical means of demonstrating the validity, or otherwise, of arguments or assertions.
• To provide, via the Completeness Theorems, a broader picture and understanding of the nature of mathematics.
• To instill an understanding of syntax and semantics and the roles they play.

Brief Description of the unit

In our everyday lives we often employ arguments to draw conclusions. In turn we expect others to follow our line of reasoning and thence agree with our conclusions. This is especially true in mathematics where we call such arguments ‘proofs’. By why are such arguments or proofs so convincing, why should we agree with their conclusions? What is it that makes them ‘valid’?
In this course we will attempt to formalize what we mean by these notions within a context/language which is adequate to express almost everything we do in mathematics, and much of everyday communication as well. In so doing we will be led to proving Kurt Gödel’s Completeness Theorem (1929) which, by clarifying the relationship between proof and truth, is one of the two most philosophically important results in mathematics.

Learning Outcomes

On successful completion of the course the students will

• appreciate how patterns of reasoning can be formalized semantically and syntactically;
• understand the relationship between truth and proof;
• in simple cases be able to construct formal proofs;
• in simple cases be able to demonstrate, or contradict, the validity of an argument by semantic means.

Future topics requiring this course unit

MATH43042 Gödel's Theorems, MATH43052 Model Theory.

Syllabus

The course will cover the topics listed below. The difference between the MATH33001 and MATH43001 versions of the course material is that the latter will require some additional reading (usually of the proofs) related to the starred topics.

• Informal examples of valid arguments [2 lectures]
• Relational languages, formulae, proof by induction on the length of a formula. [2 lectures]
• Relations, structures, interpretations [3 lectures]
• Truth in an interpretation, logical consequence, many examples [3 lectures]
• Logical equivalence, the Prenex Normal Form Theorem* [2 lectures]
• Rules of proof, formal proofs [4 lectures]
• The Correctness, Completeness and Compactness Theorems for relational languages and applications thereof [7 lectures]
• Languages with functions and constants, terms, interpretation of terms, the Correctness*, Completeness* and Compactness* Theorems for such languages [4 lectures]
• Languages with equality, the equality axioms, normal structures, the Correctness*, Completeness* and Compactness* Theorems for languages with equality. Application of the Compactness Theorem to non-standard models of arithmetic. [5 lectures]
• Revision [1 lecture]

Textbooks

Self contained course notes will be provided. The following also give well written accounts (though using some different notation and order of presentation):

• Enderton, Herbert B., A Mathematical Introduction to Logic. Second edition. Harcourt/Academic Press, Burlington, MA, 2001.
• Mendelson, E. & Rosen, K.H., Introduction to Mathematical Logic. Fifth edition. CRC Press, 2009.

Teaching and learning methods

A complete set of notes plus examples sheet(s), solutions to examples and take home tests will be available on the web. There will be three lectures a week including the opportunity to ask class questions about the examples sheets. Individual help with the course and examples will also be available at two office hours.
MATH43001 students will be expected to study all the material in the notes, which will require additional reading since some proofs will not be presented in the lectures. Mainly this will happen towards the end of the course (see the starred material in the syllabus above) so MATH43001 students should either read ahead or anticipate a higher workload at that time.
Overall MATH33001 students should expect to do at least 4 hours of private study on this course per week and MATH43001 students 6 hours per week.

Assessment

Coursework: One take home test due in week 5 and a second in week 8, each with a weighting of 10%. The courseworks for levels 3 and 4 will be different.

End of semester examination: two hours (MATH33001), two and a half hours (MATH43001); weighting 80%

to the top

Arrangements