MATH10101 - 2006/07

 

Specification

Aims

The programme unit aims to:

• address the problem of enumerating sets - both finite and infinite!
• to supply evidence that such problems are both intriguing and provocative, and require rigorous proof;
• to explain the fundamental ideas of sets, numbers and functions;
• to compare and contrast language and logic;
• to introduce a detailed study of the integers, including prime numbers and modular arithmetic;
• to show how mathematicians generalize ideas, so unique factorization of integers is shown to hold for permutations, whilst Euclid 's Algorithm introduced for integers is shown to hold for polynomials;
• to introduce the ideas of algebraic structures and so show, by examples throughout the course, how the same structure can arise in many different situations.

Brief Description of the unit

This course introduces students to the concept of proof, by studying sets, numbers and functions from a rigorous viewpoint. These topics underlie most areas of modern mathematics, and recur regularly in years 2, 3, and 4. The logical content of the material is more sophisticated than that of many A-level courses, and the aim of the lectures is to enhance students' understanding and enjoyment by providing a sequence of interesting short-term goals, and encouraging class participation.

Learning Outcomes

On completion of this unit successful students will be able to:

• analyze statements using truth tables;
• construct simple proofs including proofs by contradiction and proofs by induction;
• prove statements about sets and functions;
• prove standard results about countable sets;
• apply Euclid 's Algorithm to find the greatest common divisor of pairs of integers and to solve linear Diophantine equations;
• apply the Chinese Remainder Theorem to solve simultaneous linear congruences;
• multiply and factorize permutations;
• prove the infinitude of prime numbers, prove Fermat's Little Theorem and use it to find modular inverses and to solve linear congruences;
• multiply, use long divisision and apply Euclid 's Algorithm to find the greatest common divisor of, pairs on polynomials;
• construct multiplication tables for congruence classes, reduced congruence classes and sets of permutations. Have an informal understanding of isomorphisms between the groups seen in the course.

Future topics requiring this course unit

Almost all Mathematics course units, particularly those in pure mathematics.

Syllabus (Part 1: Nige Ray)

This covers chapters 1 to 14 of the course text omitting 5.4, 9.4, 11.3, 12.1, 12.2 and 12.3.

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, by conditions, by 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 the 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.

Part 2 (Mark 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. Congruence 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 Erastosthenes, infinitude of primes, conjectures about primes, Fermat's Little Theorem, Euler'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*.

Definitions and very simple properties. Examples from earlier in the course, multiplication tables.

*indicates that this topic is not included in the course text.

Textbooks

All students are expected to acquire a copy of

P.J. Eccles, An Introduction to Mathematical Reasoning: Numbers, Sets and Functions, Cambridge University Press, 1997.

Teaching and learning methods

Four lectures and one supervision each week.

Problem sheets are posted on the course website and students are expected to submit their solutions (included partial attempts) to the questions indicated for marking in advance of the supervision.

Assessment

Supervision attendance and participation; Weighting within unit 10%

Coursework; Weighting within unit 15%

Three hours end of semester examination; Weighting within unit 75%

to the top

Arrangements

Midterm Test

The Midterm Test will be in-class and closed book, and will relate to the first five weeks of the course ONLY. It will involve answering questions similar to those on the relevant Problem Sheets; students who have taken full advantage of their supervision classes should therefore find the Test straightforward. It will be worth 15% of the final mark for the course. Answers will be marked and returned in due course, as part of the learning process.

The Test will take place on THURSDAY 9 NOVEMBER 2006, in RENOLD C16, from 12 NOON until 12.50PM.