MT1101 Sets, Numbers and Functions
Prof. Nigel Ray, Room 1.29 Newman Building, Extension 55848
Dr. Mark Coleman, Room O8 MSS Building, Extension 63649
- Delivery: Semester One
- Credits: 20
- Lectures: see timetable
- Prerequisites: A-Level Mathematics or equivalent
- Teaching and learning methods: 4 lectures and 1 supervision per week
- To address the problem of enumerating sets - both finite and infinite!
- To supply evidence that such problems are both intriguing and provocative, and need rigorous proof
- To compare and contrast language and logic
- To enhance students' participation by providing a sequence of interesting short-term goals.
Part 1 (Prof. Ray)
Lecture 0; Provocative Examples. First thoughts on infinite sets; examples versus proof; an extended version of Hilbert's Hotel; Cantor's fate (and redemption!)
- Basic Logic.
Lecture 1; The Language of Mathematics. Mathematical statements, propositions; or, and, not; truth tables.
Lecture 2; Implication. Implication; necessary and sufficient, iff; rules of arithmetic, where proofs begin.
Lecture 3; Proof. Direct proof; case-by-case; working backwards.
Lecture 4; Contradiction. Negative statements; proof by contradiction; contrapositives, statements with or.
Lecture 5; Induction. The induction principle and proof by induction; changing the base case; inductive definitions.
Lecture 6; History and Language. Historical origins, natural numbers to complex numbers; notation, belongs to, definitions (by listing, conditions, and construction); subsets, equality.
Lecture 7; Operations on Sets. Union, intersection, empty set (with class discussion!); identities, Venn diagrams; power set.
Lecture 8; Quantifiers. Universal and existential statements, proof and negation of statements with quantifiers; induction revisited; two free variables.
Lecture 9; Further Operations. Cartesian products; power sets.
Lecture 10; Definitions and Examples. Notation; domain, codomain; formulae and examples (including empty set); equality; restriction.
Lecture 11; More Definitions and Examples. Composition; image; sequences and indexing; restriction, graphs.
Lecture 12; Jections. Injections, surjections, bijections; their compositions.
Lecture 13; Inverse Functions. Bijections and inverse functions; inverse images; transpositions.
- Counting Finite Sets.
Lecture 14; Cardinality. Role of the integers, cardinality, is it well-defined? reduction to pigeon-hole principle.
Lecture 15; Principles of Counting. Principles of addition, multiplication, inclusion- exclusion.
Lecture 16; The Pigeon-Hole Principle. Proof of pigeon-hole principle, finite sets of real numbers.
- Counting Infinite Sets
Lecture 17; Rationals and Reals. Definition of rationals, and of reals as infinite decimals; √2.
Lecture 18; Countability. Denumerability, ℵ_0, proper subsets; Cartesian products, integer pairs, rationals.
Lecture 19; Uncountability. The reals; power sets and their cardinality.
Lecture 20; Other Types of Real Number. Algebraic and transcendental numbers.
Summary of part 1
Broadly speaking, the first five weeks cover Chapters 1-14 of the course textbook. I will also include a proof of Cantor's result that the set of algebraic numbers is denumerable (see page 181) - this will be the climax of my part of the course! The following sections and subsections will be omitted (although some of this material is likely to feature in weeks 6-12):
Omissions. 5.4 (Strong induction); 9.4 (Peano's axioms); 11.3 (gcd and oddeven); 12.1, 12.2, 12.3 (Counting functions and subsets).
Part 2 (Dr. Coleman)
- Counting Collections of Functions and Subsets
Numbers of injections and bijections. Numbers of subsets and Binomial Numbers, Pascal's Triangle, Binomial Theorem.
- Arithmetic - the study of the integers
Division Theorem, Greatest Common Divisor, Euclid's Algorithm, Linear Diophantine Equations.
- Congruences and Congruence Classes
Congruences, Modular Arithmetic, Solving Linear Congruences, Chinese Remainder Theorem, Congruence Classes, Multiplication Tables*, Invertible Elements, Reduced Systems of Classes*.
- Partitions and Relations
Partitions, Relations, generalizing Congruence Classes.
Bijections, two row notation, Composition, Cycles, The Permutation group S_n, Composition Tables, Factorization, Order.
- Prime Numbers
Sieve of Eratosthenes, Infinitude of Primes, Conjectures about Primes, Fermat's Little Theorem, Euler's Theorem*.[Wilson's Theorem]
- Polynomials* #
Long Division, Division Theorem, Factorization, Statement of the Fundamental Theorem of Algebra, Greatest Common Divisor, Euclid's Algorithm.
- Groups, [Rings and Fields]*
Definition and very simple properties. Examples from earlier in the course. Multiplication tables. [Informal discussion of isomorphisms].
- * means that the material does not appear in P.J. Eccles book.
- # subject to having sufficient time. [...] means the subject was not covered.
Course Materials - Part 1 (Prof. Ray)
Course Materials - Part 2 (Dr. Coleman)
- Part 2 (Dr. Coleman)