Numbers and Sets

Numbers and Sets

NUMBERS AND SETS
[Note that this course is omitted from Option (b) of Part IA.]

Introduction to number systems and logic

  • Overview of the natural numbers, integers, real numbers, rational and irrational numbers, algebraic and transcendental numbers. Brief discussion of complex numbers; statement of the Fundamental Theorem of Algebra.
  • Ideas of axiomatic systems and proof within mathematics; the need for proof; the role of counterexamples in mathematics. Elementary logic; implication and negation; examples of negation of compound statements. Proof by contradiction. [2]

Sets, relations and functions

  • Union, intersection and equality of sets. Indicator (characteristic) functions; their use in establishing set identities. Functions; injections, surjections and bijections. Relations, and equivalence relations. Counting the combinations or permutations of a set. The Inclusion-Exclusion Principle. [4]

The integers

  • The natural numbers: mathematical induction and the well-ordering principle. Examples, including the Binomial Theorem. [2]

Elementary number theory

  • Prime numbers: existence and uniqueness of prime factorisation into primes; highest common factors and least common multiples. Euclid’s proof of the infinity of primes. Euclid’s algorithm. Solution in integers of ax+by = c. Modular arithmetic (congruences). Units modulo n. Chinese Remainder Theorem. Wilson’s Theorem; the Fermat-Euler Theorem. Public key cryptography and the RSA algorithm. [8]

The real numbers

  • Least upper bounds; simple examples. Least upper bound axiom. Sequences and series; convergence of bounded monotonic sequences. Irrationality of √2 and e. Decimal expansions. Construction of a transcendental number. [4]

Countability and uncountability

  • Definitions of finite, infinite, countable and uncountable sets. A countable union of countable sets is countable. Uncountability of R. Non-existence of a bijection from a set to its power set. Indirect proof of existence of transcendental numbers. [4]

Appropriate books

  • R.B.J.T. Allenby Numbers and Proofs. Butterworth-Heinemann 1997
  • R.P. Burn Numbers and Functions: steps into analysis. Cambridge University Press 2000(pdf)
  • H. Davenport The Higher Arithmetic. Cambridge University Press 1999(pdf)
  • A.G. Hamilton Numbers, sets and axioms: the apparatus of mathematics. Cambridge University Press 1983
  • C. Schumacher Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley 2001
  • I. Stewart and D. Tall The Foundations of Mathematics. Oxford University Press 1977

Informal description of Numbers and Sets

This course is concerned not so much with teaching you new parts of mathematics as with explaining how the language of mathematical arguments is used. We will use simple Mathematics to develop an understanding of how results are established.

Because you will exploring a broader and more intricate range of mathematical ideas at University, you will need to develop greater skills in understanding arguments and in formulating your own. These arguments are usually constructed in a careful, logical way as proofs of propositions. We begin with clearly stated and plausible assumptions or axioms and then develop a more and more complex theory from them. The course, and the lecturer, will have succeeded if you finish the course able to construct valid arguments of your own and to criticize those that are presented to you. Example sheets and supervisions will play a key role in achieving this. These skills will form the basis for the later courses,particularly those devoted to Pure Mathematics.

In order to give examples of arguments, we will take two topics: sets and numbers. Set theory provides a basic vocabulary for much of mathematics. We can use it to express in a convenient and precise shorthand the relationships between different objects. Numbers have always been a fascinating and fundamental part of Mathematics. We will use them to provide examples of proofs, algorithms and counter-examples.

Initially we will study the natural numbers 1, 2, 3, . . . and especially Mathematical Induction. Then we expand to consider integers and arithmetic leading to codes like the RSA code used on the internet.Finally we move to rational, real and complex numbers where we lay the logical foundations for analysis.(Analysis is the name given to the study of, for example, the precise meaning of differentiation and integration and the sorts of functions to which these processes can be applied.)

Learning outcomes

By the end of this course, you should:

  • understand the need for rigorous proof in mathematics, and be able to apply various different methods, including proof by induction and contradiction, to propositions in set theory and the theory of numbers;
  • know the basic properties of the natural numbers, rational numbers and real numbers;
  • understand elementary counting arguments and the properties of the binomial coefficients;
  • be familiar with elementary number theory and be able to apply your knowledge to the solution of simple problems in modular arithmetic;
  • understand the concept of countability and be able to identify typical countable and uncountable sets.
Numbers-and-sets-Outline-2
Numbers-and-sets-Outline-1
Numbers-and-sets-Outline-3
Numbers-and-sets-Outline-4