You are here: Mathematics > undergraduate > undergraduate studies > course units > 2005/06 units > mt1101
School of Mathematics

# MT1101 Sets, Numbers and Functions

Course Facts
• Lecturers:
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
• Assessment:
Page Contents

## 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 2 (Dr. Coleman)

This page is currently under development. Course materials for Part 2 can be temporarily found here: