Lecturer: Josephine Evans

Term(s): Term 1

Status for Mathematics students: Core

Commitment: 30 lectures, assignments with weekly online quizzes based on them

Assessment: 15% from online quizzes and 85% from exam

Formal registration prerequisites: None

Assumed knowledge: Grade A in A-level Maths or equivalent.

Useful background: Some elementary knowledge of modular arithmetic, induction principle, set notation.

Synergies: Most later pure mathematics modules specifically:

• MA139 Analysis 2
• MA150 Algebra 2
• MA268 Algebra 3

Leads to: The following modules have this module listed as assumed knowledge or useful background:

• MA222 Metric Spaces
• MA260 Norms, Metrics and Topologies
• MA257 Introduction to Number Theory
• MA263 Multivariable Analysis
• MA3A6 Algebraic Number Theory
• MA3H3 Set Theory

Aims: University mathematics introduces progressively more and more abstract ideas and structures, and demands more and more in the way of proof, until by the end of a mathematics degree most of the student's time is occupied with understanding proofs and creating his or her own. This is not because university mathematicians are more pedantic than schoolteachers, but because proof is how one knows things in mathematics, and it is in its proofs that the strength and richness of mathematics is to be found.

Learning to deal with abstraction and with proofs takes time. This module aims to bridge the gap between school and university mathematics, by beginning with some rather concrete techniques where the emphasis is on calculation, and gradually moving towards abstraction and proof.

Indicative Content:

• Naive Set Theory, Counting and Lists:
  Sets and functions, injections, surjections and bijections, permutations.
  Lists, sublists, lists as functions, strings.
  Subsets, power sets, partition, infinite versus finite, Cantor's Theorem.

• Operations on Sets, Lists, Functions:
  Ordered pairs, cartesian products, functions and graphs, functions and lookup tables.
  Union, intersection, set difference, list concatenation.
  Composition, iteration, orbits, Cantor-Schroeder-Bernstein, cardinalities.
• Relations:
  Reflexive, symmetric, transitive.
  Orders, equivalence classes and relations: integers, rational numbers, partitions.
  Kernels and co-kernels, well-definedness, modular arithmetic.
• Logic:
  Variables, booleans, negation, operations.
  Operators and formulas via truth tables.
  Quantifiers, tautologies, deduction rules.
• Proof:
  What is proof? False proofs, examples, subtle issues (diagrams, hand-waving)
  Kinds of proof: direct, contraposition, contradiction, construction, cases.
  Recursion, induction, pigeonhole principle, counting.
• Algorithms in Algebra and Cryptography:
  What is algorithm? Euclid's algorithm, operational complexity, P=NP
  Discrete Logarithm, introduction to cryptography, Diffie-Hellman key exchange.
  Prime factorisation, primality testing, Chinese Remainder Theorem
  RSA (Rivest–Shamir–Adleman) public key exchange

Objectives: Students will work with number systems and develop fluency with their properties; they will learn the language of sets and quantifiers, of functions and relations and will become familiar with various methods and styles of proof.

Books:
None of these is the course text, but each would be useful, especially the first:
A.F.Beardon, Algebra and Geometry, CUP, 2005.
I.N. Stewart and D.O. Tall, Foundations of Mathematics, OUP, 1977.
J. A. Green, Sets and Groups; First Course in Algebra, Chapman and Hall, 1995.

Additional Resources