Proof and Structure in Mathematics

EMMS095S4 (30 credits)

Aims

This module aims to introduce the essential logical and theoretical concepts necessary for the degree-level study of mathematics. At the end of the module you will have obtained a thorough grounding in the basic mathematical concepts which will be used throughout the degree programme.

What makes mathematics different from the sciences is the emphasis placed on proof. In this module you will be introduced to various common methods of proof, such as proof by contradiction and proof by induction, as well as the basic components of propositional logic: connectives, quantifiers and truth tables.

The main number sets (natural numbers, integers, rational, real and complex numbers) will be defined and their properties studied. Binary relations and binary operations and the concept of a group will be introduced and some elementary results established.

Teaching and Assessment

Teaching for this module will take place throughout the year, with eight evenings of lectures in each of the Autumn and Spring Terms and two evenings of revision and consolidation in the Summer Term.

Of the final course mark, 80% is based on a three-hour exam in June and the other 20% is from assessed coursework.

Coursework  will consist of short, problem based assignments. You will have around three weeks to complete each one.

The examination in June has two sections. Section A (worth 40%) consists of compulsory short questions. Section B (also worth 40%) contains several longer questions of which you must answer two.

Syllabus

1. The language of Mathematics: Statements; theorems; definitions; logical connectives (not, and, or, implies); truth tables; tautologies and equivalent statements; the universal and existential quantifiers; negating if/then statements and statements involving quantifiers; some elementary proofs; contrapositive proofs; converses and counterexamples; proof by contradiction; Euclid’s proof of the infinity of primes; proof by induction; strong induction (4 weeks/ 12 hrs).
2. The number sets: Integers, rationals and real numbers: The well ordering property; the division theorem; the fundamental theorem of arithmetic; the Euclidean division algorithm; algebraic properties of the natural numbers and integers; congruence and modular arithmetic; solution of linear congruences; The rational numbers, the real numbers; boundedness; the completeness axiom (4 weeks/ 12 hrs).
3. Complex numbers and Infinite Sequences: the complex numbers: arithmetic of complex numbers, polar form, De Moivre’s Theorem and applications. Definition of a sequence; limits and limit theorems; monotone sequences; subsequences; divergent sequences; infinite series (4 weeks/ 12 hrs).
4. Binary relations, Binary operations and Groups: binary relations and equivalence relations; binary operations; the properties of commutativity and associativity; identity elements and inverses; idempotents; operation multiplication tables; definition of a group; examples from geometry, permutations, matrices, number sets; cyclic groups and abelian groups; orders of elements and groups; subgroups; Lagrange’s Theorem (4 weeks/ 12 hrs).

In addition there will be 2 weeks/6 hours of consolidation and revision lectures in the Summer Term.

Learning Outcomes

Subject Specific

1. Knowledge and understanding of, and the ability to use, mathematical and/or statistical methods and techniques.
In particular:

• proof methods such as contrapositive proofs, proof by contradiction and proof by induction
• the basic terminology of mathematics such as logical connectives and quantifiers.

2. Knowledge and understanding of a range of results in mathematics and/or statistics.
In particular:

• Knowledge of the basic notation and terminology of logic, series, relations, and operations
• Ability to work with the main number sets (the integers, rational, real and complex numbers)
• Ability to solve linear congruences; awareness of the properties of congruence modulo positive integers n
• Facility with the concept of limits for infinite sequences.

3. Appreciation of the need for proof in mathematics, and the ability to follow and construct mathematical arguments.

4. Appreciation of the power of generalization and abstraction in the development of mathematical theories.

Intellectual

1. Ability to comprehend conceptual and abstract material.

2. Develop a logical and systematic approach to problem solving.

Practical

1. Problem-solving skills, including the ability to assess problems logically and approach them analytically.

2. Highly developed quantitative skills.

Personal and Social

1. Ability to work independently with patience and persistence.

2. Time-management skills and organizational skills.

3. Good communication skills, including the ability to write coherently.

4. Ability to complete work in a limited time period.

Recommended Texts

You do not need to buy any books as everything will be covered in lectures. However the following texts cover some of the same material and are a source of extra examples and exercises.

• Allenby, RJBT, Numbers and Proofs, Arnold, Butterworth-Heinemann (1997).
• Keith Devlin, Sets, Functions and Logic, Chapman & Hall (2003).
• Eccles, PJ, An Introduction to Mathematical Reasoning, CUP, Cambridge (1997).
• Martin Liebeck, A Concise Introduction to Pure Mathematics, Chapman & Hall (2000).
• Solow, D, How to Read and Do Proofs, John Wiley and Sons, New York (2004).
• Ledermann, W and AJ Weir, Introduction to Group Theory (Second Edition), Addison Wesley Longman, (1996).
• Humphreys, JF and MY Prest, Numbers, Groups and Codes, Cambridge University Press (1989)