MT1101 Sets, Numbers and Functions

Course Description

Aims

• 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.

Syllabus

Part 1 (Prof. Ray)

1. Motivation.
   Lecture 0; Provocative Examples. First thoughts on infinite sets; examples versus proof; an extended version of Hilbert's Hotel; Cantor's fate (and redemption!)
2. 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.
3. Proof.
   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.
4. Sets.
   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.
5. Functions.
   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.
6. 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.
7. 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)

1. Counting Collections of Functions and Subsets
   Numbers of injections and bijections. Numbers of subsets and Binomial Numbers, Pascal's Triangle, Binomial Theorem.
2. Arithmetic - the study of the integers
   Division Theorem, Greatest Common Divisor, Euclid's Algorithm, Linear Diophantine Equations.
3. Congruences and Congruence Classes
   Congruences, Modular Arithmetic, Solving Linear Congruences, Chinese Remainder Theorem, Congruence Classes, Multiplication Tables*, Invertible Elements, Reduced Systems of Classes*.
4. Partitions and Relations
   Partitions, Relations, generalizing Congruence Classes.
5. Permutations*
   Bijections, two row notation, Composition, Cycles, The Permutation group S_n, Composition Tables, Factorization, Order.
6. Prime Numbers
   Sieve of Eratosthenes, Infinitude of Primes, Conjectures about Primes, Fermat's Little Theorem, Euler's Theorem*.[Wilson's Theorem]
7. Polynomials* #
   Long Division, Division Theorem, Factorization, Statement of the Fundamental Theorem of Algebra, Greatest Common Divisor, Euclid's Algorithm.
8. 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)

Past Exam Papers

• January 2006