# An Introduction to Pure Mathematics Preface

## Preview text

Draft 2, Version of 11 October 2012
Oxford University Mathematical Institute
An Introduction to Pure Mathematics
Notes by Peter M. Neumann (Queen’s College)
Preface
These notes are intended as a rough guide to the eight-lecture course Introduction to Pure Mathematics which is a part of the Oxford 1st -year undergraduate course for the Preliminary Examination in Mathematics. Please do not expect a polished account. They are my personal lecture notes, not a carefully checked textbook. Nevertheless, I hope they may be of some help.
Our 1st -year courses are designed to build on your previous experience and the knowledge of mathematics that you have acquired from school or college. The published synopsis for this one is as follows.
• The natural numbers and their ordering. Induction as a method of proof, including a proof of the binomial theorem with non-negative integral coeﬃcients.
• Sets: examples including the natural numbers, the integers, the rational numbers, the real numbers. Inclusion, union, intersection, power set, ordered pairs and cartesian product of sets.
• Relations. Deﬁnition of an equivalence relation. Examples. • Maps: composition, restriction; injective (one-to-one), surjective (onto) and invert-
ible maps; images and preimages. • Rules for writing mathematics with examples. • Hypotheses, conclusions,“if”, “only if”, “if and only if”, “and”, “or”. • Formulation of mathematical statements with examples. Quantiﬁers: “for all”,
“there exists”. • Problem solving in mathematics: experimentation, conjecture, conﬁrmation, fol-
lowed by explaining the solution precisely. • Proofs and refutations: standard techniques for constructing proofs; counter exam-
ples. Example of proof by contradiction and more on proof by induction.
(⋆) Charles Batty, How do undergraduates do Mathematics? (Mathematical Insti-
tute Study Guide, 1994). Paper copies can be purchased from Reception in the Mathematical Institute. It is also available on-line at http://www.maths.ox.ac.uk/files/study-guide/guide.pdf.
i

Further reading: (1) Geoff Smith, Introductory Mathematics: Algebra and Analysis (Springer-Verlag, London, 1998), Chapters 1 and 2. (2) Robert G. Bartle and Donald R. Sherbert, Introduction to Real Analysis (Wiley, New York, Third Edition, 2000), Chapter 1 and Appendices A and B. (3) C. Plumpton, E. Shipton and R. L. Perry, Proof (Macmillan, London, 1984). (4) R. B. J. T. Allenby, Numbers and Proofs (Arnold, London, 1997). (5) Richard Earl, Bridging Course in Mathematics (Mathematical Institute website: use the search box in http://www.maths.ox.ac.uk.) (6) G. Po´lya, How to solve it (Second edition 1957, reprinted by Penguin Books, 1990). My personal opinion is that this GREAT Classic should be in every mathematician’s personal library. Oxford synopses provide a good guide to the content of the lectures, but it should
never be forgotten that it is the syllabus which deﬁnes the course. It is the syllabus which should guide student learning, it is the syllabus which speciﬁes to the examiners what they should test, it is the syllabus which suggests to tutors what they should teach, it is the syllabus which provides the basis of the lecture synopses.
A set of two exercise sheets goes with this lecture course. The questions they contain will be found embedded in these notes along with a number of supplementary exercises.
These notes contain much from the notes of the 2011 version of the course. It is a pleasure to acknowledge my great debt to Dr Robin Knight who wrote them.
I would much welcome feedback. Desy Kristianti of Oriel College has already made useful suggestions for which I am very grateful. Please let me know of any further errors, infelicities and obscurities. Email me at [email protected] or write a note to me at Queen’s College.
Π MN: Queen’s: Version of 11 October 2012
ii

CONTENTS

1

The Greek alphabet

2

2. Numbers and induction

Natural numbers and mathematical induction

3

Factorials, binomial coeﬃcients, Pascal’s triangle

4

The Binomial Theorem for non-negative integer exponents

4

3. Sets

Sets, examples

7

Notation: the sets N, Z, Q, R, C; intervals in R

8

Some algebra of sets: subsets, unions, intersections, set diﬀerence 9

Finite sets: their size or cardinality

10

The power set of a set

11

Ordered pairs; cartesian products of sets

11

4. Relations and functions

Binary relations

13

Properties a relation may have; Equivalence relations

13

Partitions of a set

14

Functions

15

Injective, surjective, bijective functions

16

Algebra of functions—composition, etc.

17

Associativity of composition; inverses

18

One-sided inverses

19

5. Writing mathematics

Errors to avoid

21

The language of mathematical reasoning

22

The quantiﬁers ‘for all’, ‘there exists’

23

Handling negation

25

Formulation of mathematical statements

26

6. Proofs and refutations

Direct proofs

29

29

More on Induction: strong induction; well-ordering

31

Refutation

32

7. Problem-solving in mathematics

33

Some techniques and examples

33

Problem-solving: a summary

36

*****

iv

1 Prolegomenon
We begin with a word. If you do not know it look it up. The point I want to make with the word ‘prolegomenon’ is that in mathematics (as in life) we are forever coming across words that are new to us. Do not be afraid to look them up. That is what dictionaries and other reference works, whether on paper or on-line, are for.
Also a word of advice. Mathematics is a complex subject involving theory, problemsolving, discovery, conjecture, proof or refutation, examples or counterexamples, applications, and much else beside. One of its characteristics, especially but far from exclusively on the ‘pure’ side, is a certainty that can rarely be matched in other subjects. That certainty comes from precision in the use of words and symbols and from precision in the use of logical argument. Many words that we use in mathematics are everyday words such as real, rational, complex, imaginary, set, group, ring, function, relation, to which we give special meanings; others, such as homomorphism, isomorphism, homeomorphism, topology, are rarely met outside of mathematics. Although there may be small local variations, generally, the mathematical community has agreed on the technical meanings of such words. If you come across a word you have not met before, or a familiar word in an unfamiliar context, then make sure to look it up.
1.2 Plan for these lectures
The lecture plan is more or less as listed in the synopsis. We’ll begin with some basic mathematics including numbers and mathematical induction. Then we’ll move on to some of the language of mathematics, the language of sets, relations and functions, and some particularly important examples of each. Next we’ll discuss rules for writing mathematics. The importance of these rules or conventions cannot be over-emphasised. Mathematicians need to be able to express their thoughts very precisely. They need to be able to write what they mean and mean what they write. Their precise meaning needs to be understood by the reader.
Sections 5 and 6 contain discussion of proof as it is commonly understood in mathematics. We will discuss some particularly common logical errors and then examine some of the basic elements of logic used by mathematicians. I will say something about problem-solving, something about experimenting and formulating conjectures, and about the importance of examples and counter-examples. We’ll end with a discussion of how to discover and then reﬁne and explain one’s own proofs.
Sometimes a concept or technique might be used informally before it has been formally deﬁned or discussed. This is so that when we come to our formal discussion we will already have some context to build on. In particular, although I shall not be discussing proofs until the second week, I will feel free to show some examples right from the ﬁrst lecture.
1.3 Lectures and lecture notes
Pre-prepared lecture notes are—or should be—primarily for a lecturer’s own use. They are, if you like, a script for the live event which is the lecture. Your lecturers should feel free to say things that are not in their notes, and not say things that are in their notes. Therefore do take your own notes in lectures. Doing so has several advantages:
1

(1) You get a record of what actually happened in the lecture, including explanations that occurred to the lecturer on the spur of the moment; diagrams; questions that members of the audience asked; the responses; what, if anything, was particularly emphasised; what struck you personally as noteworthy;
(2) it can help ﬁx the content of the lectures in your memory;
(3) the ability to take accurate notes is a useful life skill.
On this last point: mathematics undergraduates go on to careers of every kind. Twenty years from now you may remember little or none of the material you studied as an undergraduate, and you may well have no need for it, but if you get the practice now, you should be able to take useful minutes of meetings and take accurate notes of any seminars or presentations you attend later in life.
The taking of accurate notes is not a matter of copying what a lecturer writes on the board. For one thing there is no point—most of our lecturers provide written notes such as these—but for another, you will ﬁnd that most lecturers go too fast for that. The lecturer leads, the audience follows, and following inevitably involves falling behind. Rather, try to follow the lecturer’s meaning, and make notes in the real sense of that word. Jottings. But make sure that your notes contain enough to stimulate your memory so that you can reconstruct the narrative and the arguments for yourself afterwards. For example, make a note of diagrams. To my great embarrassment I have been unable to incorporate diagrams in these notes, mainly for lack of time. But a picture is worth a thousand words, and I am sure to use diagrams in the lectures. Create your own personal version of the lecture notes. That is a powerful technique for learning and understanding.
One ﬁnal observation on lectures: do not expect to understand them instantly. If you do, that’s great; but don’t worry if you feel lost or left behind. Try to retain at least some idea of the big picture; work through your lecture notes after the lecture; then discuss points that are still puzzling you with your contemporaries and your college tutors.

1.4 The Greek alphabet

Here is the part of the lower case Greek alphabet that is commonly used in mathematics, not in any particular order, with names and approximate Roman equivalents:

α : alpha, a δ : delta, d θ or ϑ : theta ι : iota, i λ : lambda, l ω : omega, o σ : sigma, s ξ : xi, x

β : beta, b ǫ or ε : epsilon, e φ or ϕ : phi κ : kappa, k µ : mu, m π or ̟ : pi, p τ : tau, t η : eta

γ : gamma, c
ψ : psi
ν : nu, n ρ : rho, r χ : chi ζ : zeta, z

A few of the upper case (capital letters) are also commonly used in mathematics:

γ → Γ; λ → Λ;

δ → ∆; ω → Ω;

θ → Θ; π → Π;

φ → Φ; σ → Σ.

You might see Ξ (capital ξ ), but it is rare. The letter Σ and the summation symbol look alike, but technically they are typographically diﬀerent; the same goes for the letter Π and the product symbol .

2

2 Numbers and induction
2.1 Natural numbers
Numbers are, of course, fundamental for most parts of mathematics and its applications. Most of us are comfortable with various diﬀerent kinds of numbers. Yet even at this very basic level we need to deﬁne our terms, or perhaps simply agree usage and conventions.
Definition 2.1. A natural number is a member of the sequence 0, 1, 2, 3, . . . obtained by starting from 0 and adding 1 successively. We write N for the collection (technically, the set—see below) {0, 1, 2, 3, . . .} of all natural numbers.
Important note. Although nowadays all mathematicians use N as a standard name for the collection of natural numbers, some authors and lecturers include 0 as a natural number, some do not. Unfortunately, there is no standard convention. In this course, 0 will belong to N. Just make sure when reading texts or discussing mathematics with others that you clarify such notational conventions before you get in deep.
Natural numbers have many familiar and important properties. For example, they can be added and multiplied—that is, if m, n are natural numbers then so are m + n and m × n—and they may be compared: m < n if m occurs earlier in the sequence than n. Furthermore N is well-ordered, that is, any non-empty collection of natural numbers has a least (or ﬁrst) member. Although there will be further discussion of some of these points later (see § 6.3), all this will, for the purposes of your 1st year course (and for much of the 2nd year too), be taken for granted. Notice, however, that a purist could ﬁnd several points of attack. In the deﬁnition I have used the terms 0, 1, ‘member’, ‘sequence’ and ‘adding successively’, and in the discussion I have used such terms as ‘added’, ‘multiplied’, ‘occurs earlier’, ‘least’. Do we all agree what these mean? At this level it would be very surprising if we did not. Nevertheless, there is an exciting area where mathematics and philosophy come together which deals with such questions. It is represented in the Oxford mathematics degree in the Foundations courses (Logic and Set Theory) oﬀered in Parts B and C.
2.2 Mathematical Induction
Theorem 2.2 [Mathematical Induction]. Let P be a property of natural numbers, that is, a statement P (x) about natural numbers x that may be true for some natural numbers x and false for others. Suppose that P (0) is true, and that for all natural numbers n, if P (n) is true then P (n + 1) is also true. Then P (n) is true for all natural numbers n.
I have called this a theorem, but what proof can we give? Intuitively it seems clear: we are given that P (0) holds, then its truth implies that of P (1), the truth of P (1) implies that of P (2), and so on. Nevertheless, it says something non-trivial. It collects together all the individual true statements, P (0), P (1), P (2), . . ., of which there are inﬁnitely many, into just one true statement, namely ‘P (n) is true for all natural numbers n’. It is so basic that in some versions of the logical foundations of mathematical thinking it is taken as an axiom.
Mathematical Induction is a technique for proving theorems. It goes with a method for deﬁning functions called recursion. Two typical deﬁnitions by recursion are the following:
3

Definition 2.3 [Powers]. Let a be a number (or a variable that takes numerical values). Deﬁne a0 := 1 and then deﬁne an+1 := an × a for n 0

Definition 2.4 [Factorials]. Deﬁne n! for all n thereafter (n + 1)! := n! × (n + 1) for all n 0.

0 by the rule that 0! := 1, and

These are typical of recursion in that it is used to deﬁne a function of a natural number by specifying what value it takes at 0, and saying also how to get from the value it takes at n to the value it takes at n + 1. The second function deﬁned above is the familiar factorial function, which we commonly deﬁne informally by writing n! := 1×2×3×· · ·×n.
Note that the deﬁnitions a0 := 1, 0! := 1 are made for good reason. It makes sense that a product of no factors should be 1. After all, if we have a product of a number of factors, and then add in no more factors, we do not change the product, that is, we have multiplied it by 1. For a very similar reason, we take the sum of no numbers to be 0: if we start with a sum of some numbers and then add no summands we do not change the original sum, so what we have added is 0.
One use of the factorial function is to deﬁne the following extremely useful function of two variables:

Read the symbol := as ‘to be’ or as ‘is deﬁned to be’. It is quite diﬀerent from = , ‘is equal to’, which indicates that two previously deﬁned entities are the same.

Definition 2.5 [Binomial coeﬃcients]. For natural numbers m, n with m n deﬁne n := n! .
m m!(n − m)!
Famously, the binomial coeﬃcients may be organised into an array commonly called Pascal’s Triangle, whose deﬁning property is captured in the following lemma.

Lemma 2.6. [Pascal’s Triangle]. Let m, n be natural numbers such that 1 m n.

Then

n m−1

+

n m

=

n+1 m

.

Exercise 2.1. Write out a proof of Lemma 2.6, using just our deﬁnitions of the factorial function and binomial coeﬃcients, nothing more.

As a good illustration of how Mathematical Induction may be used we give a proof of a very famous and important theorem:

Theorem 2.7 [The Binomial Theorem (for non-negative integral exponents)].

Let x, y be numbers (or variables that may take numerical values).

n

natural number n, (x + y)n =

n m

xn−mym.

m=0

Then for every

Proof. Let P (n) be the assertion that the equation above is true for the natural

number n. Certainly P (0) is true since (x + y)0 = 1 while the sum on the right of the

equation has just one term, namely

0 0

x0y0 , which also is equal to 1.

n

Now suppose that P (n) is true, so that (x + y)n =

n m

xn−mym . Then

m=0

4

(x + y)n+1 = (x + y)n(x + y) =

n

n m

xn−mym

m=0

x+y

[by P (n)]

n

n

=

n m

xn−m+1ym +

n m

xn−mym+1

m=0

m=0

n
= xn+1 + yn+1 +
m=1

n m

+

n m−1

xn+1−mym,

that is, by Lemma 2.6 together with the deﬁnitions of n +0 1 and nn ++ 11 ,

n+1

(x + y)n+1 =

n+1 m

xn+1−mym,

m=0

which is the statement P (n + 1). By induction, therefore, the equation holds for all

natural numbers n, as the theorem states.

Exercise 2.2.
n
m3 .
m=0

n

n

Write careful proofs by induction of formulae for m , m2 ,

m=0

m=0

n
Exercise 2.3. Show that if Sk(n) := mk then Sk(n) may be expressed as a
m=0
polynomial of degree k + 1 in n , whose leading term is nk+1 . k+1

Exercise 2.4. The following famous argument purports to show that all natural numbers are small. ‘Certainly 0 is small. If n is small then also n + 1 is small. Therefore by induction all natural numbers are small.’ What is missing?

Note: I have learned from Desi Kristianti of Oriel College that this is known as Wang’s Paradox. It is not what I would call a paradox. When my friend and I were shown it by one of our schoolteachers we all treated it as a joke. I still think of it as a joke—though a joke with a serious moral. The moral is: make sure to deﬁne your terms precisely.

Exercise 2.5.

n

Show that

n m

m=0

= 2n , and that

n m

=

n m

= 2n−1.

0 m n,

0 m n,

m even

m odd

Exercise 2.6. Show that 4n < 2n < 4n if n 2n n
inequalities?

2. How far can you reﬁne these

5

6 