MC144 Proof and Logical Structures

Next: MC145 Algebraic Structures and Up: Year 1 Previous: MC130 Mathematical Modelling

MC144 Proof and Logical Structures

Credits: 10

Convenor: Dr. J.F. Watters

Semester: 1 (weeks 1 to 6)

Prerequisites:
Assessment:	Coursework and classroom tests: 20%	One and a half hour exam: 80%

Lectures:	18	Classes:	none
Tutorials:	5	Private Study:	52
Labs:	none	Seminars:	none
Project:	none	Other:	none
Total:	75

Course Description

This module is intended to help students understand what is required when a proof is called for, to provide principles involved in the construction of proofs and to introduce the most frequently used strategies for proving theorems. At the same time, students will be introduced to the foundational concepts of sets, relations and functions, as well as the language of mathematics, these being essential for the study of mathematics at degree level.

Aims

This module's aims are:

to introduce the idea of mathematical proof;
to give experience of writing simple proofs and to teach the proper use of mathematical notation;
to extend usage of and familiarity with mathematical language;
to introduce the concepts of sets, relations and functions.

Objectives

To familiarise the student with the foundational concepts of mathematics.
To be able to use various proof strategies in simple cases.
To know the elementary algebra of sets.
To understand the ideas of functions and relations.

Transferable Skills

Writing and thinking within a logical framework.
Proof strategies.
Familiarity with the language of set theory, functions, and relations.

Syllabus

THE LANGUAGE OF MATHEMATICS

Paradoxes. Mathematical statements. Logical and conditional connectives e.g. implies (denoted $\Rightarrow$ ). Logical equivalence. Quantifiers. Negation of statements.

PROOF STRATEGIES

Direct proof of a statement of the form $A \Rightarrow B$ .

Proof by reducing to separate cases.

Informal discussion of rational and real numbers and statement of well-ordering principle. Proof by contradiction; used to show that $\sqrt{2}$ is not a rational number.

Proof by using the (logically equivalent) contrapositive form.

Proof by induction.

The use of counterexamples to show the falsity of statements.

SET THEORY

Informal notion of a set, membership of a set, subset, the empty set; equality and inclusion of sets. Operations on sets: intersection, union, difference, and complement. The set of all subsets of a set (the power set). The algebra of sets. The Cartesian product.

FUNCTIONS

Definition and examples; notation and terminology. Composition of functions. Injections, surjections, bijections. Inverse functions.

RELATIONS

Definition of relations. Reflexive, symmetric, transitive, equivalence relations. Set of equivalence classes. Partitions.

Reading list

Background:

N. L. Biggs, Discrete Mathematics, Oxford University Press.

P. M. Cohn, Algebra I, John Wiley.

D. Driscoll Schwartz, Conjecture and proof, Harcourt Brace.

S. Galovich, Doing Mathematics, Harcourt Brace.

R. Garnier and J. Taylor, 100% Mathematical Proof, John Wiley.

A. G. Hamilton, Numbers, Sets and Axioms, Cambridge University Press.

G. Pólya, How to Solve It, Penguin.

S. Singh, Fermat's Last Theorem, Fourth Estate.

D. Solow, How to Read and Do Proofs

I. Stewart and D. Tall, The Foundations of Mathematics, Oxford University Press.

D. J. Velleman, How to Prove It, Cambridge University Press.

Details of Assessment

The 20% coursework element is made up of a mix of classroom tests (10%) and weekly assignments (10%). Two tests, largely on material from the first half of the course, will be held in weeks 4 and 6. The one and a half hour examination in January comprises 4 questions, and to obtain full marks you need to give complete answers to all questions.

Next: MC145 Algebraic Structures and Up: Year 1 Previous: MC130 Mathematical Modelling

S. J. Ambler
11/20/1999