Sets, Functions and Logic

Sets, Functions and

Logic
Basic concepts of university
mathematics

KEITH J. DEVLIN
Reader in Mathematics,
University ofLancaster

Springer-Science+Business Media, B.V.

 © K. J. Devlin 1981
Originally published by Chapman and Hall in 1981
Softcover reprint of the hardcover 1st edition 1981

ISBN 978-0-412-22660-1 ISBN 978-1-4899-2967-9 (eBook)

DOI 10.1007/978-1-4899-2967-9

This title is available in both hardbound and paperback edi-

tions. The paperback edition 1s sold subject to the condition
that it shall not, by way of trade or otherwise, be lent, re-sold,
hired out, or otherwise circulated without the publisher's prior
consent in any form of binding or cover other than that m
which it is published and without a similar condition including
this condition being imposed on the subsequent purchaser

All rights reserved. No part of this book may be reprinted, or

reproduced or utilized in any form or by any electronic,
mechanical or other means, now known or hereafter invented,
including photocopying and recording, or in any information
storage and retreival system, without permission in writing from
the publisher.

Bnttsh Library Catalogumg m Publication Data

Devhn, Keith J
Sets, functwns and logic.
1. Mathematics-1961-
1. Title
510 QA37.2 80-40674
ISBN 978-0-412-22660-1
ISBN 0-412-22670-7 Pbk
Contents

Preface Vll

Note for the student ix

1 Use of language in mathematics 1
1.1 The language of mathematics: part 1 2
1.2 Properties of the language 8
1.3 The language of mathematics: part 2 15
1.4 Proofs in mathematics 20
1.5 Mathematical truth 29
2 Sets and functions 32
2.1 Sets 32
2.2 Operations on sets 36
2.3 Functions 44
2.4 Composition of functions. Inverse functions 51
3 The real numbers 54
3.1 The real line 54
3.2 Upper bounds. Completeness 56
3.3 Absolute values 58
3.4 Intervals 60
3.5 Sequences 62
4 Complex numbers 66
4.1 N urn ber systems 66
4.2 Complex numbers 68
4.3 The complex plane 71
4.4 The complex number i 73
4.5 Conjugate complex numbers. Division of
complex numbers 76
4.6 Polar representation of complex numbers 78
v
vi CONTENTS
4.7 Multiplication of complex numbers in polar form 80
4.8 Algebraic equations 84
List of symbols 88
Index 89
Preface

The purpose of this book is to provide the student beginning

undergraduate mathematics with a solid foundation in the basic
logical concepts necessary for most of the subjects encountered in a
university mathematics course.
The main distinction between most school mathematics and
university mathematics lies in the degree of rigour demanded at
university level. In general, the new student has no experience of
wholly rigorous definitions and proofs, with the result that, although
competent to handle quite difficult problems in, say, the differential
calculus, he/she is totally lost when presented with a rigorous
definition oflimits and derivatives. In effect, this means that in the first
few weeks at university the student needs to master what is virtually
an entire new language {'the language of mathematics'} and to adopt
an entirely new mode ofthinking. Needless to say, only the very ablest
students come through this process without a great deal of difficulty.
Unfortunately, whilst it is understood by all university teachers of
mathematics that it takes a great deal of time and effort to master the
new crafts, very little class time can be made available to cover the
necessary material (and indeed, even if it were, it is difficult to see how
it could be successfully used, since what the student really requires is
time to ponder over the new ideas: it is not the amount of material
that causes the problems, rather its strangeness). It is intended that
this book will be of use to the student during the first term at
university (and perhaps also during the weeks prior to entering the
university).
The material covered represents only a tiny fragment ofthe typical
first year mathematics syllabus, and indeed is usually 'dealt with' in
the first two weeks oflectures. But time spent mastering this material
pays dividends later on, particularly when the student begins the
Analysis course: always a traumatic event!
VII
viii PREFACE
I have strived to keep the book as short as possible, whilst keeping
in mind my intention that the weakest student should be able to read
through it unaided. This has meant omitting many topics, e.g. number
systems, countability, relations, continuity, which would arguably fall
within the scope of a book of this nature. However, there are available
on the market a number of excellent introductory texts in Algebra and
Analysis which deal with these topics, and in any case they fall quite
clearly within the syllabuses of the various subjects concerned. So I
have included only those topics which are basic to almost every area of
mathematics, and without which it is practically impossible to begin
anything at all.
In Chapter 1, we examine those parts of language which are so
crucial to (pure) mathematics and which traditionally cause a great
deal of trouble to beginners (in particular, the negation of statements
involving quantifiers and implications). This is not a crash course in
mathematical logic in the formal sense - rather just an attempt to
make precise those points of language which play such a vital role in
mathematical discourse. It is designed to prepare the student for
his/her other courses as quickly as possible. Some lectures in
mathematical logic could subsequently be given to strengthen this
initial coverage, should the instructor feel this is desirable - but this
would fall outside the narrow aims of this book.
Chapter 2 deals with sets and functions, which, though intrinsically
easy, cause many problems for students who meet this for the first
time at university level.
Next, in Chapter 3 we take a brief look at the real numbers. As
much as anything this chapter provides concrete applications and
examples of the material covered in the first two chapters. Though
this will clearly prepare the ground for an Analysis course, it is not
intended to supersede any of the parts of such a course. In particular,
convergence of sequences is included purely as an illustration of
the behaviour of quantifiers.
Finally, in Chapter 4 we present a crash course in complex
numbers. Though this is primarily designed for the reader who has
not covered this topic at school, the earlier parts of this chapter
should be of interest to all readers, and tie in with chapter 3 to some
extent.
Note for the student

Unless you have done what is known as a 'modern maths' syllabus at

A-level, almost everything in this book will be new to you, and will
doubtless seem very strange. Indeed, you may feel that it is not
'mathematics' at all. With patience and a fair amount of hard work,
this stage will soon pass. Do not try to rush through the book in order
to 'keep up with the lectures'. Take it steadily, and try to understand
the new concepts. There is little to learn, but a great deal to
comprehend! (The actual facts contained in this book could be listed
on three or four pages of notes.) And try the exercises! They are
included for a purpose: to aid your understanding. Discuss any
difficulties which arise with your colleagues or with your tutor. Do
not give up. Last year's students managed it. So did the previous
year's. So did we all. So will you!

Further reading
The following book is suggested for further reading: The Foundations
of Mathematics by I. Stewart and D. Tall (Oxford University Press,
1977).

ix
CHAPTER 1

Use of language in
mathematics

It is probably impossible to formulate a precise definition of

(contemporary) pure mathematics (except perhaps to say that it is
what contemporary pure mathematicians do for a living i). But one
thing is clear, in pure mathematics one is concerned with statements
about mathematical objects.
Mathematical objects are things such as: integers, real numbers, sets,
functions, etc. Examples of mathematical statements are:
(1) There are infinitely many prime numbers.
(2) For every real number a, the equation x 2 + a = 0 has a real root.
(3) J2 is irrational.
(4) If p(n) denotes the number of primes less than or equal to the
natural number n, then as n becomes very large, p(n) approaches
n/loge (n).
Not only are we interested in statements of the above kind, we are,
above all, interested in knowing which statements are true and which
are false. (The truth or falsity in each case is demonstrated by a proof.)
For instance, in the above examples, (1), (3), and (4) are true whereas
(2) is false.
The truth of (1) is easily proved. We show that if we list the primes in
increasing order as
PI' P2' P3' ... , Pm ... ,
then the list must continue for ever. (We all know what the first
few members of the sequence are: PI = 2, P2 = 3, P3 = 5, P4 = 7,
Ps = 11, .... ) Consider the list up to stage n:

PI' P2' P3' ... , Pn

2 SETS, FUNCTIONS AND LOGIC
Let

If p is not a prime, there must be a prime q < p such that q divides p.

But none of Pl' ... , Pn divides P, for the division of P by anyone of
these leaves a remainder of 1. So, either P must itself be prime, or else
there is a prime q < P which exceeds Pn- Either way we see that there is
a prime greater than Pn' Since this argument does not depend in any
way upon the size of n, it follows that there are infinitely many primes.
Example (2) can easily be proved to be false. Since the square of no
real number is negative, the equation x 2 + 1 = 0 does not have a real
root.
We give a proof of(3) later. The only known proofs of example (4)
are extremely complicated.
Before we can prove whether certain statements are true or false, we
must be able to understand precisely what the statement says. Above
all, mathematics is a very precise subject, where exactness of
expression is required. This already creates a difficulty, for in real life
our use oflanguage is rarely precise. Now, to systematically make the
entire English language precise (by defining exactly what each word is
to mean) would be an impossible task. It would also be unnecessary. It
turns out that by deciding exactly what we mean by a few simple
words, we can obtain a 'language' which is precise. The point is that in
mathematics we don't use all of the English language. Indeed, when
we restrict our attention to mathematical statements (rather than our
attempts to explain them), we need only a very small part of our
language.

1.1 The language of mathematics: part 1

We shall make precise a few key words of the English language,
thereby enabling us to formulate in an exact and unambiguous
fashion any mathematical concept we wish to consider. The difficulty
for the beginner is that the mathematical usage of some of these words
is not quite the same as the everyday, non-mathematical usage.
However, there is no such problem with the first word considered
below: and.
We need to be able to assert that two events simultaneously hold.
For instance, we may wish to say that n is greater than 3 and less than
 USE OF LANGUAGE IN MATHEMATICS 3

3· 2. So the word

and

is indispensable. Sometimes, in order to shorten an expression, we

introduce an abbreviation for and. The most common are

/\ , &

Thus, the expression

(n> 3) /\ (n < 3'2)

says: n is greater than 3 and less than 3·2. In other words, n lies
between 3 and 3'2.
There is no possible source of confusion when we use the word and.
(If ¢ and IjJ are any two mathematical statements, ¢ /\ IjJ is the
assertion (which may not be a valid assertion) that both ¢ and IjJ are
true.) The same cannot be said of our next 'word'. We wish to be able
to assert that event A occurs or event B occurs. For instance, we might
want to say

either the equation x 2 +a = 0 has a real root

or a> 0

or perhaps we want to say

a b = 0 if a = 0 or b=0

Now, the use of 'or' is different in these two examples. In the first case
we say 'either . .. or .. .', which emphasizes that there is no possibility
of both occurring (at once). In the second case, it is quite possible for
botha and b to be zero. Even if we were to alter our second example by
inserting an 'either', we would still read it as ifboth possibilities could
occur at once: the use of 'either' only helps to strengthen an assertion
where it is already clear that there is no possibility of both. But there is
no harm in dropping the use of the word 'either' altogether. The first
example above remains true without the word 'either', even if by 'or'
we understand the possibility that both may occur. True, with this
4 SETS, FUNCTIONS AND LOGIC
example both cannot occur. But that does not affect the truth of the
assertion.
Accordingly, when we use the word 'or' in mathematics we always
mean the 'inclusive-or'. If ¢ and t/J are mathematical statements, ¢ or
t/J is the assertion that at least one of ¢ or t/J is valid. We usually
abbreviate or by the symbol v . Thus ¢ v t/J means at least one of ¢
and t/J are valid.
For instance, the following statement is true:

(3 < 5) v (1 = 0)

(Beginners often make the mistake oftrying to argue that this is 'false'
because 1 cannot equal O. They fail to grasp that all that is happening
is that we decide on the convention that 'or' has the meaning 'at least
one of'. This does not agree with many uses of 'or' outside of
mathematics, but for mathematics this definition chosen has many
advantages.)
For our next word, we need to be able to negate a statement, to say
that a particular statement is false. So we need the word

not

If ¢ is any statement, not-¢ is the assertion that ¢ is false. Thus, if ¢ is a

true statement, not-¢ is a false statement; and if ¢ is a false statement,
not-¢ is a true statement. We usually abbreviate not by the symbol

(Older texts sometimes use the symbol ~ but this has long since
dropped from common usage.)
Now, although our usage of not accords with most common usage,
the negation concept is sometimes used very loosely in everyday
speech. For instance, there is no confusion about the meaning of the
statement
~(n<3)

This clearly means

n~3

(which, incidentally, is the same as (n = 3) v (n > 3) !). But consider the

 USE OF LANGUAGE IN MATHEMATICS 5

statement

All British cars are badly made

What is the negation of this statement?

(a) All British cars are well made.
(b) All British cars are not badly made.
(c) At least one British car is well made.
(d) At least one British car is not badly made.
A common mistake is for the beginner to choose (a). But this is
obviously wrong. Our original statement is false (consider Rolls
Royce). Hence the negation of this statement will be true. But (a) is
certainly not true! Neither is (b) true. So realistic considerations lead
us to conclude that the correct answer is either (c) or (d). (We shall
later see how we can eliminate (a) and (b) by a mathematical argument.)
Both (c) and (d) can be said to represent the negation of our original
statement. (Rolls Royce testifies the truth of both (c) and (d).) Which
do you think most closely corresponds to the negation of our original
statement? (We come back to this example later, but before we leave it
now, let us remark that the original statement is only concerned with
British cars. Hence its negation will only deal with British cars. So the
negation will not contain any reference to foreign cars. For instance,
the statement

All foreign cars are well made

is not the negation of our original statement. Indeed, knowing

whether our original statement is true or false in no way helps us to
decide the truth or falsity ofthe above statement. True, 'foreign' is the
negation of 'British' (in Britain, anyway), but we are trying to negate
the assertion as a whole, not some adjective occurring in it.)
So far we have considered three basic words and made their
meaning precise: and (/\, &), or ( v), not (~). We refer to these
operations as conjunction, disjunction, and negation, respectively.
Thus ¢ /\ t/J is the conjunction of the statements ¢ and t/J, ~ ¢ is the
negation of ¢, etc.
Our fourth word causes more initial confusion than all three of
these together. We need the word 'implies'. We want to be able to say
that statement ¢ implies statement t/J. Indeed implication is the way we
6 SETS, FUNCTIONS AND LOGIC
prove statements. We shall write

to mean that ¢ implies ljI. (Modern texts use a single arrow, ~, instead
of =>, but to avoid confusion with our function notation later we
adopt the more old-fashioned notation here.)
Now, we all know what ¢=>ljI means. Or do we? Well, it certainly
means

if ¢ is true, then ljI has to be true as well

Thus, if ¢ is a true assertion, then ¢ => ljI will be a true assertion
providing ljI is true. But wait; suppose for ¢ I take the true assertion
'J2 is irrational' and for ljI I take the true assertion '0 < 1'. Then is the
implication ¢ => ljI true? In other words, does the irrationality of 2 J
imply that 0 is less than I? Of course it does not. Again, what can be
said about the truth of the implication ¢ => ljI if ¢ is false? A confusing
state of affairs indeed. It would appear that ¢ => ljI is often mean-
ingless. But we cannot have meaningless statements floating about.
The truth or falsity of the implication ¢ => ljI should depend upon the
nature of ¢ and ljI, but not the meaningfulness of this implication. And
if we leave certain cases without a meaning we soon find ourselves in
an appalling mess. For instance, it is possible to construct a perfectly
logical argument which does deduce the fact that 0 < 1 from the
(J
assumption thatJ 2 is irrational. 2 being irrational will clearly play
a rather redundant role in such an argument, but so what?) By now,
the reader is no doubt thoroughly confused - which is good. Because
now he should be ready to accept the way out of the dilemma. We
shall make precise what is meant by the implication ¢ => ljI being 'true'
or 'false'. In all cases where the implication ¢=> ljI is 'meaningful', our
definition will agree with the 'usual idea'. But we shall eliminate all
possible confusions (in a strict sense, though you are forgiven if you
still feel a little bewildered by all this) by assigning (in a sensible
manner) a meaning to all eventualities.
The way we arrive at our definition is to consider not the notion of
implication but its negation. Let us try to assign a precise meaning to
the statement '¢ does not imply ljI', which we will write as
 USE OF LANGUAGE IN MATHEMATICS 7

(though we could use ~ (¢ ~ t/J) instead.) Well, leaving aside all

question of whether there is a 'meaningful' causal relation between ¢
and t/J (to avoidJ2 and 0 < 1 type difficulties), how can we be sure
that ¢ =/>t/J is a valid statement? More precisely, how should the truth
or falsity of the assertion ¢ =/> t/J depend upon the truth or falsity of ¢
and t/J? Well, ¢ will not imply t/J if it is the case that although ¢ is true, t/J
is nevertheless false. Please read this last sentence again. Now once
more. O.K., now we are ready to continue. (On second thoughts,
maybe you should read it a fourth time.) By letting the truth of
¢=/>t/J depend only upon the truth or falsity of ¢ and t/J, we have re-
moved all uncertainties about whether there is really a 'sensible'
relation between ¢ and t/J. And our notion of ¢=/>t/J certainly agrees
with all special cases where we do have a 'meaningful' relationship.
Having defined the truth or falsity of ¢ =/> t/J we obtain that of ¢ ~ t/J
by just taking the negation. ¢ ~ t/J will be true exactly when ¢ =/> t/J is
false. Examination of this definition leads to the following
conclusions:
¢ ~ t/J will be true whenever one of the following holds:
(1) ¢ and t/J are both true.
(2) ¢ and t/J are both false.
(3) ¢ is false and t/J is true.
The points to note are:
(a) We are defining what 'implies' should mean.
(b) To avoid difficulties, we base our definition solely on the notion of
truth and falsity.
(c) Our definition agrees with our intuition in all 'meaningful' cases.
Closely related to implication is the notion of 'equivalence'. Two
statements ¢ and t/J are said to be equivalent, written ¢~t/J (or ¢~t/J
in modern texts), if ¢ ~ t/J and t/J ~ ¢. By looking back at the definition
of implication, this means that ¢ and t/J are equivalent ifthey are both
true or both false. The three remarks (a), (b), (c) above apply to
equivalence just as to implication.

Exercise 1.1
(1) Express in a concise manner the meaning of the following
statements:
8 SETS, FUNCTIONS AND LOGIC

(a) (n> 0) !dn < 10)

(b) (3 < 4) A (3 < 6)
(c) (e < 4) A (e 2 < 9)
(d) (n > O)v (n> 1)
(e) (n < O)v (n> 0)

(2) Which of the following are true and which are false?
(a) (n 2 > 2)~(n > 1'4)
(b) (n 2 < O)~(n = 3)
(c) (n 2 > 0)~(1 + 2 = 4)
(d) (n < n2)~(n = 5)
(e) (e2;;:::O)~(e<O)
(I) ~ [(5 is an integer)~(52;;::: 1)]
(g) (the area of a circle of radius 1 is n)~(3 is a prime)

1.2 Properties of the language

So far we have taken five common concepts, and, or, not, implies,
equivalence, and made their meanings precise. Thus, whenever
precision is necessary, we can use these words with absolute
conviction: there should be no possible cause for confusion (except
due to misunderstanding of the concepts, which can only be overcome
by experience on the part of the student). Of course, our precise
'language of mathematics' will include other 'symbols' or 'words' such
as ~, =, less than, n, e, function, etc., but these all have a precise
definition already (since they are mathematical concepts). It is only
those parts of the 'language' which we take from common usage which
need clarification and eventual definition. There are two further
concepts which we take from everyday speech, but we shall postpone
those until later. In the meantime we consider the language developed
so far. That is, we investigate the consequences of our formal
definitions, and also introduce some common terminology.
We consider first the behaviour of negation. What is the meaning of

~(¢ A t/I)
where ¢ and t/I are some mathematical statements?
Literally, ¢ A t/I means 'both ¢ and t/I are true', so ~(¢ A t/I) means
'it is not the case that both ¢ and IjJ are true'. Well, if they are not both
 USE OF LANGUAGE IN MATHEMATICS 9

true, thenat least one of them must be false. But to say 'at least one of ¢
and IjJ is false', is clearly the same as saying 'at least one of ~ ¢ and
-> IjJ is true' (by our definition of negation). By our meaning for 'or',
this can be expressed as (~¢) v (~IjJ). Thus

are equivalent (i.e. mean the same).

Likewise it can be shown (exercise: carry out the required logical
argument) that

are equivalent.
Thus, negation has the effect that it changes v into 1\ and
changes 1\ into v . Now re-read the above 'proof' that ----,(¢ 1\ 1jJ) and
(----,¢) v (----,IjJ) are the same.

(Question: what does ~ (~ ¢) say?)

The effect of negation on implication is already bound up with the
definition of implication.
By our definition

is the same as

And

IS the same as

Of course, once we have made the meanings of various words precise,

and introduced abbreviations, we are free to alter our notation if it
IO SETS, FUNCTIONS AND LOGIC

seems helpful. Thus, we usually write

instead of

~(4)=I/I)

Likewise, we use the more familiar

x=/=y

instead of

~(x = y)

Another example: in dealing with real numbers, we usually write, say,

instead of

But we would probably write

~(a < x ~ b)

instead of

as the latter would appear to be rather unclear as to its meaning. (We

could make this precise, but it still seems rather inelegant, and as such
is best avoided.)
=
There is some terminology associated with and - which should
be mastered straight away, as it pervades all mathematical discussion.
We can read 4>=1/1 as '1/1 holds if 4> holds', i.e.

1/1 if 4>
 USE OF LANGUAGE IN MATHEMATICS 11
Likewise 1/1 => 4> can be read as

4> if 1/1

The following way of reading 4> -= IjJ follows now from the definition of
4> -= 1/1 as (4) => 1jJ) /\ (1jJ => 4> ):
Read 4>-=1jJ as

4> iffi IjJ

(i.e. if /\ fi, reversing the direction.) In fact it is more common to write

4> iff 1/1

(dropping the second i). Of course, it is rather difficult in giving a
lecture to distinguish between 'if' and 'iff. But we do not read 'iff'
aloud as a prolonged 'if'. We make the following observation. We can
read 4> -= 1/1 as

IjJ if and only if 4>

The 'if' comes from the 4> => 1jJ, the 'only if' coming (in the presence of
the 'if') from the IjJ => ¢. Of course, when we have an equivalence, the
order does not matter, so we could also write (or say)

¢ if and only if IjJ

This is how we read 'iff'. So:

(a) We write 'iff'.
(b) We read it as 'if and only if'.
(c) We mean 'they are equivalent'.
Now, the use of 'iff' causes no problems once the student knows it
means 'equivalent' (or 'implication both ways'). (The usage of '1jJ if ¢'
to mean '4> implies 1jJ' is so rare that it can be ignored just now.) This
cannot be said of our next pair of words.
Consider the implication ¢ => 1/1. What this says is that for IjJ to be
true it suffices that ¢ be true. Or, ¢ is a sufficient condition for 1jJ. It also
says that in order for ¢ to be true, it is necessary that IjJ be true (though
12 SETS, FUNCTIONS AND LOGIC
perhaps not sufficient!) So: t/J is a necessary condition for cPo The words
'necessary' and 'sufficient' in this context are very widespread, which
is a pity because in our experience everyone (including the experts)
has to stop and think carefully which is which. Here it is in a diagram

cP =>

1
sufficient necessary

(Think of the word 'sun'. This will remind you of the order.) So, if you
must show that cP is a necessary condition for t/J you must prove t/J => cPo
And to show that cP is a sufficient condition for t/J you must prove cP =>
t/J. Still worried? Fortunately, you usually need to show that t/J is both
necessary and sufficient for cPo (To put it another way, mathematicians,
afraid of showing themselves up by getting things the wrong way
round, usually only use these words together: in which case the
meaning is the same as 'iff.) So, if you need to show that t/J is necessary
and sufficient for cP, what is required is a proof of the implication both
ways. (But beware the sadistic setter of examination questions! Be
prepared!)
And so to some light relief to finish the section. Since we have
defined all of our logical connectives ( 1\, V , ~, =>, ¢» by reference to
truth and falsity alone, and not to meaning, it is possible to represent
(or illustrate) them by means of a table: a truth table. We introduce
two symbols: T, to denote 'true' and F to denote 'false'. The definition
of cP 1\ t/J can be illustrated by the table:

T T T
T F F
F T F
F F F

In the first two columns appear all the possible combinations of values
of T and F which the two statements cP and t/J can have. In the third
column we see the value cP 1\ t/J achieves according to each assignment
ofT or F to cP and t/J. Thus, we see that cP 1\ t/J is T only when both cP
 USE OF LANGUAGE IN MATHEMATICS 13

and tjJ are T. Similarly, the definition of ~ ¢ can be represented thus:

T F
F T

One can go on to construct truth tables for more complicated

expressions. Consider, for example, the expression (¢ /\ tjJ) v(~¢).
We can build its table column by column as follows:

T T T F T
T F F F F
F T F T T
F F F T T

We can also draw up tables for expressions such as (¢ /\ tjJ) V e, but if

there are n 'primitive statements' involved there will be 2" rows in the
table, so already (¢ /\ tjJ) ve needs 8 rows!
Truth tables can be useful in checking that two rather complex
statements are equivalent. For (by our definition of equivalence) two
statements will be equivalent if they have the same truth table. For
example, we can demonstrate the equivalence of

~(¢ /\ tjJ) and (~¢) v (~tjJ)

as follows:

* *
¢ tjJ ¢/\tjJ ~ (¢ /\ tjJ) ~¢ ~tjJ (~¢)v(~tjJ)

T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

The two columns marked * being identical shows that the two
expressions are equivalent.
14 SETS, FUNCTIONS AND LOGIC
Exercise 1.2
(1) Which of the following conditions is necessary for the natural
number n to be divisible by 6?
(a) n is divisible by 3
(b) n is divisible by 9
(c) n is divisible by 12
(d) n = 24
(e) n 2 is divisible by 3
(0 n is even and divisible by 3
(2) In (1), which conditions are sufficient for n to be divisible by 6?
(3) In (1), which conditions are necessary and sufficient for n to be
divisible by 6?
(4) Let m, n denote any two natural numbers. Prove that mn is odd iff
m and n are odd.
(5) With reference to (4), is it true that mn is even iffm and n are even?
(6) Show that </1¢!>t/I is equivalent to (-, </1) ¢!> ( - , t/I). How does this
relate to your answers to questions (4) and (5) above?
(7) Draw truth tables to illustrate the following: (a) </1 v t/I; (b) </1 => t/I;
(c) </1¢!>t/I.
(8) Use truth tables to prove that the following are equivalent:
(a) ~(</1=>t/I) and </1 A (-,t/I)
(b) </1=>(t/I A 0) and (</1=>t/I) A (</1=>0)
(c) (</1 v t/I) =>0 and (</1 =>0) A (t/I =>(J)
(9) Verify the equivalences in (b) and (c) above by means ofa logical
argument. (That is, in (b) say, assuming </1 and concluding t/I A (J
is the same as both deducing t/I from </1 and 0 from </1.)
(10) Use truth tables to prove the equivalence of

(11) Use truth tables to show that </1=>t/I and t/I=></1 are not
equivalent. Give an example of statements </1 and t/I such that
</1 => t/I is true but t/I => </1 is false.
(12) Connected with question (11), which of the following are
equivalent?

(a) </1 A t/I and t/I A </1

(b) </1 v t/I and t/I v </1
 USE OF LANGUAGE IN MATHEMATICS 15

1.3 The language of mathematics: part 2

And so to the final part of our language. We introduce the two
quantifiers. In mathematics we frequently make existence assertions,
e.g.
the equation x 2 + 2x + 1 = 0 has a real root

or, to put it another way,

there exists a real number a such that a2 + 2a + 1 = 0

or,
/2 is rational

which does not look much like an existence statement until we write it
in the form

there exist natural numbers p and q such that/2 = p/q

The first example here is a true existence statement (takea = - 1); the
second is false (as we prove later). (Remark: the second example is not
unique; there are many mathematical statements which are really
existence assertions, but which do not appear so on the surface.)
We use the symbol

to mean

there exists an x such that

or, if we want to specify that kind of x, we write for instance

(3XE,;V)

to mean

there exists a natural number x such that

(Here.IV denotes the set of natural numbers, and 'E%' means 'is an
element of %'. See later for a discussion of basic set theory.)
16 SETS, FUNCTIONS AND LOGIC
For instance, to say that the equation x 2 + 2x + 1 = 0 has a real
root we would write

(3xE81)(X 2 + 2x + 1 = 0)

(81 denotes the set of real numbers.)

Notice that our symbol is just a back-to-front E, which denotes
Exists, of course.
As well as saying that certain objects exist, we also need to say that
something holds for all x. We use the symbol

"Ix

to mean

for all x it is the case that ...

And if we wish to specify what sort of x we are considering, we write,

for instance

(VXEJV)

to mean

for all natural numbers x it is the case that ...

For instance, to say that J2 is irrational we can write

(VPEJV)(VqEJVK.,i2 -+ p/q)
To avoid proliferation of notation, we would generally abbreviate this
to

(Vp, qEJV)(j2 -+ p/q)

Notice that V is just an upside-down A, coming from All.

Exercise 1.3
(1) Express the following as existence assertions:
 USE OF LANGUAGE IN MATHEMATICS 17
(a) The equation x 3 = 27 has a natural number solution.
(b) 1000000 is not the largest natural number.
(c) the natural number n is not a prime.
(2) Express the following as 'for all' assertions:
(a) The equation x 3 = 28 does not have a natural number
solution.
(b) 0 is less than every natural number.
(c) the natural number n is prime.

The symbol 3 is called the existential quantifier; V is the universal

quantifzer. Most statements in mathematics involve combinations of
both quantifiers. For instance, to make the assertion that there is no
largest natural number needs two quantifiers, thus:

(VmE,;V,)(3nE%)(n > m)

This reads: for all natural numbers m it is the case that there exists a
natural number n such that n is greater than m.
Notice that the order in which the quantifiers appear is of
paramount importance. If we switch the order in the above we get

(3nE%)(VmE%)(n> m)

This asserts that there is a natural number which exceeds all natural
numbers, which is clearly false!

Exercise 1.4
(1) Express the following using quantifiers:
(a) The equation x 2 + a = 0 has a real root for any real number a.
(b) The equation x 2 + a = 0 has a real root for any negative real
number a.
(c) Every real number is rational.
(d) There is an irrational number.
(e) There are infinitely many irrational numbers. (This one
looks quite complex.)
(2) Let C be the set of all cars, let B(x) mean that x is British, and let
M(x) mean that x is badly made.
18 SETS, FUNCTIONS AND LOGIC
Express the following in symbolic form:
(a) All British cars are badly made.
(b) All foreign cars are badly made.
(c) All badly made cars are British.
(d) There is a British car which is not badly made.
(e) There is a foreign car which is badly made.

Particularly in Analysis it is important to be able to negate

statements involving quantifiers (and end up with the correct answer).
Of course, one can negate any statement by simply putting a negation
symbol in front. But what we want is a positive assertion, not a negative
one. What is meant by 'positive' here should become clear from our
examples. (Roughly speaking, a 'positive' statement is one containing
no negation symbol, or else one in which the negation symbols are as
far inside the statement as possible, without resulting in a cumber-
some expression.)
Let A(x) denote some property of x (e.g. A(x) could say that x is a
real root of the equation x 2 + 2x + 1 = 0). Suppose it is not the case
that \fxA(x) is true. That is, assume

~ [\fxA(x)]

Then, if it is not the case that all x satisfy A(x), what must happen is
that at least one ofthe x must fail to satisfy A(x). In other words, for at
least one x, ~ A(x) must be true. In symbols, this is

3x[~A(x)]

Hence ~[\fxA(x)] implies 3x[ ~A(x)]. Now suppose

3x[ ~A(x)]

Thus there will be an x for which A(x) fails. Hence A(x) does not hold
for every x (it fails for the x where it fails!) In other words, it is false that
A(x) holds for all x. In symbols,

~ [\fxA(x)]

Thus 3x[ ~A(x)] implies ~[\fxA(x)]. Our two implications com-

bine now to produce the equivalence

~ [\f x A (x)] ~ 3x[ ~ A (x)]

 USE OF LANGUAGE IN MATHEMATICS 19

A similar argument shows

--,.[3xA(x)] ~ 'v'x[ --,.A(x)]

(Exercise: Provide this argument.)

Now let us return to our original problem about the British cars.
We wish to negate the statement

All British cars are badly made

Let us formulate this symbolically using the notation of

Exercise 1.4(2). If you got part (a) of this question correct, you should
have the formulation

(\fxEC)[B(x)= M(x)]

Negating this gives

(3XEC) --,. [B(x)= M(x)]

(One common cause of confusion. Why do we not say (3x¢C)? The

answer is that the 'EC' part simply tells us which kind of x we are to
consider. Since our original statement concerns British cars, so will its
negation.)
Consider now the part

--,. [B(x) =M(x)]

We have seen already that this is equivalent to

B(x) 1\ [ --,. M(x)]

Hence as our negated statement (in positive form now) we get

(3XEC)(B(x) 1\ [--,.M(x)])

In words, there is a car which is British and is not badly made; i.e.
there is a British car which is not badly made.
We can also obtain this result directly as follows. If it is not the case
that all British cars are badly made, then it must be the case that at
20 SETS, FUNCTIONS AND LOGIC
least one of them fails to be badly made. Hence, as this argument
reverses, the required negation is that at least one British car is not
badly made.
In order to negate statements with more than one quantifier, the
idea is to handle each quantifier in turn: the effect being that the
negation symbol jumps inwards, changing V to 3 and 3 to V as it jumps
over. Thus, for example

~ [Vx3y Vz A(x, y, z)]<:>3x ~ [3y Vz A(x,y, z)]

<:>3x Vy~[Vz A(x, y, z)]
<:>3x Vy 3z~ A(x. y, z)

Exercise 1.5
(1) Negate the following statements and put your answer into
positive form:
(a) All students are communists.
(b) One of my friends does not have a car.
(c) Some elephants do not like currant buns.
(d) Every triangle IS isosceles.
(e) Some of the students in the class are not here today.
(0 All of the spark plugs in my car are working correctly.
(g) (VxEJII')(3YEJV)(X + y = 1)
(h) (Vx > 0)(3y < O)(x + y = 0) (x, y denote real number
variables).
(i) 3x(Va> O)(lxl < a) (see Chapter 2, Section 2.3 for a definition
of Ixl).
m (Vx, YEJV)(3zEJV)(X + y = Z2).

1.4 Proofs in mathematics

A proof in mathematics is a logically sound argument which
establishes the truth of the statement in question. There are many
types of 'proofs'. Our purpose here is just to mention a few of these
and see how they relate to our discussion of language.
Suppose first we wish to establish the truth of an assertion

Well, since this will be true whenever ¢ is false, by our definition, we

need only consider the case when ¢ is true. That is we can assume ¢.
 USE OF LANGUAGE IN MATHEMATICS 21
For the implication to be valid now IjJ must also be true. Thus, using
our assumption that ¢ is true we must now present an argument
which demonstrates the truth of 1jJ. This of course accords with our
everyday understanding of 'implication'. So, when we come to prove
implications, there is no problem.
For example, let us prove the statement

(x and yare rational numbers)=(x + y is a rational number)

Assume x and yare rational numbers. Then we can find integers

p, q, m, n such that x = p/m, y = q/n. Then

p q pn + qm
x+ y=-+~=---
m n mn

Hence, as pn + qm and mn are integers, we conclude that x + y is a

rational. The statement is proved.

Implications involving quantifiers are often best handled by using

the equivalence of ¢ = IjJ with (~IjJ)=( ~ ¢). Suppose, for instance, we
wish to prove the implication

(sin () =1= 0) = (V'nEX)(() =1= nn)

This statement is equivalent to

[ ~ (V nEX)(() =1= nn)] = ~ (sin () =1= 0)

which reduces to the positive form

(3nE,A/)(() = nn)=(sin () = 0)

which is an implication we know to be correct. This proves the

original implication by virtue of what equivalence means: in order to
prove a statement it is enough to prove any equivalent statement.

Another common method of proof is the so-called method of proof

by contradiction (reductio ad absurdum). This is essentially a disguised
version of the last type of proof. We wish to prove some statement ¢
but cannot see how to begin. So we assume ~ ¢ and proceed to deduce
some obviously false statement (e.g. 0 = 1). Since our conclusion is
22 SETS, FUNCTIONS AND LOGIC
false it follows (assuming our reasoning is sound) that our initial
assumption of ~ cp has to be false. Hence cp is shown to be true. This
relates to the above method of 'proving an equivalent statement' as
follows. Let F denote any false statement, T any true statement. We
assume ~ cp and deduce F. So we prove the implication

But this is logically equivalent to

i.e. to

=
Hence our proof also establishes the implication T cp. But T is true,
so the truth of the implication means that cp is true, as required.
A good illustration of the method of proof by contradiction is
furnished by the following result, promised earlier.

Theorem 1.1
J 2 is irrational.
Proof
J
Assume, on the contrary, that 2 were rational. Then we can find
natural numbers p and q such that

We may assume that any common factors in p, q have been cancelled

out. Squaring gives

Thus

(1.1)

Thus p2 is even. Hence p must be even, since (odd)2 = (odd). Thus

 USE OF LANGUAGE IN MATHEMATICS 23
there is a natural number r such that p = 2r. Substituting in Equation
(1.1) gives

Cancelling 2 gives

Thus q2 is even. Hence q must be even. But p is even and p and q have
no common factors, so we have a contradiction. Hence our original
assumption thatJ2 was rational must be false. In other words,J2
must be irrational. QED.
Proving existence assertions is often straightforward. In order to
prove the statement

3x A (x)

It is enough to find one x which satisfies A (x). For instance, if we wish

to prove that

there exists an irrational number

it suffices to quote the above theorem. Not only does this tell us that
an irrational number exists, it provides us with a specific example.
This is not always the case. There are many instances in mathematics
where one knows that, say, a real number exists which satisfies a
certain property, but one has no idea what such an x looks like, or
even whether it is positive or negative. Indeed, advanced mathematics
abounds with examples. We content ourselves here with a trivial one.
Let A be the statement that in the decimal expansion of TC the digit 3
appears infinitely many times. Consider the existence assertion

3n [A => n = 0) /\ (~A => n = 1)]

We can prove this as follows. Either A or ~ A.1f A, then n = 0 suffices.

If ~ A, then n = 1 suffices. Hence, as 0 and 1 certainly exist, we have
proved the existence statement. But at the present state of our
knowledge we do not know whether or not A is true, so we cannot say
which of 0 or 1 satisfies the statement. (Clearly, they cannot both
24 SETS, FUNCTIONS AND LOGIC
satisfy it!) It is possible that one day a proof of A (or of ~ A) will be
found, in which case we will have our example. But a proof of A or of
--. A would doubtless be rather deep, and certainly much less trivial
than our above existence proof.

Finally, how does one prove a statement of the form

VxA(x)?

One possibility is to take an 'arbitrary' x and show that it must satisfy

A(x). For instance, suppose we wish to prove the assertion

We can do this as follows. Let n be an arbitrary natural number. Then

n2 is a natural number. Hence m = n2 + 1 is a natural number. But
m> n2 , so we have shown that

This is a proof because our original n was quite arbitrary: we said

nothing at all about n: it could be any natural number: hence the
argument is valid for all ne.K. This is not the same as picking a
[Xlrticular n. If we had chosen, say, n = 37, the proof would not have
been valid - even though we had chosen 37 quite at random. For
instance, suppose we wanted to prove

(Vne.K)(n 2 = 81)

By picking at random a particular n we might be unlucky enough to

pick n = 9. But this does not prove the statement of course, because
our choice was an arbitrary choice (albeit an unlucky one) of a
[Xlrticular n, and not a 'choice' of an arbitrary n. When we say 'let n be
arbitrary' we use the symbol n throughout, and assume also that the
'value' of n remains constant throughout, but we make absolutely no
restriction on what the value of n is.

There are other possibilities. Statements of the form

(Vne.K)A(n)
 USE OF LANGUAGE IN MATHEMATICS 25

are often proved by induction. The idea here is to first prove A(1), and
then prove the statement

(VnEJII)[A(n)=;.A(n + 1)]
That this proves (VnEJII)A(n) may be reasoned as follows. We proved
A(I). But we know that A(1)=;.A(2) is true. Hence A(2) is true. But
A(2)=;.A(3) is true. Hence A(3) is true. And so on right through the
natural numbers. As an example let us use the method of induction to
prove a simple theorem.

Theorem 1.2
If x > 0 then for any nEJII,

(1 + xt + 1 > 1 + (n + 1)x
Proof
For n = 1 the binomial theorem gives

(1 + xt + 1 = (1 + X)2 = 1 + 2x + x 2 > 1 + 2x = 1 + (n + l)x

(since x 2 > 0). Hence the statement is true for n = 1. We now wish to
prove the implication

(VnEJII)[A(n)=;.A(n + 1)]
where A(n) is the statement

(1 + x)" + 1 > 1 + (n + l)x

To do this we take an arbitrary (!) n in JII. We must prove the

implication

A(n)=;.A(n + 1)

To do this we assume A(n) and try to deduce A(n + 1). We have

(1 + xt + 2 = (1 + xt + 1 (1 + x)
> (1 + (n + l)x)(1 + x) [by A(n)]
26 SETS, FUNCTIONS AND LOGIC

= 1 + (11+ l)x + x + (n + l)x 2

= 1 + (n + 2)x + (n + 1)x 2
> 1 + (n + 2)x

This proves A (n + 1). (Question: The assumption x > 0 was used in the
above argument. Where?) Hence by induction the theorem is proved.
The following summarizes the method of proof by induction. You
wish to prove that some statement A(n) is valid for all natural
numbers n. First you establish A(1). This is usually just a matter of
trivial observation. You then present an algebraic argument which
establishes the implication

A(n)=>A(n+ 1)

for any n. In general, you do this as follows. Assume A(n). Look at the
statement of A(n + 1), and somehow try to reduce it to A(n), which has
been assumed true, and thereby deduce the truth of A(n + 1). This
having been accomplished, the induction proof is complete.
In setting out an induction proof formally, three points should be
remembered:
(1) State clearly that the method of induction is being used.
(2) Prove the case n = 1 (or at the very least make the written
observation that this case is obviously true).
(3) (the hard part) Prove the implication
A(n)=>A(n + 1)
Let us look at one further example to illustrate the above points. We
prove the following well known result from algebra.

Theorem 1.3

Every natural number greater than 1 is a product of primes.

(Remark: At first it might seem that the statement to be proved by
induction is

A(n) : n is a product of primes

However, as will shortly become clear, it is more convenient to prove

 USE OF LANGUAGE IN MATHEMATICS 27

by induction the statement

B(n): every natural number m such that 1 < m ~ n

is a product of primes

So here goes; and from now on we shall set out our proof in a correct
fashion.)

Pro()[
We prove, by induction, that B(n) is true for all natural numbers n > 1,
where B(n) is the statement

all natural numbers m such that 1 < m ~ n

are products of primes

This clearly proves the theorem.

For n = 2, the result is trivial: B(2) holds because 2 is prime. (Notice
that in this case we must start at n = 2 rather than the more common
n = 1, for obvious reasons.)
Now assume B(n). We prove B(n + 1). Let m be a natural number
such that 1 < m ~ n + 1. If m ~ n, then by B(n), m is a product of
primes. So in order to prove B(n + 1) we need only show that n + 1 is a
product of primes. If n + 1 is a prime there is nothing further to say.
Otherwise, there are natural numbers p, q, such that

1 < p, q < n + 1

and

n + 1 = pq

Now p, q ~ n, so by B(n), p and q are products of primes. But then

n + 1 = pq is a product of primes. This completes the proof of
B(n + 1).
The theorem is thus proved by induction.
(End of proof.)
Of course, in the above example, the implication

B(n) =B(n + 1)
28 SETS, FUNCTIONS AND LOGIC

was rather easy to establish. (Indeed, we considered B(n) rather than

the more 'obvious' A(n) mentioned earlier precisely in order to carry
through this simple argument.) In many cases, real ingenuity is
required. But do not be misled into confusing the proof by induction
of the main result, (\lnEJII)A(n), with the technical subproof of the
=
implication (\In E JII)[A(n) A(n + 1)]. Without an announcement of
the fact that induction is being used and an observation or proof that
A(1) is valid, any amount of technical cleverness at proving A(n)=
A(n + 1) is worthless [as a proof of the result (\lnEJII)A(n)].

So much for induction. One last remark concerning proofs of

statements of the form

\Ix A(x)

If all else fails, there is the method of contradiction. By assuming

~ \I x A(x) we get an x such that ~ A(x) (because -,. \Ix A(x) is
equivalent to 3x ~ A(x)). Now we have a place to start. The difficulty
is finding the finish (i.e. the contradiction).

Exercise 1.6
(1) The symbol
n

I
,~ 1
a,

is a common abbreviation for the sum

For instance,
n
I ,.2
r ~ 1

denotes the sum

Prove the following by induction:

 USE OF LANGUAGE IN MATHEMATICS 29

1
L
n
(b) 'v'nEJIf: r2 = -n(n + 1)(2n + 1)
r=1 6

(2) Prove by the method of contradiction that if x and yare real

numbers such that x + y is irrational, then at least one of x, y is
irrational. Does it follow that if x + y is rational, then at least one
of x, y is rational?
J
(3) Prove that 3 is irrational.
(4) Prove that there exist real numbers x and y such that x + y = y.
(5) Prove that there are infinitely many natural numbers n such that
Jn is irrational. How would you express this fact symbolically (no
words allowed)?

1.5 Mathematical truth

The notion of 'truth' is one which has occupied philosophers for
generations, and no doubt will continue to do so, and it is not our
present intention to enter into this rather bewildering are~. However,
we should say something about what a mathematician means when
he says some mathematical statement is true (or false). This requires a
little knowledge of the development of mathematics.
All mathematical concepts have their origin in the everyday world
around us. For example, the natural numbers arise from our desire (or
need) to count collections of objects, the rational numbers are
required in order to measure lengths, geometry and trigonometry
assist us in navigation, and so on. At the initial stage 'truth' means
'experimentally verifiable'. Thus we can demonstrate the 'truth' ofthe
assertion

1+2=3

by taking one apple and two oranges and noting that there are three
items altogether. But what about the assertion

1000000000 + 5 = 10oo0oo005?

Most of us would (I hope) agree that this statement is just as 'true' as

30 SETS, FUNCTIONS AND LOGIC
the previous one, though it is clearly out ofthe question to verify this
fact by counting. (If you disagree with this last claim, just add a few
more significant zeros.) So why do we so readily agree that the
equation is valid? Well, although the concepts of natural number and
addition arise out of everyday experience, they are really just idealized
concepts - figments of our imagination - whose properties and be-
haviour are postulated by us to correspond to natural phenomena.
(None of us has ever seen 'the number 10'. We may have seen ten
apples in a bowl. And we have just seen two symbols on a page which
we read as 'ten'. But 'the number 10' itself remains locked away
somewhere in our psyche.) The equation

1000000000 + 5 = 1000000005

is 'true' because it is a consequence of the properties which we

postulate for the natural numbers. Of course, the natural numbers
and addition are so very basic and familiar to us, that it is rare to
regard matters in quite this fashion ('rare', notice, not 'incorrect'). But
what about complex numbers? The equation

is 'true', but we cannot test this by experiment - even a hypothetical

experiment! In fact it is 'true' only in the sense that it can be proved to
be a consequence of the properties which we postulate the complex
numbers to have.
This brings us to the real nature of pure mathematics. In each area,
be it the theory of addition of integers, the theory of real numbers,
geometry, calculus, or whatever, we begin with a collection of
postulates (or axioms), setting down the properties the objects under
consideration are to have. These postulates are formulated either by
observation of some everyday event (as with the postulates for
addition of integers or for classical Euclidean geometry), or else by
consideration of what properties the system 'ought' to have (as with
the postulates for real numbers - see Chapter 3 - or for complex
numbers). From then on 'truth' means simply 'provable from the
postulates'. (There are also axioms for logical deduction - so the
notion of just what constitutes a 'proof' is also determined by means
of postulates, but at this stage you are probably best advised to stick
to whatever intuitive notions you have already regarding the nature
 USE OF LANGUAGE IN MATHEMATICS 31
of proof.) In the case of the natural numbers or the rational numbers,
the basic postulates are often never cited at the first year under-
graduate level, so you may have some difficulty in appreciating the
above remarks. But it is extremely likely that your Analysis course
will commence with some discussion of the postulates for the real
numbers, and then you will see how 'true' corresponds to 'provable
from the axioms'. (We discuss the real numbers briefly in Chapter 3.)
Our only concern now is that when you are next asked to prove
something, you will be puzzled as to where you should start.
Especially as you don't know 'all the axioms'. Don't worry! (In fact,
you probably will, but what more can I say?) Except in unusual
circumstances, a 'proof of something is simply a logical argument
which convinces us that the fact is true (for the system concerned). The
J
'proof given earlier that 2 is irrational is valid in this sense. True
enough, this 'proof used various properties of the natural numbers
(such as the square of an odd number being odd), which are only 'true'
because they follow from the postulates for the integers. But we all
'know' that (odd)2 = odd, so in this case there is no need to go right
back to the axioms to check it. As a general rule: let common sense be
the judge of what is or is not a proof After a little while you should have
no difficulties in deciding what you mayor may not assume in any
given instance. (Though even the experts can disagree on this matter -
and frequently do! A favourite pastime amongst mathematicians-
not unlike cock-fIghting-is to engage an analyst and a differential
equations expert in a 'discussion' as to where the former should begin
his lecture course: by introducing the postulates for the real number
system and deducing everything from them, or by assuming the
students 'know' enough about the real numbers already and building
on this knowledge.)
CHAPTER 2

Sets and functions

2.1 Sets
The concept of a 'set' is extremely basic and pervades the whole of
present day mathematical thought. Any well-defined collection of
objects is a set. For instance we have:

the set of all students in your class

the set of all prime numbers
the set whose members are you and my left foot

So long as we have some way of specifying the collection, then we say

it is a set. Our last example above has already made use of the notion
of 'membership'. If A is a set, then the members of the collection A are
called either the members of A or the elements of A. (With a concept as
simple as a set, there is no way to avoid circular definitions: but we all
know what is meant.) We write

XEA

to denote that x is an element of A.

Some sets occur frequently in mathematics, and it is convenient to
adopt a standard notation for them:
%: the set of all natural numbers (i.e. the numbers 1,2,3, etc.)
:!Z: the set of all integers (i.e. the positive and negative whole
numbers)
f2: the set of all rational numbers (i.e. 'fractions')
!!ll: the set of all real numbers
~: the set of all complex numbers

Thus,
XE!!ll

32
 SETS AND FUNCTIONS 33
means that x is a real number. And

(XE,q) 1\ (x > 0)

means that x is a positive rational number.

There are several ways of specifying a set. If it has a small number of
elements we can list them. In this case we denote the set by enclosing
the list of the elements in curly brackets; thus, for example,

{I, 2, 3,4, 5}

denotes the set consisting of the natural numbers 1, 2, 3, 4 and 5.

By use of 'dots' we can extend this notation to any finite set; e.g.

{I, 2, 3, ... , n}

denotes the set of the first n natural numbers. Again

{2, 3, 5, 7, 11, 13, 17, ... ,53}

denotes the set of all primes up to 53.

Certain infinite sets can also be described by the use of 'dots' (only
now the dots have no 'end'); e.g.

{2, 4, 6, 8, ... , 2n, ... }

denotes the set of all even natural numbers. Again,

{... , - 8, - 6, - 4, - 2, 0, 2, 4, 6, 8, ... }

denotes the set of all even integers.

In general, however, infinite sets (and many finite ones too) are best
described by giving the property which defines the set. If A(x) is some
property, the set of all those x which satisfy A(x) is denoted by

{xIA(x}}

Or, if we wish to restrict the x to those which are members of a certain

set X, we would write

{xEXIA(x)}
34 SETS, FUNCTIONS AND LOGIC

This is read 'the set of all x in X such that A (x)'.

For example:

% = {xE~lx > 0]
f2 = {xE~1 (3m,nE~)((m > 0) /\ (mx = n))}
{J2, -J2} = {xE~lx2 = 2}
{I, 2, 3} = {xE%lx < 4]

Two sets, A, B are equal, written A = B, if they have exactly the same
elements. As the above example shows, equality of sets does not mean
that they have identical definitions; there are often many ways of
describing the same set. The definition of equality reflects rather the
fact that a set is just a collection of objects.
If we have to prove that the sets A and B are equal, it is often quite
difficult to prove in one go that they have the same elements. What is
usually done is to split the proof into two parts:
(a) Show that every member of A is a member of B.
(b) Show that every member of B is a member of A.

Taken together, (a) and (b) clearly imply A = B. (The proof of (a), (b) is
usually of the 'take an arbitrary element' variety. To prove (a), for
instance, we must prove (VxEA)(XEB); so we take an arbitrary
element x of A and show that x must be an element of B.)

Exercise 2.1
(1) Let

P = {nENI(n > 1) /\ (VX,YE.%)(XY = n=>(x = 1 v y = I))}

What well-known set is P?

(2) Let

P = {xE~lsinx = O}, Q = {mrlnE~}

What is the relationship between P and Q?

(3) Let
A = {xE~I(x > 0) /\ (x 2 = 3)}

Give a simpler definition of A.

 SETS AND FUNCTIONS 35
(4) Let

A = {o, t, f, s, e, n}

Give an alternative definition of the set A. (Hint: this is connected

with AI, but is not entirely mathematical.)

The set notations introduced have obvious extensions. For in-

stance we can write

f2 = {minim, nE~, n =1= O}

and so on.

It is convenient in mathematics to introduce a set which has no

elements: the empty set (or null set). There will only be one such set, of
course, since any two such will have exactly the same elements (!) and
thus be (by definition) equal. The empty set is denoted by the
Scandinavian letter

o
The empty set can be 'defined' in many ways; e.g.

0= {xE9llx 2 < O}
0={xEAlll<x<2}
0= {xix =1= x}

Notice that 0 and {0} are quite different sets. 0 is the empty set: it
has NO members. {0} is a set which has ONE member. Hence

0=1= {0}
Indeed, the correct relation here is

0E{0}

(The fact that the element of {0} is the empty set is irrelevant in this
connection: {0} does have an element, 0 does not.)

A set A is called a subset of a set B if every element of A is a member

of B. For example, {t, 2} is a subset of {l, 2, 3}. We write
36 SETS, FUNCTIONS AND LOGIC
A~B

to mean that A is a subset of B. If we wish to emphasize that A and B

are unequal here, we say that A is a proper subset of B and write

AcB

(This usage compares with the ordering relations ~ and < on 9l.)
Clearly, for any sets A, B, we have

A = B itT (A s:;; B) A (B s:;; A)

Notice also that for any set X,

0s:;;X

Exercise 2.2
(1) List all subsets of the set {I, 2,3, 4}.
(2) List all subsets of the set {I, 2, 3, {I, 2} }.
(3) Prove (by induction) that a set with exactly n elements has 2ft
subsets. (The set of all subsets of a set X is called the power set of X,
denoted by .o/'(X).)

2.2 Operations on sets

There are various natural operations we can perform on sets. (They
correspond roughly to addition, multiplication, and substraction for
integers.)
Given two sets A, B we can form the set of all objects which are
members of either one of A and B. This set is called the union of A and
B and is denoted by

AuB

Formally, this set has the definition

A uB = {XI(XEA) v (xEB)}

(Now the reader gets his first real inkling as to why we defined our
precise use of 'or' to mean the 'inclusive-or'.)
 SETS AND FUNCTIONS 37
This can be illustrated diagrammatically as follows. We first of all
introduce the notion of a universal set. It is rare in mathematics to
discuss 'arbitrary sets'. One is generally only interested in sets of reals,
or sets of integers, or so on. Now, when discussing sets of reals, it is
convenient to imagine that there is nothing else in the world except
reals. For one thing, this prevents our having to keep saying 'x is a
real'. When we do this, we announce the fact by the rather pompous
phrase, 'Let [JIt be the universal set for the discussion'. This means that
any set mentioned in the ensuing discussion will be assumed to be a
subset of [JIt. Likewise if we fix :!l' as universal set, or fi, etc. Thus,
there is not one universal set: rather we introduce one such whenever
it is convenient to ignore all the possibilities other than the ones
concerned. (If this is still confusing to you, it should become clearer
when we look at set-theoretic complements in a short while.) And now
to our diagram. Fix some universal set U. We represent U by means of
a rectangle on the page. The elements of U are the 'points' within the
rectangle. So, relative to our fixed universal set, all 'objects' lie inside
our rectangle. Sets (i.e. subsets of U) are denoted by encircling regions
within U.
In Fig. 2.1, the set A is represented by the interior of the left-hand
circle, the region shaded horizontally, and the set B is represented by
the interior of the right-hand circle, the region shaded vertically. The

Figure 2.1 Union and llltersection

38 SETS, FUNCTIONS AND LOGIC
set Au B is represented now by the total shaded region (which
includes a region which is shaded two ways here). Such a diagram-
matic representation of sets is called a Venn diagram.

Exercise 2.3
(1) What is the relationship between A and B illustrated by the Venn
diagram in Fig. 2.2?
(2) Draw a Venn diagram to illustrate the fact

AuBs;C

(3) Draw a Venn diagram to illustrate the fact

A s;BuC

The intersection of the sets A, B is the set of all members which A and B
have in common. It is denoted by

AnB

and has the formal definition

A nB = {xl (xEA) 1\ (xEB)}

Figure 2.2 Inclusion

 SETS AND FUNCTIONS 39
In Fig. 2.1, the set An B is represented by the region which is doubly
shaded.
Two sets A, B are said to be disjoint if they have no elements in
common: that is, if A nB = 0.

Exercise 2.4
(1) For each of the following pairs of sets A, B, find Au B and An B:
(a) {a,b,c},{c,d,e,f}
(b) {xE9flx < O}, {xE9flx ~ O}
(c) {1, 2, {1, 2, 3}}, {l, {1, 2}}
(2) Prove the following (for any sets A, B):

(Drawing a Venn diagram does not constitute a proof. It

illustrates the fact, but does not prove it. For a proof, a logical
argument is needed.)
(3) Prove the following statements:

An0=0
Au0=A
AnB=BnA
AuB=BuA
AnA=AuA=A

(4) Prove that if A, B, C are sets, then

(a) An(BnC)=(AnB)nC
(b) A u(BuC) = (A uB)uC

Illustrate these results by means of a Venn diagram.

(5) By considering the sets A = 9f, B =!!2, C = set of irrationals, show
that it is not always the case that

(A uB)nC = A u(BnC)

(6) Show that the equality (AnB)uC=An(BuC) is not always

valid.
40 SETS, FUNCTIONS AND LOGIC

Figure 2.3 Complement

Once we have fixed a universal set we can introduce the notion of

the complement of the set A. Relative to the universal set U, the
complement of a set A is the set of all elements of U which are not in A.
This set is denoted by A', and has the formal definition

A' = {xEUlx¢A}

(Notice that we write x¢A instead of ~(xEA), for clarity.)

In Fig. 2.3, A' is represented by the un shaded region.

The following theorem sums up the basic facts about the three set
operations just discussed.

Theorem 2.1
Let A, B, C be subsets of a universal set U.

(1) Au(BuC)=(AuB)uC
(associative property of union)
(2) An(BnC)=(AnB)nC
(associative property of intersection)
(3) AuB=BuA
(commutative property of union)
(4) AnB=BnA
(commutative property of intersection)
(5) A u(B n C) = (A uB)n(A u C)
(distributive property for u over n)
 SETS AND FUNCTIONS 41
(6) An(BuC) = (AnB)u(AnC)
(distributive property for n over u)
(7) (A uB)' = A' nB'
(8) (AnB)' = A'uB'
«7) and (8) are called the de Morgan laws)
(9) AuA' = U
(10) AnA' = 0
(11) (A')' = A
(idempotence of complement)

Proof
The proof ofparts (1) to (4) and of parts (9) to (11) are left as an exercise
(some have already been given in Exercise 2.4). In each of the
remaining cases we take the statements in pairs and produce a Venn
diagram illustration for the one and a rigorous proof for the other.
Consider part (5). We can represent this diagrammatically as in
Fig. 2.4. We have drawn the diagram to illustrate the most general (i.e.
the most complex case), which is when all the sets have elements in
common with each of the other sets. We have also numbered each of
the regions. Now let us see which regions correspond to which sets.

Figure 2.4 Diagrammatic representation of the distributive law

42 SETS, FUNCTIONS AND LOGIC
Well,

A is the regions 1, 2, 3, 4

and

B n C is the regions 3, 6 (common to Band C)

So,

Au (B n C) is the regions 1, 2, 3, 4, 3, 6, i.e. 1, 2, 3, 4, 6

Again,

Au B is the regions 1,2, 3,4, 6, 7

and

Au C is the regions 1, 2, 3, 4, 5, 6

so

(A u B) n (A u C) is 1, 2, 3,4, 6 (common to both)

But this is the same region that we obtained for Au (B n C) above.

This illustrates (5). We leave it to the reader to provide a formal proof
(which he can model on our proof of (6) below).
Consider part (6). Here is a rigorous proof. Let

D=An(BuC)
E = (AnB)u(A nC)

We prove first that D s;; E. Let XED. Then xEA and xEBuC. Since
xEBuC, either XEB or XEC, or both. In case xEB, we have xEA and
xEB, so XEA nB. On the other hand, ifx¢B, then we must have XEC,
so XEA and XEC, giving XEA n C. In either of these cases, xEE. Hence
D s;; E. Now we prove E s;; D. Let xEE. There are two cases. Suppose
first that XEA nB. Then XEA and xEB, so xEA and XEBu C, so xED.
On the other hand, ifx¢A nB, then xEA n C, so again we obtain xEA
and xEBuC, giving xED. Hence Es;;D.
 SETS AND FUNCTIONS 43

u
4

Figure 2.5 Diagrammatic representation of the de Morgan laws

Since D s; E and E s; D, it follows that D = E, which proves (6).

We turn now to (7) and (8). We illustrate (7) by means of a diagram
(Fig. 2.5), and leave it to the reader to provide a rigorous proof.
Clearly, A u B is regions 1, 2, 3. Thus, (A u B)' is region 4. (the only
remaining region).
Again, A' is regions 3, 4, and B' is regions 1, 4, so A' n B' is region 4
(the common region); this illustrates (7).
Now we prove (8). Let xE(AnB)'. Thus x¢AnB. Hence

~((xEA) /\ (xEB))

This is the same as

In other words

(x¢A) v (x¢B)

I.e.

(xEA') V (xEB')

I.e.

XEA'uB'
44 SETS, FUNCTIONS AND LOGIC
This shows that (A nB)' £; A' UB'. The above steps may be reversed
to give A' u B' £; (A n BY, thereby completing the proof.

Exercise 2.5
(1) Illustrate the proofs of parts (6) and (8) of Theorem 2.1 by means
of a Venn diagram.
(2) By using the set identities established in the theorem, show that

[A u(BnC)] nC = (A uB)nC

(What is required here is an algebraic proof, not a set-theoretic

one.)
(3) Use the distributive laws to show that

(A uB)n(CuD) = (An C)u(AnD)u(Bn C)u(BnD)

Does the result remain valid if we interchange nand u here? If so,

justify this by an argument which does not involve a direct
calculation involving the sets concerned. If not, give an example
to justify your answer.

2.3 Functions
The concept of a function from real numbers to real numbers will be
familiar to you already. For instance the equation

y=x 2 +x + 1

determines a function from real numbers to real numbers. We can

draw its graph as in Fig. 2.6.
We are able to plot the graph of this function because, for each
value ofx in 9l we can calculate the corresponding value of y: we just
substitute the value of x concerned into the equation. So what the
above equation does is provide us with a general rule for calculating
values. (After all, x and yare just variables, not specific numbers.)
We can thus generalize the concept of a function as follows. Let A
and B be any non-empty sets. A function from A to B is a rule which
associates with each member of A a unique member of B. We make no
restrictions on the rule: the only crucial point is that the element of B
 SETS AND FUNCTIONS 45
Y

-3 -2 -1 o 2 3 x

-1

Figure 2.6 Graph of the function y = x 2 + X +1

which we associate with a given member of A must be unique. Now, in
the case of a function as above given by an equation, we can refer to
that function by giving its equation. But our definition allows for all
kinds of 'rules'. Hence it is convenient to introduce some notation.
Suppose we have a rule which associates with each member of the
non-empty set A a unique member of the set B. Let f denote this rule.
Then we say f is a function A to B. We write

to abbreviate this last sentence. If aEA, we denote the unique element

of B which the rule associates to a by

f(a)

Thus, in our original example above, f : ~ ..... 9f and

(This last equation reads: the value of the function f at x is the real
number x 2 + x + 1.)
Notice that we have not defined the concept of 'a function', but
rather 'a function from a set A to a set B'. This distinction should be
borne in mind at all times, as it affects our subsequent definitions to a
46 SETS, FUNCTIONS AND LOGIC

A f B

Inputs Black box Possible outputs

Figure 2.7 The three parts of a function
very great degree. One can think of a function as a sort of 'black box'
which has an input hole and an output hole (Fig. 2.7). At the input
hole there is another box full of possible inputs, and at the output hole
there is a further box designed to take all the 'possible' outputs.
We may feed into the black box any of the members of A. The black
box f then processes our input and produces a single output, which
will always be a member of the set B.
Now, it may be that iftwo different inputsa l ,a 2 are made, the same
output occurs in each case, i.e. f(a l ) = f(a 2 ). If this never happens, we
say f is one-one, or injective, or an injection. Thus, f is one-one if
distinct inputs produce distinct outputs.
Now let's look at the set B of 'possible' outputs. We have enclosed
the word 'possible' in quotation marks for the following reason. The
output box is an integral part of our black box apparatus (it is not
possible to purchase a black box on its own). But it is possible that
some of the space in B is not needed: the black box will never be able
to fill the box B. But if it is possible to fill box B, we say f is onto or
surjective, or a surjection.
Let us now see what these definitions mean in relation to our
original example of the rule determined by the equation

y= X2 +X + 1
This determines a function f: fJt -+ fJt given by f (x) = x 2 + X + 1.
Is f one-one? That is, can we find distinct reals Xl and X 2 such that
[(Xl) = f(x 2 ) (in which case it will not be one-one), or is it the
case that

(in which case it will be one-one). A quick glance at Fig. 2.6 shows us
that
f( - 1) = f(O) = 1
 SETS AND FUNCTIONS 47
Hence f : fJl-+ fJl is not one-one. Is f onto? That is, does every
element of fJl occur as a value of f for some input? Again, the diagram
(Fig. 2.6) provides the answer. The number 0 is never a value of f
(Indeed, no n urn ber less than 0.75 is a value of f) Hence f : fJl-+ fJl is
not onto.
But the same equation y = x 2 + X + 1 also determines a function
g:fJl+-+fJl, where fJl+ ={xEfJllx~O}, the set of all non-negative
reals. The only difference between this function and the previous one
is that our new function has a different 'input box'; we are no longer
allowed to feed negative numbers into our 'black box'. The graph of
this function is illustrated in Fig. 2.8.
The function g : fJl + ---+ fJl so defined is clearly one-one: it is indeed
increasing: if x 1 < x 2 , then g(x 1) < g(x 2 ). But it is still not onto, for 0 is
still not a value, and neither is any real less than 1.
Finally, let h : fJl+ -+ A be the function h(x) = x 2 + X + 1, where now
A = {xEfJllx ~ I}. This function is both one-one and onto.
A function which is one-one and onto is sometimes called a
bijection.
Let us now briefly review our definitions. A function from a
non-empty set A to a set B is a rule which associates with each element
a of A a unique element f(a) of B, called the value of fat a. We write
f : A ---+ B in this case. The set A is the domain of f, the set B the
codomain. When a function is specified, it is not sufficient to give

y
3

Or--------,r--------,~~
2 X

-1

Figure 2.8 Graph of the function y = x 2 + X + 1 for x ~0

48 SETS, FUNCTIONS AND LOGIC
the rule: the domain and codomain must also be given. The function
f : A --+ B is one-one (injective) if distinct elements of A give rise to
distinct values in B. And f is onto (surjective) if every element of B
is a value of f A function which is both one-one and onto is called a
bijection.
Functions are also called mappings, maps or transformations
(though the last word tends to be reserved for special kinds of
functions).
Now let us consider some examples of functions, other than the
familiar example of function given by an equation.
(1) Consider the function f : fJA -+ fJA defined by

f(x) = { x, ~f x ~ 0
- x, If x < 0

This function is not defined by an equation: rather the rule consists of

two separate cases. In words, the rule is: given x as input, the output is
x if x ~ 0 and is - x if x < O. Since for each x there is exactly one
possible f(x) (because no x is at the same time ~ 0 and < 0), this does
define a function. It is the absolute value function. We usually write
Ixl instead of f(x), and call1xl the absolute value of x, or the modulus
(or mod) of x. This function is not one-one, since, for example,
f (- 1) = f (1) = 1. It is not onto, since no negative real is a value.
(If we were to consider instead the function g : fJA --+ fJA + defined by
g(x) = lxi, then g would be onto, but still not one-one).
(2) Consider next the function f : fJA -+.AI defined by

f (x) = {1, ~f x ~s irr~tional

0, If x IS ratIOnal

The function f : f7t -+.AI so defined is neither one-one nor onto.

(3) Let A = {a, b, c, d}, B = {c, d, e}. Define f : A -+ B by

f(a)=c, f(b)=d, f(c)=c, f(d)=e

(In other words, the 'rule' is determined by listing all the values
individually.) The function f so defined is not one-one, but it is onto.
(4) Let A be the set of all countries, and let B be the set of all capital
cities in the world. Define f : A -+ B by letting f(a) be the capital city
of a. The function f is a bijection.
 SETS AND FUNCTIONS 49
(5) Let f : flA -+:?Z be defined by

f(x) = the largest integer n such that n::;; x

We callf(x) the integer part ofx. This function is not one-one, but it is
onto.
(6) Let A be any non-empty set. Define I A : A -+ A by

We call IA the identity function on A. It is clearly bijective.

Exercise 2.6
(1) Let A = {I, 2}, B = {I, 2, 3}. List all the functions from A to B.
(2) List those functions in question (1) which are
(a) one-one (b) onto (c) bijective.
(3) Define f : flA -+ flA by f(x) = t(x + Ixl). Evaluate f(O), f(1), f(2). Is
f one-one? Is f onto? Justify your answers.
(4) Define f : flA -+ flA by

f(x) = {X2 + 1,. if x ~ 0

x-I, If x < 0

Prove that f is one-one. Is f onto?

(5) Define f : JV -+ JV by
f( = {2n, if n is even
n) n, I' fn 'IS 0 dd

Show that f is one-one. Is f onto?

(6) Let A = {I, 3, 5, 7, ... }, the set of odd natural numbers, and B
= {2, 4,6,8, ... }, the set of even natural numbers. Give examples
of functions from A to B which are:
(a) One-one but not onto.
(b) Onto but not one-one.
(c) Neither one-one nor onto.
(d) One-one and onto.

Let f :A -+ B. If X s; A, the range of f on X is the set of all values of

50 SETS, FUNCTIONS AND LOGIC
f for inputs from the set X. In symbols

{f(X)IXEX}

or, alternatively,

{bEBI(3xEX)(f(x) = b)}

The range of f on X is denoted by

f[X]

We refer to the set f [A] simply as the range of f

Exercise 2.7
(1) Let f :A~B. Show that f is onto itT f[A] =B.
(2) Define f :.% ~.% by

_ {2, if n is not prime

f(n)- n,1' fn 'IS pnme
.

Let P be the set of all primes, K the set of all non-primes (in .%).
Identify the setsf[.%], f[P], f[K].
(3) Let f : A ~ B. Show that f is not one-one itT there are elements
x, YEA such that x =1= Y and f[{x, y}] has only one element.
(4) Define f :fIt~fYt by f(x) = x 2 + X + 1. What is f[fIt]? What is
f[fYt+]?
(5) Let f:.% -+.%. Show that there is a set A ~.% such that
h : A -+.% is one-one, where we define

h(n) = f(n) (\fnEA)

Now show that there is a set B s;; .% such that g : A -+ B is a

bijection, where we define

g{n) = h{n} (\fnEA)

We say two functions f, g from a set A to a set B are equal itT for
every aEA, f(a) = g(a). Thus, equality offunctions depends upon the
 SETS AND FUNCTIONS 51

domains being equal, the codomains being equal, and the actions
being equal. We do not require that the 'rules' are the same. For
instance, f : f!lt -+ f!lt and g : f!lt -+ f!lt are equal, where we define

f(x) = maximum (x, - x)

g(x) = Ixl

2.4 Composition of functions. Inverse functions

Suppose f : A -+ Band g : B -> C are given. Then we can define a
function h : A -> C by the following rule: given aEA, use rule f to
calculate b = f(a), and then use rule g to calculate g(b) for this b; the
resulting element of C (being uniquely defined) shall be h(a). In
symbols,
h(a) = g(f(a)) (\faEA)

We denote the function h so defined by g 0 J, and refer to this function

as the composition of g and! Notice that for g 0 f to be defined, the
codomain of f should be equal to the domain of g.

Exercise 2.8
(1) Let f : A -> B, g : B -+ C, h : C -+ D. Prove that

h o(g 0 f) = (h og) 0 f

(associative law)
(2) Define f :f!lt -> f!lt by

f(X)={x 2 , i~x~O
x-I, If x < 0

Define g : f!lt -> f!lt by

X + 1, if x ~ 1
g(x) = { .
2x ,If x < 1

Find formulae for the functions g 0 f and fag. Use this example
to show that g af = fag is not in general true.
52 SETS, FUNCTIONS AND LOGIC
(3) Define f :~~f7l and 9 :f7l~~ by

f(x) = x2
g(x) = { x+ 1, if x>O
-10, if x~O

Find go f and fog. In each case say whether the function is one-
one, onto, both, or neither, and identify the ranges of each of the
functions f, g, go f, fog.
(4) Let A = {{t, 2}, {t, 3}, {2}, {2, 5}, {3, 4, 5}}. Define f: A ~ %
by

f(a) = sum of the elements of a (\1' aEA)

Findf[A]. Now define g: % ~ % by

( ) = {the largest prime ~ n, if n > 1,

9 n 1, if n = 1

Find 9 0 f and identify its range. Is f one-one? Is 9 f one-one?

0

Let f: A ~ B. We say f is invertible if there exists a functIOn

9 :B~A such that for all aEA, bEB,

Theorem 2.2
Let f : A ~ B. Then f is invertible itT it is a bijection, in which case the
function 9 as described above is unique.

Proof
Suppose f is invertible. We prove that f is a bijection. By the
invertibility of f, there is a 9 : B ~ A as above. Let aI' a 2 EA, a l =1= a 2 •
We prove that f(a l ) =1= f(a 2 ), which shows that f is one-one
(since aI' a 2 are arbitrary). Suppose, on the contrary, that

By the property of 9 we have g(b)=a l and g(b)=a 2 • But 9 is a

 SETS AND FUNCTIONS 53
function. Hencea 1 = a 2 , a contradiction. Thus f(a 1 ) -+ f(a 2 ), and f is
shown to be one-one. Let beB now. We show that f(a) = b for some
aeA, which shows that f is onto (since b is arbitrary). Leta = g(b). By
the properties of g,f(a) = b, so we are done. Hence f is a bijection.
Conversely, assume now that f is a bijection. We show that f is
invertible.
Let beB. Since f is onto there is aeA such that f(a) = b. But f is
one-one, so there cannot be another such a. Hence, for each b in B
there is exactly one a in A with f(a) = b. Define g : B ..... A by the rule:
for each beB, g(b) is the unique element a of A for which f(a) = b.
Clearly, g is as required for invertibility of f Since this is the only
possible definition of g, we see also that g is unique. QED.
The unique function g as above is called the inverse of f, and
denoted by f - 1.

Exercise 2.9
(1) Let f : A -+ B be invertible. Show that

(2) Define f : ~ -+ ~ by

f(x) = {X2 + 1, if x ~ 0
x + 1, if x < 0

Show that f is a bijection and find f - 1.

(3) Define f: ~2 ..... [JI2 by f(x, y) = (x + 2y, x - y). Show thatf is a
bijection and find f - 1.
(4) Let f: A ..... Band g: B -+ C be invertible. Show that go f is
invertible and that (g f)- 1 = f- 1 og- 1.
0

(5) Let A be the set of all countries, B the set of all capital cities ofthe
world. Define f : A ..... B by

f(a) = the capital of the country a (VaeA)

Describe the inverse function f- 1.

CHAPTER 3

The real numbers

3.1 The real line

In this book we assume that you already have a reasonable idea of the
concept of a real number. But why do we need to introduce the real
number system in the first place? In real life, we are never able to
measure any quantity (e.g. length or temperature) to more than a few
decimal places, for which the rational numbers suffice. Indeed, the
rational numbers suffice for the measurement of any quantity to
whatever degree of accuracy is required. This fact is illustrated by the
following simple result:

Theorem 3.1
If r, sE:!2, r < s, there is tE:!2 such that r < t < s.

Proof
Let t = ~(r + s). Clearly, r < t < s. But is tEfl? Well, letting r = m/n,
s = p/q, where m, n, p, qE:?Z. We have

t=~(~+E)=mq+np
2 n q 2nq

so as mq + np, 2nqE:?Z, we conclude that tE:!2. QED.

The trouble is, although the rationals are 'dense' in the sense of the
above theorem, there are nevertheless 'holes' in the rational line. For
example, if we let

A = {xEfllx2 < 2}
B = {xE:!2lx2 ~ 2}
54
 THE REAL NUMBERS 55
then every element of A is smaller than every element of B, and

AuB=~

But A has no greatest member and B has no smallest member (as the
reader can easily check for himself), so there is a sort of ,hole' between
A and B. This is the 'hole' wherej2 ought to be, of course. The fact
that ~ contains 'holes' makes it unsuitable for mathematical pur-
poses, even though it suffices for all our measurements. Indeed, a
number system in which the equation

x2 - 2 =0

has no solution is a pretty weak one. So we agree that for

mathematics, we require a number system which does not contain
'holes', and in which we can take square roots, etc. (at least for positive
numbers). But what are the real numbers? Ifwe ask what the rationals
are, we can answer by referring back to the integers, since all rationals
are essentially quotients of integers. And the integers are so basic that
for most purposes this suffices as an answer. But when the same
question is asked of the reals the answer is not so easy. The point is,
although the rationals are an abstract system of entities, and thus
nothing more than figments of our intuition, they correspond to such
basic concepts that they possess a certain concreteness. (We can
calculate a number to 30 decimal places, even 50, and to get all the
rationals we just need to imagine that we could calculate to any finite
number of places, which does not require too great a feat of
imagination.) But the concept of an irrational number is already
much more abstract. The result (proved in Chapter 1) that it is utterly
impossible to calculate the decimal expansion of j2, that its
expansion continues for ever, without recurrence, defies the 'finite'
imagination. We cannot 'construct' such a number, not even in
theory. So in what sense are we justified in regarding, say,j2 as a
number at all? The answer is, only in a strict mathematical sense. One
constructs the real number line by an abstract mathematical con-
struction which, essentially, 'fills in all the holes' in ~. This con-
struction is quite complicated, and was one of the major mathemati-
cal accomplishments ofthe 19th century. It only answers the question
'What is a real number?' in an abstract, mathematical sense. Its value,
really, is that it does tell us that we are not going to run into any
56 SETS, FUNCTIONS AND LOGIC
trouble if we imagine that the 'holes' in !!2 are all filled in. And the
advantage of so doing is that the mathematical possibilities multiply
enormously. (For instance, the calculus cannot be developed over !!2,
but it can over ~.)
For our present purposes, we shall take as a sort of 'definition' of a
real number the points on the real line. (This is, of course, a circular
'definition', and hence no definition at all, but it provides us with a
useful and intuitive starting point. If you object violently, you can try
to imagine starting with the rational line and 'filling in' the 'holes', but
even trying to find a 'hole' is not easy!) The set of reals (i.e. the points
on the real line) is denoted by ~. The elements of ~ possess a natural
ordering ( < ), which corresponds to the 'ordering' of the points on the
real line.
The fact that the real line has no 'holes' is expressed by the so-called
completeness property, described below.

3.2 Upper bounds. Completeness

Let AS; R. Any real x such that

(\faEA) (a ~ x)

is called an upper bound of A. We call x a least upper bound (l.u.b.)if

there is no smaller upper bound: that is if, whenever y < x, y fails to be
an upper bound of A. Clearly then, x is a least upper bound of A if
(\faEA) (a ~ x), and whenever y < x there is an aEA such that a > y. A
set A of real numbers does not have to have any upper bound, of
course. For instance, the set JV S; ~ has no upper bound. But if A
does have an upper bound, it will necessarily have a least one. This is
the completeness property of the real line.

Completeness property
Let A S; ~. If A has an upper bound, then it has a least upper bound
(in ~).

Clearly, if A has a least upper bound, this must be unique. (If x and y
were both least upper bounds, one would have to be smaller than
the other, say x < y, so y would not be a least upper bound.)
The rational line, !!2, does not have this property. For instance, the
 THE REAL NUMBERS 57

set

is bounded above in fl by 2, but it has no least upper bound in fl. To

see this, let xEfl be any upper bound of A. We show that there is a
smaller one (in fl). Let x = p/q, p, qEJIi. Suppose first that x 2 < 2.
Thus 2q2 > p2. Now, as n gets large, the expression n2/2n + 1 increases
without bound, so we can pick nEJIi so large that

Rearranging, this gives

Hence

Let

n + 1p
Y=--
n q

Then, since (n + 1)/n > 1, we have x < y. But Y is rational and we have
just seen that y2 < 2, so YEA. This contradicts the fact that x is an
upper bound for A. It follows that we must have x 2 ~ 2. Since there is
no rational whose square is 2, this means that x 2 > 2. Thus p2 > 2q2,
and we can pick nEJIi so large now that

which becomes, upon rearranging,

i.e. -p2 ( -n- )2 >2

q2 n + 1
58 SETS, FUNCTIONS AND LOGIC
Let

n p
y=--
n + 1q

Since nl(n + 1) < 1, y < x. We complete the proof by showing that y is

an upper bound for A. Let aEA. Thus a2 < 2. Thus

Thus a < y, as required.

On the other hand, the set A (regarded as a subset of !!It now) does
have a least upper bound in !!It, namely J2.
Exercise 3.1
(1) Let A 5; fJf, xEfJf. Show that x is the l.u.b. of A iff(a) and (b) below
are valid:
(a) (VaEA)(a ~ x)
(b) (Ve> O)(3aEA)(a > x - e)
(2) By negating (a) and (b) above, obtain a symbolic definition ofthe
property 'x is not the l.u.b. of A'. (Put your answer in a positive
form.)
(3) Besides the completeness property, the Archimedean property is an
important fundamental property of fJf. This says that if x, YE!!It
and x, Y> 0, there is an nEA' such that nx > y.
Use the Archimedean property to show that if r, sEf)f and r < s,
there is a qE2 such that r < q < s. (Hint: pick nEA', n> 1/(s - r),
and find an mEA' such that r < (min) < s.)

3.3 Absolute values

Recall from Chapter 2 the definition of the absolute value function

Ixl = { x, ~f x ~ 0
-x, If x < 0

We prove some simple results about this function.

 THE REAL NUMBERS 59
Theorem 3.2

(By J x is always meant the positive square root.)

Proof
Clearly, lal 2 = a 2 . Taking square roots, J(laI2) =J(a 2 ). But lal ~ o.
Hence J(laI2) = lal, and the theorem is proved.

Theorem 3.3
labl = lallbl
Proof
There are four possible cases:
(I) a ~ 0, b ~ O. Then labl = ab = lallbl.
(II) a ~ 0, b < O. Then labl = - (ab) = a( - b) = lallbl.
(III) a < 0, b ~ O. Then labl = - (ab) = ( - alb = lallbl.
(IV) a < 0, b < O. Then labl = ab = ( - a)( - b) = lallbl. QED.

Theorem 3.4
Let a > O. Then Ixl ::;; a iff - a ::;; x ::;; a

Proof
Exercise for the reader.

Theorem 3.5 (Triangle inequality)

la + bl ::;; lal + Ibl

Proof
Clearly, by Theorem 3.3,

ab ::;; labl = lallbl

Thus

2ab ::;; 21allbl

60 SETS, FUNCTIONS AND LOGIC
So

i.e., by Theorem 3.2,

i.e.

Hence

i.e., by Theorem 3.2,

la + bl ~ lal + Ibl
QED.
If x, YEYl, the positive number Ix - yl represents the 'distance'
between x and Y on the real line. If x =1= y, then Ix - yl > 0. Conversely,
if Ix - yl > 0, then x =1= y. Hence x = y iff Ix - yl = 0. By the triangle
inequality, if x,y,zE~, we have

Ix - yl ~ Ix - zl + Iz - yl

This inequality is also referred to as 'the triangle inequality'.

3.4 Intervals

Certain types of subset of ~ occur so frequently that it is convenient to

introduce a special notation for them. Let a,bE~, a < b.
The open interval (a,b) is the set

(a,b) = {xE~la < x < b}

The closed interval [a,b] is the set

[a,b] = {xE~la ~ x ~ b}
 THE REAL NUMBERS 61
The point to notice here is that neither a nor b is an element of (a, b),
but both a and b are elements of [a,b]. (This seemingly trivial
distinction turns out to be highly significant in elementary Real
Analysis.) Thus, (a, b) is the stretch ofthe real line beginning 'just past'
a and ending 'just before' b, whilst [a, b] is the stretch beginning at a
and ending at b.
The above notation extends in an obvious manner. We set

[a, b) = {xE9l!la ~x < b}

(a,b] = {xE9l!la < x ~ b}

[a, b) is left-closed and right-open; (a, b] is left-open and right-closed.

We refer to either [a,b) or (a,b] as a half-open (or half-closed) interval.
Finally, we set

( - 00, a) = {xE9l!lx < a}

( - 00, a] = {xE9llx ~ a}
(a, (0) = {xE9l!lx > a}
[a, oo)={xE9l!lx~a}

Notice however that the symbol 00 is never coupled with a square

bracket. This would be misleading, since 00 is not a number, just a
useful symbol. In the above definitions it simply helps us to extend a
notation to cover another case.
Any set of the above forms is called an interval. Thus, an interval is
just an uninterrupted piece of the real line.

Exercise 3.2
(1) What is l.u.b. (a, b)? What isl.u.b. [a, b]? What is max (a, b)? What
is max[a, b]?
(2) Let A = {Ix - Yllx, YE(a, b)}. Prove that A has an upper bound.
What is l.u.b. A?
(3) Prove that the intersection of two intervals is again an interval. Is
the same true for unions?
(4) Taking 9l! as the universal set, express the following in terms of
unions of intervals:
(a) [1, 3]'
62 SETS, FUNCTIONS AND LOGIC
(b) (1, 7]'
(c) (5, 8]'
(d) (3,7)u[6,8]
(e) (-00, 3)'u(6, 00)
(f) A I, where A = ( - 00, 5] u(7, 00)
(g) A', where A = (6, 8)n(7, 9]
(h) (1, 2) n [2, 3)
(i) (1,4]n[4,10]

3.5 Sequences
Suppose we associate with each natural number n a real number an"
The set of all these numbers am arranged according to the index n, is
called a sequence. We denote this sequence by

Thus, the sumbol {an} represents the sequence

For example, the members of % themselves constitute a sequence,

when assigned their usual order

1,2,3, ... , n, ...

This sequence would be denoted by {n} (because an = n for each n).

Or we could order the elements of % in a different manner to
obtain the sequence

2, 1, 4, 3, 6, 5, 8, 7, ...

This is quite a different sequence from the sequence {n}, since the
ordering in which the members of the sequence appear is important.
Or, if we allow repetitions we get a completely new sequence

1, 1,2,2,3,3,4,4,4, 5, 6, 7, 8, 8, ...

(There does not need to be a nice rule involved: it may be impossible

to find a formula to describe an in terms of n.) Again, we can have a
 THE REAL NUMBERS 63

constant sequence

'lr, n, TC, 7r, 1t, . . . , TC, ...

or an alternating (in sign) sequence

1, - 1, 1, - 1, 1, - 1, ...

In short, there is no restriction on what the members of a sequence

{an} may be, except that they be real numbers. What counts is the
order in which the members of the sequence are placed.
Now, some sequences have a rather special property. As we go
along the sequence, the numbers in the sequence get closer and closer
to some fixed number. For example, the members of the sequence

get closer and closer to 0 as n gets larger, whilst the members of the
sequence

{1+ ;n} = ±,
1t, 1 1t, 1 /6' ...

get closer and closer to 1. And the members of the sequence

3,3·1,3·14,3·141,3·1415,3·14159,3·141592,3·1415926, ...

get closer and closer to n (though this example is not as good as the
others, owing to our not giving any general rule for the nth term in the
sequence).
If the members of the sequence {an} get closer and closer to some
fixed number a, we say that the sequence {an} tends to the limit a, and
write

(The arrow means 'approaches without bound'. So, as n gets larger,

without bound, so an gets closer to a without bound.)
So far, this is all very intuitive. Let us see if we can obtain a precise
64 SETS, FUNCTIONS AND LOGIC
definition of what it means to sayan -'a as n -. 00. Well, to say that an
gets closer and closer to a, without bound, is to say that the difference
Ian - al gets closer and closer to 0, without bound. This is the same as
saying that whenever B is a positive real number, the difference Ian - al
is eventually less than B. This leads to the following definition:

iff

(VB> 0)(3nE.K)(Vm ~ n)(a m- al < B)

This looks quite complicated. Let us try to analyse it. Consider the
part

(3nE.K)(Vm ~ n)(lam - al < B)

This says that there is an n such that for all m greater than or equal to
n, the distance from am to a is less than B. In other words, there is an n
such that all terms in the sequence {an} beyond an lie within the
distance B of a. We can express this concisely by saying that the terms
in the sequence {an} are eventually all within the distance B from a.
Thus, the statement

(VB> 0)(3nE.K)(Vm ~ n)(la m- al < B)

says that for every B > 0, the members of the sequence {an} are
eventually all within the distance B from a. This is just the formal way
of saying that an gets closer and closer to a, without bound.
Let us consider a numerical example. Consider the sequence {l/n}.
We 'know' that l/n -.0 as n -. 00. We shall see how the formal
definition works for this sequence. We must prove that

(VB> 0)(3nE.K)(Vm ~ n)(I~ - 01 < B)

This simplifies at once to

(VB> O)(3nE.K)(Vm ~ n)(! < B)

 THE REAL NUMBERS 65

To prove that this is a true assertion, let B > 0 be arbitrary. We must

=
find an n such that m ~ n l/m < B. Pick n large enough so that
n > l/B. (This uses the Archimedean property of ~!) If now m ~ n,
then l/m::::; l/n < B. In other words, (Vm ~ n)(l/m < B), as required.
The point to notice is that our choice of n depended upon the value of
B. The smaller B is, the greater needs to be our n.
Another example is the sequence {n/(n + I)}, i.e.

1 234
2' 3' 4' 5" ..

We prove that n/(n + 1) ~ 1 as n ~ 00. Let B > 0 be given. We must find

as nE JV such that for all m ~ n, Im/(m + 1) - 11 < B. Pick n so large that
n > l/B. Then, for m ~ n,

1 ~_11=1~1=~1
m+1 m+1
<~::::;~<B
m+1 m n

as required.

Exercise 3.3
(1) Formulate both in symbols and in words what it means to say
that an +a as n ----> 00.
(2) Prove that (n/n + 1)2 ----> 1 as n ----> 00.
(3) Prove that 1/n 2 ----> 0 as n ----> 00.
(4) Prove that (1/2t---->0 as n----> 00.
(5) We say a sequence {an} tends to infinity if, as n increases, an
increases without bound. For instance, the sequence {n} tends to
infinity, as does the sequence {2n}. Formulate a precise definition
of this notion, and prove that both of these examples fulfill the
definition.
(6) Let {an} be an increasing sequence (i.e. an < an + 1 for each n).
Suppose thatan---->a as n----> 00. Prove thata = l.u.b.{a 1, a2 , a3 , . •• }.
CHAPTER 4

Complex numbers

4.1 Number systems

In this book we do not propose to make a detailed study of number
systems. However, in order to motivate to some extent the in-
troduction of complex numbers, we consider briefly the development
of the real number system.
The simplest number system of all is the natural number system:

%={1,2,3, ... }

with the usual operations of addition and multiplication. (Usually,

when we speak of a number system, we mean the numbers concerned
together with the operations of addition and multiplication on those
numbers.) Though perfectly adequate as a system for 'counting'
elements of finite sets, the system is mathematically inadequate.
Equations such as

x+3=2

have no solution in the system (though all the constants in the

equation do lie in the system). This particular deficit is overcome by
extending % to a larger system, the integers:

~= {a, ± 1, ± 2, ± 3, ... }
Given the natural number system, the system of integers may be
defined, in a precise mathematical manner, from it: that is, we may
construct the set ~ and define the operations of addition and
multiplication on this set, assuming only the existence of the natural
number system (together with a few very simple set-theoretic
operations). (Moreover, we can prove that these operations have all
66
 COMPLEX NUMBERS 67
the familiar properties: commutativity, associativity, etc.) Though
easy, the details of this procedure are not within our present scope.
Now, in !!L, all equations

x+a=b (a, bE!!L)

have solutions, but !!L is still mathematically deficient. For instance,

the equation
3x =2

has no solution in !!L. We overcome this problem by extending !!L to

the system fl of rational numbers. This involves constructing the set fl
and defining the operations of addition and multiplication on this set
(as well as proving that these operations have all the usual
properties). Again we do not go into the (easy) details.
In fl, all equations

ax =b (a, bEfl)

have solutions (except when a = 0, but then there is no equation !).

Nevertheless, fl is mathematically deficient, since, for example, the
equation

has no solution in fl. To overcome this difficulty we extend fl to the

real numbers, qt. Again, this involves constructing the set qt, defining
the operations of addition and multiplication on qt, and proving that
these operations behave as we want them to. However, this time it is
not so easy. We should not expect it to be. For, whereas we can easily
'imagine' what is meant by a 'negative integer' (given that we know
what a natural number is), and what is meant by a 'rational number',
the concept of an irrational real number defies the (finite) imagination.
(We can evaluate numbers to 10 decimal places, even 50 or 100; and
we can easily conceive of evaluating a number to any finite number of
decimal places; but we can quite literally never evaluate a number to
infinitely many places. In introducing irrational numbers, the notion
of the 'infinite' first plays a significant role. And we can never truly
picture any infinite quantity.) So, whereas we may feel quite happy
with the extensions of v;f to !!L and of!!L to fl, the step from fl to qt is
68 SETS, FUNCTIONS AND LOGIC

quite unnerving. The best 'picture' we have is that of 'filling in the

holes' on the rational line. However, as we showed in Chapter 3,
Section 3.1, in a sense there are no 'holes' in!!2. (More precisely,!!2 has
no finite holes, only infinitely small (?) ones.) So, for the extension
from !!2 to f!Jl we need to rely entirely on our mathematics to keep us
out of danger. And the mathematics required is quite considerable.
Indeed, it was not until the latter part of the 19th century that the
mathematicians Cantor and Dedekind (independently) first managed
to provide a rigorous construction of f!Jl from !!2.
With the real numbers, we have our first system of numbers which
allows us to develop some really meaningful and useful mathematics.
For instance, in f!Jl we can develop the calculus, with its many
applications in physics and engineering. Or we can extend our theory
of geometry by introducing the notion of systems of coordinates.
And so on.
However, strong through the system f!Jl is, it is still mathematically
deficient. For instance, in f!Jl the equation

x2 + 1= 0

has no solution. To overcome this problem, we extend f!Jl to a larger

number system, the complex numbers. We describe the extension
procedure below.

4.2 Complex numbers

Our aim is to construct a system of numbers which extends f!Jl and
allows the solution of, in particular, the above equation.
That is, we need to do three things:
(a) Construct the set of new numbers.
(b) Define the operations of addition and multiplication on this set.
(c) Prove that everything behaves as it should.
There are various ways to do this. We describe the most common way,
but the precise way chosen does not matter. Just 'what' a complex
number will be is not important. It is the behaviour of the entire
system that counts. This point often escapes the beginner. He/she is so
used to using real numbers, that he/she ascribes to them a sort of
concrete 'existence', forgetting that they are nothing more than
figments of the (mathematical) imagination. Thus the (totally mis-
 COMPLEX NUMBERS 69
leading) idea that real numbers are somehow more 'real' than
complex numbers. (The appalling use of the words 'real' and
'imaginary' does not help matters. No number is 'real'; they are all
'imaginary' -in the everyday meaning of these words!) Indeed, the
really big leap comes in the passage from f2 to fJt; the subsequent
passage from fJt to <f,j is no worse than that from:!l: to f2 (and in fact is
mathematically very similar). So whereas it is forgivable to regard
rational numbers as 'concrete objects' ('forgivable', note, not 'cor-
rect'), it is a crime of the highest order to regard all real numbers as
concrete objects. That this crime is so widespread exemplifies the old
saying 'familiarity breeds contempt'.
So, having (we hope) disposed of any feelings that we are about to
do something new/bold/foolish/avant-grade/miraculous/deep, let us
describe briefly the construction of the complex number system.
The system fJt is given. Hence we may construct the Euclidean
plane fJt2. More formally, .0Jl 2 is the Cartesian product fJt x fJt, the set of
all ordered pairs (x,y) where x and yare real numbers, the pair (x,y)
being the formal counterpart to the 'point' in the Euclidean plane
whose coordinates are x and y.
Our first definition is: a complex number is an element of fJt2. So now
we know what a complex number is: it is nothing more nor less than
an ordered pair of real numbers. (Very likely you have by now
forgotten the remarks made just a few paragraphs ago, and have
regressed into regarding real numbers as somehow 'real'. In which
case our last definition will strike you as odd. All we can say is that if
we were to explain what a real number actually IS, you would
probably wish you had decided to study music or art or ancient
languages or whatever. In comparison, our definition of a complex
number is very ordinary.)
Our next task is to define the operations of addition and multipli-
cation of complex numbers.
If (a, b), (c, d) are complex numbers, we define the sum

(a, b) + (c, d)

to be the complex number

(a + c, b + d)
It is easy to prove that addition of complex numbers, so defined, is
70 SETS, FUNCTIONS AND LOGIC
both commutative and associative. Moreover, the complex number
(0,0) acts as an additive identity [i.e. (a, b) + (0,0) = (a, b) for all
complex numbers (a, b)], and the complex number ( - a, - b) is the
additive inverse of (a, b) [i.e. (a, b) + (- a, - b) = (0,0)].
We do not need to define subtraction as such. Writing - (a, b) for
the additive inverse of (a, b) [namely ( - a, - b)], we 'define' sub-
traction by:
(a, b) - (e, d) = (a, b) + [ - (e, d)]

Thus,

(a, b) - (e, d) = (a - e, b - d)

The product of the complex numbers (a, b), (e, d) is defined thus:

(a, b)(e, d) = (ae - bd, ad + be)

The reason for choosing this odd looking definition [rather than, say,
the 'obvious' definition (a, b)(e, d) = (ae, bd)] will become clear later.
But let us remark that we are entirely free to define multiplication
however we wish. However, unless we define it as above, we will not be
defining the system of complex numbers, but rather some other
system. 'So what is so special about our chosen definition?', you ask.
Well, the proof of the pudding lies in the eating: with the definition
given, we obtain precisely the number system we want! The many
applications of complex numbers both within mathematics and
without testify to the wisdom of our definition. (The beginner is often
surprised to hear that complex numbers are really 'useful'. And yet
he/she accepts that irrational real numbers are 'useful', even though
we can never measure any actual quantity to more than a few decimal
places (and certainly not to infinitely many places !). Once more the
reason for the discrepancy lies in the familiarity with the one system
and the strangeness of the other.)
It is a routine matter to verify that multiplication of complex
numbers is commutative and associative, and that the distributive law
holds for multiplication and addition [i.e. z(u + v) = zu + ZV, for
complex numbers z, u, v]. Moreover, the complex number (1, 0) acts as
a multiplicative identity, and (a, b) (0, 0) = (0, 0) for all complex
numbers (a, b). We prove later that division of complex numbers is
always possible (except for division by zero, i.e. (0, 0».
 COMPLEX NUMBERS 71
4.3 The complex plane
Having now defined the complex number system, can we obtain some
sort of intuitive picture ofthe system? For instance, although (as you
now know!) the real number system is a highly abstract and technical
system, we nonetheless have the comforting picture of the real line, a
continuous straight line stretching out to infinity in both directions.
Well, in fact whereas we need a considerable amount of effort in order
to relate this picture to the (complicated) mathematical system that is
the real numbers, our definition of the complex numbers itself
provides a visual interpretation: the two dimensional plane ~2).
Instead of a straight line (for ~) we have a plane, stretching out to
infinity in all directions. When we think of the plane ~2 in this
manner, we refer to it as the complex plane. (Thus we have a real line
and a complex plane.)
One point to notice is that whereas the real numbers have a natural
ordering (they lie on a line !), the same is not true of the complex
numbers. There is no natural notion of 'less than' for complex
numbers.
U(a, b) is a complex number, we refer to the real number a as the real
part of (a, b), and to the real number b as the imaginary part of (a, b). The
use ofthese words is not intended to convey any deep meaning, but is
due to the way complex numbers were developed historically. The

Im

y -- - - - -- - -- -...,z
I
= (x, yJ

I
I
I
I
I
I
I
I
I

o x Re

Figure 4.1 The complex plane

72 SETS, FUNCTIONS AND LOGIC

real part of a complex number z is denoted by Re(z), the imaginary

part by Im(z). Notice that both Re(z) and Im(z), are real numbers.
Thus, in the complex plane, the x-axis is referred to as the real axis, the
y-axis being the imaginary axis (Fig. 4.1).
Having now defined the complex numbers, in what sense is this
system an extension of the reals? According to our definition, no real
number is a complex number (since all complex numbers are ordered
pairs of real numbers). However, as we mentioned earlier, with
number systems it does not matter exactly what a number is, it is the
behaviour of the entire system that counts. Consider now the complex
numbers of the form

(x, 0)

If we add two of these we obtain another such:

(x, 0) + (y, 0) = (x + y, 0)
And multiplication is also simple in this case:

(x, O)(y, 0) = (xy, 0)

Indeed, as we can now see, the operations of complex addition and

complex multiplication on the complex numbers of the form (x, 0)
reduce to the operations of real addition and real multiplication on
the first coordinates. The second coordinate-O-plays no role at all.
Hence, the subsystem of the complex numbers consisting of the
numbers of the form (x, 0) isjust a thinly disguised version of the real
number system. (In formal mathematical jargon, we say that the
above subsystem ofC(5 is isomorphic to the system Bl.) So, in view of our
earlier remark, when we consider complex numbers, we may as well
regard a complex number (x, 0) as the same as the real number x. That
is, there is no point in distinguishing between (x, 0) and x: just write x
instead. In this way we obtain the set-theoretic inclusion

And in the sense of complex number theory, a 'real number' is just a

complex number whose imaginary part is zero. Pictorally, in the
complex plane, the 'real line' is just the real axis ('Re' in Fig. 4.1.)
 COMPLEX NUMBERS 73
Notice that as a result of our above discussion, if x is a 'real number'
and (a, b)EC(}, then the product x(a, b) is the complex number
(xa, xb) (i.e. x(a, b) = (x, O)(a, b) = (xa - Ob,xb - Oa) = (xa, xb)).

4.4. The complex number i

We have already investigated complex numbers of the form (x, 0).
What about those of the form (0, y)? Such a number is said to be a
(pure) imaginary number. (Unfortunately we are stuck with this name,
misleading though it is 1) Any such number can be expressed as a
product of a real number and the particular imaginary number (0, 1),
namely

(0, y) = y(O, 1)

(This is also true for any fixed imaginary number (0, k) in place of
(0, 1), of course, provided k f 0, but it will be seen that the choice of
k = 1 is most natural.) The imaginary number (0, 1) has a remarkable
property. Squaring gives

(0, 1)2 = (0, 1)(0, 1) = (0.0 - 1.1,0.1 + 1.0) = (- 1,0)

I.e.

Thus, (0, 1) is a square root of - 11

Denoting the number (0, 1) by i, we can now obtain a convenient
alternative notation for complex numbers. For if(x, y) is any complex
number, then

(x, y) = (x, 0) + (0, y) = (x, 0) + y(O; 1) = x + yi

But be very careful when using this notation. The symbol + refers
throughout to complex addition. There is no intention that the real
numbers x and y should be added (in the sense of ~) here. And the
symbol i is just a convenient abbreviation for the complex number
(0, 1).
With this notation, complex multipication is easily appreciated.
F or we now see that it is essentially a result of ordinary algebra. Given
74 SETS, FUNCTIONS AND LOGIC
complex numbers a + bi and e + di, we have, by algebra

(a + bi)(e + di) = a(e + di) + bi(e + di)

=ae +adi + bei + bdi 2

But i 2 = - 1. Hence

(a + bi)(e + di) =ae +adi + bei - bd

= (ae - bd) + (ad + be)i

Translation ofthis equality back into the ordered pair notation yields
our original definition

(a, b)(e, d) = (ae - bd, ad + be)

When we deal with complex numbers, we usually adopt the notation

a+bi

Notice that if z = a + bi, then a = Re(z) and b = Im(z). Also,

(a + bi) + (e + di) = (a + e) + (b + d)i

And if z, ware complex numbers, than

z = w iff [Re(z) = Re(w) and Im(z) = Im(w)]

This last fact is extremely useful in calculations with complex

numbers. For example, suppose we wish to find the square roots of
the complex number 3 + 4i. We begin by letting x + yi be a square
root of 3 + 4i. Thus

(x + yi)2 = 3 + 4i

Expanding the left hand side we get

 COMPLEX NUMBERS 75
Noting that i2 = - 1, this becomes

Equating real and imaginary parts we obtain the equations

x2 - i = 3
2xy=4

Eliminating y we get

i.e.

This facto rises to give

(x 2 -4)(x 2 +1)=O

Since x is real, x 2 + 1 +- O. Hence

Thus x = ± 2. So, using the equation

y= 2/x

we obtain the solutions x = 2, y = 1 and x = - 2, y = - 1. Thus the

required square roots are

± (2 + i)
This answer may be checked by direct evaluation:

(2 + i)2 = 4 + 4i + i2 = 4 + 4i - 1 = 3 + 4i
76 SETS, FUNCTIONS AND LOGIC
Exercise 4.1
(1) Evaluate
(a) (2 + 3i) + (6 + 5i)
(b) 3(1 + i) - i(9 - 2i)
(c) (3 + 1)(9 - 6i)
(d) (1 + i)i
(e) i 3
(f) i 6
(g) (1 - i)2

(2) Find the complex square roots of

(a) 1
(b) - 3 + 4i
(c) 1 + (4J3)i
(3) Which complex number is both real and imaginary?
(4) On the complex plane, plot the numbers 1, - 1, i, - i and the
square roots of i (from question (2)(a)).

4.5 Conjugate complex numbers. Division of complex numbers

If z = a + bi is a complex number, the complex conjugate of z is the
z
complex number = a - bi. The relationship between z and is z
illustrated in Fig. 4.2 overleaf.
Our main reason for introducing the complex conjugate lies in the
fact that it enables us to show that division by complex numbers is
possible. For let z = a + bi be any non-zero complex number. Then

which is real. Hence

In other words, the multiplicative inverse of z exists and is z/(a 2 + b2 ).

This enables us to divide by (non-zero) complex numbers. For
example, suppose we wish to divide 1 + i by 3 + 4i. Then we
commence by multiplying both numerator and denominator by
 COMPLEX NUMBERS 77
Im

,,
b -------------.,z=a+bi

,
I
I
I
I
I
I
I
o ,a Re
I

,
I
I

,
I

I
I
-b ____________ .Jz=a-bi

Figure 4.2 Complex conjugates

3 + 4i: thus

1+i 1 + i 3 - 4i (1 + i)(3 - 4i) 3 - 4i + 3i - 4i 2

-- ----
3 + 4i 3 + 4i 3 - 4i (3 + 4i)(3 - 4i) 9 - 12i + 12i - 16i 2
7-i 7-i 7 1.
=--=--=---\
9 + 16 25 25 25

We may check this by multiplying the answer by 3 + 4i:

Exercise 4.2
(1) Evaluate
(a) 1/(1 + i)
78 SETS, FUNCTIONS AND LOGIC
(b) 1/(3 - i)
(c) + i)/(l - i)
(1
(d) 61(5 + 2i)
(e) 1/i
(f) i/(2 + 5i)
(g) (1 + 3i)/(2 - i)2
(2) Prove that a complex number z is real iff z = Z.
(3) Prove that l/z = l/z for any non-zero complex number z.
(4) Prove that zw = zw for any complex numbers z, w.
(5) z
Prove that z + w = + w for any complex numbers z, w.
(6) What is z?
(7) Prove that Re(z) = (z + z)/2 and Im(z) = (z - z)/2i.
(8) Prove that zw + zw is always real (hint: prove that zw + zw =
2 Re(zw)).
(9) Prove that zw - zw is always imaginary.
(10) Define f: ~ --+ ~ by f(z) = z. Is f a bijection? If so, what is f - 1?

4.6 Polar representation of complex numbers

Since complex numbers are essentially just the points in the complex
plane, any coordinate system for r7/ 2 will suffice to determine complex
numbers. Using polar coordinates we are able to obtain a repre-
sentation of complex numbers which is particularly well suited to

1m

z= x+yi

Re

Figure 4.3 Polar representation of complex numbers

 COMPLEX NUMBERS 79
complex multiplication (which hitherto has appeared 'complex' in the
everyday sense of this word!)
In order to specify the complex number z = x + yi (Fig. 4.3) we need
only give the distance r from the point z to the origin and the angle e
made by the line Oz and the real axis. We call (r, e) the polar coordinates
of the point z in the complex plane. Here e is measured in an
anticlockwise direction from the real axis, and is subject to the
constraints
o~ e< 2n
e
(It is usual to express in radians in this context.) The number r will be
a positive real (or zero), but is otherwise unrestricted.
The relationship between the polar coordinates and the usual
coordinates is expressed by the equations

x = Re(z) = rcos e
y = Im(z) = rsin e
Thus
z = x + iy = r(cos e + i sin e)
We usually use cis e to abbreviate the expression cos e+ i sin e.
Thus
z = rcis e

This is the polar representation of z. eis the argument of z, arg(z). r is the

modulus of z, Izl. Notice that by Pythagoras's theorem,

Hence, if z is real, Izi is just the 'usual' modulus or absolute value of z in

the sense of f!It.

Exercise 4.3
(1) Express the following complex numbers in polar form:
(a) 1
(b) - 1
80 SETS, FUNCTIONS AND LOGIC
(c)
(d) -1
(e) 1+i
(f) 3 + 4i
(g) 5 - 12i
(2) Express the following complex numbers in 'rectangular form'
(i.e. as x + yi):
(a) 3 cisn/4
(b) 4cisn/6
(c) cis5n/6
(3) Prove that if ZE~ and XE~, then arg(xz) = arg(z) and
Ixzl = Ixllzl.
(4) Prove that Izl2 = zz.
(5) Prove that Re(z):o.::; IRe(z)1 :0.::; Izi.
(6) Prove that Im(z):o.::; IIm(z)1 :0.::; Izi.
(7) Prove that Izwl = Izllwl.
(8) Give an example to illustrate that Iz + wi =1= Izl + Iwl·
(9) Prove that Izl = Izi.
(10) Prove the triangle law: Iz + wl:o.::; Izl + Iwl (hint: write Iz + wl 2 as
(z + w)(z + w) and use the results of questions (4), (5), (8) of
Exercise 4.2, together with the questions (5) and (9) of this
exercise.

4.7 Multiplication of complex numbers in polar form

Let z, w be complex numbers. In polar form, let z = r cis 8, w = s cis ¢.
Then

zw = (r cos 8 + ir sin O)(s cos ¢ + is sin ¢)

= rs cos 8 cos ¢ + irs cos 8 sin ¢ + irs sin 8 cos ¢ +
i 2 rs sin 8 sin ¢
= rs[(cos 8 cos ¢ - sin 8 sin ¢) + i(sin 8 cos ¢ + cos 8 sin ¢)J
Remembering now our basic trigonometric identities, this becomes

zw = rs[cos (8 + ¢) + isin (8 + ¢)]

= rs cis (8 + ¢)

Hence, when we multiply two complex numbers in polar form we

 COMPLEX NUMBERS 81

multiply the moduli and add the arguments. (It may be that the result
of adding the arguments results in an angle greater than or equal to
2n, and in this case we can simply subtract 2n from the answer; but
this is a minor point.)

Exercise 4.4
(1) What is the locus of the point z in the complex plane which
satisfies the equation Izl = I? (i.e. Describe the set {zE~llzl = I}.)
(2) Let w = cis cP. Let U = {zE~llzl = 1]. Show that the following
defines a function f: U ---> U :f(z) = wz. Is f bijective? Describe in
geometric terms the behaviour of the function!
A particular case of the above multiplication rule occurs when the
two complex numbers involved are identical. We then get the rule

(r cis 8)2 = r2 cis 20

In particular, if r = 1, we have

(cis W = cis 20

This generalises as follows.

Theorem 4.1 (de Moivre's theorem)

For all nE.Af, (cis 8r = cis n8.

Proof
The proof is by induction on n. For n = 1 there is nothing to prove. We
assume the result for n and prove it for n + 1. We have, using the result
for n,

(cis 8)" + 1 = (cis 8)" (cis 8) = (cis nO)( cis 0)

= (cos n8 + i sin n8)(cos 8 + i sin 0)
= cos n8 cos 8 + i sin 8 cos n8 + i sin n8 cos 8
+ i2 sin n8 sin 8
= (cos n8cos 8 - sinn8sin 8) + i(sin 8cos n8
+ cos Osin n8)
= cos(n8 + 8) + isin(8 + n8)
= cos(n + 1)8 + isin(n + 1)0
The theorem is thus proved by induction.
82 SETS, FUNCTIONS AND LOGIC
Let us use de Moivre's theorem to evaluate (1 + i)l 0. In polar form,

. J2( n .. n)
1+ 1 = cos "4 + 1 sm"4

Thus, by de Moivre's theorem,

( n .. n)
=2 5 cos"2+ 1SIn "2
= 25 (0 + il)
= 25 i

We may also use de Moivre's theorem in order to evaluate roots. Let

us, for example, try to find the complex cube roots of 1. Suppose
z = rcis e is a complex cube root of 1. Thus, by de Moivre's
theorem,

Clearly, if two complex numbers are equal, they have the same
modulus.
Hence

Thus, as r is a positive real, r = 1, and z = cis e. We must determine e.

We do this by equating real and imaginary parts. We have:

cos38 + isin38 = 1 + Oi

Hence

cos 38 = 1, sin38 = 0

Now, we shall be interested only in values of 8 between 0 and 2n (i.e.

 COMPLEX NUMBERS 83
o~ 8 < 2n). Hence we need only look at values of 38 between 0 and
6n. In this region, the only solutions to the above equations are

3B = 0, 2n, 4n

Hence

8 = 0 2n 4n
, 3' 3

For 8 = 0 we get the root

cisO = 1

For 8 = 2n/3 we get the root

· 2n 1 i}3
CIS~= --+~-
3 2 2

For 8 = 4n/3 we get the root

· 4n 1 i)3
CIS~= ---~-

3 2 2

(Notice that these last two roots are complex conjugates.)

Another example. Let us find the square roots of 1 + i. Let z be a
square root, and write z as z = r cis 8. By de Moivre's theorem,

(4.1)

Equating moduli,

Hence r = -d2 and z = -d2(cis 8), and equation (4.1) becomes

· 8 =-
cls2 1 + -1.
1
J2 J2
Equating real and imaginary parts, cos 28 = 1/)2, sin 28 = 1/)2.
84 SETS, FUNCTIONS AND LOGIC
Thus, to obtain 0 ~ 0 < 2n, we have the solutions

n 9n
2e=~
4' 4
giVIng

9n
8

Hence the roots are ,v2(cisn/8) and .d2(cis9n/8). In this case let us
leave them in this form. The point to notice is that we divided out by
the modulus before evaluating the argument. This is important, since
sin and cos only take values between - 1 and + 1. (Failure to divide
out the modulus will not cause any problems, of course, providing we
remember to carry it as a coefficient throughout the evaluation.
However, it is perhaps wiser to adopt the procedure above.)

Exercise 4.5
(1) Use de Moivre's theorem to evaluate the following:
(a) (1 - i)5
(b) [8 + sj3)ir
(2) Use de Moivre's theorem to evaluate the cube roots of i and - 1.
(3) Use de Moivre's theorem to evaluate the square roots of 8
+ (8}3)i.
(4) Use de Moivre's theorem to evaluate the complex 6th roots of729.
(5) Without actually calculating the roots in an a + bi form, plot on
the complex plane the square roots of ± 1, ± i, ±(1 ± i)/J2.
(6) Plot on the complex plane the 6th roots of 1.
(7) Obtain a formula (in terms of n) for the nth roots of 1.
(8) Both by direct calculation and by reference to a diagram, prove
that if z, ware the two non-real cube roots of 1, then Z2 = wand
w2 =z.

4.8 Algebraic equations

It is well known that in f1ll, the quadratic equation

ax 2 + bx + c =0
 COMPLEX NUMBERS 85
has a solution iff b2 ;:: 4ac, III which case the roots are given by the
formula

- b ±j(b 2 - 4aC)
X=
2a
(a +- 0)

Consider now a similar equatiOn III Cf/:

az 2 + bz + c = 0

(where we allow a, b, c to be complex also). The algebra which led to

the above formula still works. Hence the roots are given by

- b ±j(b2 - 4ac)
z= ---'-----'--
2a
(a +- 0)

But there is no condition restricting the validity of this formula now.

The equation always has a solution, and the formula always gives the
root. For example, consider the equation

Its roots are given by

-1±j(1-4'1'1)
Z=
2'1
-1 ± j -3
2
-1 ±(j3)i
2

= ---+-1
I j3.
2- 2

(You may check this by substituting back in the original equation.)

Or consider the cubic equation

2z 3 + 3z 2 + 2z + 3 = 0
86 SETS, FUNCTIONS AND LOGIC
This facto rises as

(Z2 + 1)(2z + 3) = 0

Hence the roots are z = i, z = - i, Z = - 3/2.

The point is this. Given a quadratic or cubic equation (or worse), we
can set about finding its roots in the usual manner, but now we are not
prevented from proceeding by virtue of needing to form, say, the
square root of a negative number. (Since J - r = (Jr)i). Moreover,
the coefficients may also be complex.
In fact there is a general result here. Consider any complex
polynomial equation (with complex coefficients)

aoz n + a 1 zn - 1 + ... + an _ 1 Z + an = 0

Then this equation has a (complex) root. This basic result is known as
the Jundnmental theorem oj algebra. It is truly remarkable. For what it
amounts to is a proof of the fact that our search for a number system
which is adequate for mathematics is complete. A fact which
experience would not have led us to expect. For consider once more
our progress. Starting with % we observed that % did not allow us to
solve all equations of the form x + m = n. So we extended % to :!l:.
But in :!l: we could not solve all equations ofthe form mx = n. So we
extended :!l: to !!2. In !!2 we could not solve all equations of the form
x 2 = k(k;:' 0), so we extended!!2 to Yl. One might by now expect that
this procedure will continue indefinitely. But no, if we make one more
step now (essentially introducing just the single new root of the
equation x 2 + 1 = 0), then all equations have solutions. In fact much
more is the case. The study of complex numbers is one of the most
beautiful and elegant branches of mathematics, the full appreciation
of which can only be gained by a detailed investigation of the subject.
This gateway into one of the most fascinating parts of mathematics
forms a suitable place for us to end our account.

Exercise 4.6
(1) Solve the following equations:

(a) 4Z2 +z+9 = 0

(b) Z3 - (5 + i)zZ + (6 + 5i)z - 6i = 0 (Try z = i!)
(c) z2-(5-i)z-5i=0
 COMPLEX NUMBERS 87

(2) Express the following polynomial expressions as a product of

linear factors:
(a) Z2 - 1
(b) Z2 +1
(c) z4 - 1
(d) Z4+ 1

(3) Consider the polynomial equation

where ai' ... , an are real. Prove that if z is a root of this equation,
then so is z.
(4) Consider the equation Z2 - 2z + 5 = O. Given that one root of this
equation is z = 1 + 2i, what is the other root?
(5) Use de Moivre's theorem to prove that the equation

has a complex root for any complex values of a, b (a 1= 0).

List of symbols

Symbol Page Symbol Page

A 3 ,gil (x) 36
& 3 u 36
v 4 n 38

-
4 A' 40
=> 6 f:A~B 45
7 f(a) 45
+ 10
10
Ixl
IA
48
49
=1=
T 12 f[X] 50
F 12 fog 51
3 15 f- 1 53
(3xe %), etc. 15 l.u.b. 56
V 16 Jx 59
(V xe %), etc. 16 (a, b) 60
n [a, b] 60
La
i= 1
i 28 [a, b), (a, b] 61
e 32 {an} 62
% 32 an~a 63
~ 32 (x, y) 69
32 Re(z) 72
fl
Im(z) 72
at 32
CC 32 1 73
{ ... } 33 x +iy 73
{xIA(x)} 33 Z 76
{xeXIA(x)} 33 (r, (J) 79
35 cis (J 79
0 arg(z) 79
S;; 36
c 36 Izl 79
Index

Absolute value, 48 If, 10

All, 16 ItT, 11
And, 3 Imaginary axis, 72
Archimedean property, 58 Imaginary number, 73
Argument, 79 Imaginary part, 71
Axiom, 30 Implies, 6
Induction, 25
Bijection, 47 Injection, 46
Integers, 66
Cartesian product, 69 Intersection, 38
Closed interval, 60 Interval, 60
Codomain, 47 Inverse function, 53
Complement, 40 Invertible function, 52
Completeness property, 56 Isomorphic, 72
Complex number, 69
Complex plane, 71 Least upper bound, 56
Composition function, 51 Limit, 63
Conjugate, 76
Map, mapping, 48
Conjunction, 5
Member, 32
Connective, 12
Modulus, 48, 79
Contradiction, 21
de Moivre's theorem, 81
de Morgan laws, 41
Disjoint, 39
Disjunction, 5 Natural number, 66
Domain, 47 Necessary, 11
Negation, 5
Element, 32 Not, 4
Empty set, 35 Null set, 35
Equivalent, 7 Number system, 66
Euclidean plane, 69
Exists, 15 One-one, 46
Onto, 46
Function, 44,47 Open interval, 60
Fundamental theorem of Or, 4
algebra, 86
Pair, 69
Identity function, 49 Polar coordinates, 79
89
90 INDEX
Polar representation, 79 Set, 32
Positive statement, 18 Statement, 1
Postulate, 30 Subset, 35
Power set, 36 Sufficient, 11
Proper subset, 36 Surjection, 46
Proof, 20
Transformation, 48
Quantifier, 17 Triangle inequality, 59, 60
Truth, 29
Range, 49 Truth table, 12
Rational number, 67
Real axis, 72 Union, 36
Real line, 71 Universal set, 37
Real number, 56, 67 Upper bound, 56
Real part, 71
Value, 47
Sequence, 62 Venn diagram, 38