Visit https://ebooknice.

com to download the full version and

explore more ebooks

(Ebook) The Foundations of Analysis: A

Straightforward Introduction. Book 1 Logic, Sets and
Numbers by K.G. Binmore ISBN 9780521233224,
9780521299152, 0521233224, 0521299152
_____ Click the link below to download _____
https://ebooknice.com/product/the-foundations-of-
analysis-a-straightforward-introduction-book-1-logic-
sets-and-numbers-2338400

Explore and download more ebooks at ebooknice.com

Here are some recommended products that might interest you.
You can download now and explore!

(Ebook) The Foundations of Analysis: A Straightforward Introduction.

Book 1 Logic, Sets and Numbers by K.G. Binmore ISBN 9780521233224,
9780521299152, 0521233224, 0521299152

https://ebooknice.com/product/the-foundations-of-analysis-a-
straightforward-introduction-book-1-logic-sets-and-numbers-2338400

ebooknice.com

(Ebook) Biota Grow 2C gather 2C cook by Loucas, Jason; Viles, James

ISBN 9781459699816, 9781743365571, 9781925268492, 1459699815,
1743365578, 1925268497

https://ebooknice.com/product/biota-grow-2c-gather-2c-cook-6661374

ebooknice.com

(Ebook) Foundations of Analysis: A Straightforward Introduction: Book

2, Topological Ideas by K.G. Binmore ISBN 9780521299305, 0521299306

https://ebooknice.com/product/foundations-of-analysis-a-
straightforward-introduction-book-2-topological-ideas-1854094

ebooknice.com

(Ebook) Matematik 5000+ Kurs 2c Lärobok by Lena Alfredsson, Hans

Heikne, Sanna Bodemyr ISBN 9789127456600, 9127456609

https://ebooknice.com/product/matematik-5000-kurs-2c-larobok-23848312

ebooknice.com
(Ebook) SAT II Success MATH 1C and 2C 2002 (Peterson's SAT II Success)
by Peterson's ISBN 9780768906677, 0768906679

https://ebooknice.com/product/sat-ii-success-
math-1c-and-2c-2002-peterson-s-sat-ii-success-1722018

ebooknice.com

(Ebook) Master SAT II Math 1c and 2c 4th ed (Arco Master the SAT
Subject Test: Math Levels 1 & 2) by Arco ISBN 9780768923049,
0768923042

https://ebooknice.com/product/master-sat-ii-math-1c-and-2c-4th-ed-
arco-master-the-sat-subject-test-math-levels-1-2-2326094

ebooknice.com

(Ebook) Cambridge IGCSE and O Level History Workbook 2C - Depth Study:

the United States, 1919-41 2nd Edition by Benjamin Harrison ISBN
9781398375147, 9781398375048, 1398375144, 1398375047

https://ebooknice.com/product/cambridge-igcse-and-o-level-history-
workbook-2c-depth-study-the-united-states-1919-41-2nd-edition-53538044

ebooknice.com

(Ebook) MATHEMATICAL ANALYSIS: A STRAIGHTFORWARD APPROACH, SECOND

EDITION by K.G. BINMORE ISBN 9780521246804, 9780521288828, 0521288827,
0521246806

https://ebooknice.com/product/mathematical-analysis-a-straightforward-
approach-second-edition-37702432

ebooknice.com

(Ebook) Mathematical Analysis: A Straightforward Approach: Second

Edition by K.G. Binmore ISBN 9781107526235, 9780521288828,
9780521246804, 0521246806, 0521288827, 110752623X

https://ebooknice.com/product/mathematical-analysis-a-straightforward-
approach-second-edition-11796904

ebooknice.com
THE FOUNDATIONS OF ANALYSIS:
A STRAIGHTFORWARD INTRODUCTION

BooK 1
LOGIC, SETS AND NUMBERS
THE FOUNDATIONS OF
ANALYSIS:
A STRAIGHTFORWARD
INTRODUCTION
BOOK 1
LOGIC, SETS AND NUMBERS

K. G. BINMORE
Professor of Mathematics
London School of Economics and Political Science

CAMBRIDGE UNIVERSITY PRESS

Cambridge
London New York New Rochelle
Melbourne Sydney
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Siio Paulo, Delhi

Cambridge University Press

The Edinburgh Building, Cambridge CB2 8RU, UK

Published in the United States of America by Cambridge University Press, New York

www.cambridge.org
Information on this title: www.cambridge.org/9780521233224

© Cambridge University Press 1980

This publication is in copyright. Subject to statutory exception

and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.

First published 1980

Re-issued in this digitally printed version 2008

A catalogue record for this publication is available from the British Library

ISBN 978-0-521-23322-4 hardback

ISBN 978-0-521-29915-2 paperback
 CONTENTS

Introduction pageix

1 Proofs 1
1.1 What is a proof? 1
1.5 Mathematical proof 3
1.7 Obvious 5
1.8 The interpretation of a mathematical theory 5

2 Logic (I) 7
2.1 Statements 7
2.4 Equivalence 7
2.6 Not 8
2.7 And, or 8
2.10 Implies 9
2.12 If and only if 11
2.13 Proof schema 12

3 Logic (11) 14
3.1 Predicates and sets 14
3.4 Quantifiers 16
3.6 Manipulations with quantifiers 17
3.10 More on contradictories 18
3.13 Examples and counter-examples 19

4 Set operations 21
4.1 Subsets 21
4.4 Complements 22
4.7 Unions and intersections 23
4.13t Zermelo~Fraenkel set theory 25

5 Relations 28
5.1 Ordered pairs 28
tThis material is more advanced than the main body of the text and is perhaps best
omitted at a first reading.
V
vi Contents

5.2 Cartesian products 28

5.3 Relations 29
5.5 Equivalence relations 30
5.8 Orderings 31

6 Functions 33
6.1 Formal definition 33
6.2 Terminology 35
6.5 Composition 39
6.6t Binary operations and groups 40
6.8t Axiom of choice 41

7 Real numbers (I) 44

7.1 Introduction 44
7.2 Real numbers and length 44
7.3 Axioms of arithmetic 46
7.6 Some theorems in arithmetic 49
7.10 Axioms of order 50
7.13 Intervals 51

8 Principle of induction 54
8.1 Ordered fields 54
8.2 The natural numbers 54
8.4 Principle of induction 56
8.7 Inductive definitions 56
8.10 Properties of N 59
8.13 Integers 60
8.14 Rational numbers 60

9 Real numbers (11) 63

9.1 Introduction 63
9.2 The method of exhaustion 63
9.3 Bounds 66
9.4 Continuum axiom 66
9.7 Supremum and infimum 67
9.llt Dedekind sections 70
9.13t Powers 71
9.16 Infinity 73
9.19 Denseness of the rationals 74
9.21t Uniqueness of the real numbers 75

lOt Construction of the number systems 78

10.1 t Models 78
10.2t Basic assumptions 79
 Contents vii

10.3t Natural numbers 79

10.4t Peano postulates 80
10.6t Arithmetic and order 80
10.10t Measuring lengths 83
10.11 t Positive rational numbers 84
10.13t Positive real numbers 86
10.16t Negative numbers and displacements 88
10.17t Real numbers 89
10.19t Linear and quadratic equations 91
10.20t Complex numbers 92
10.22t Cubic equations 94
10.23t Polynomials 96

llt Number theory 98

1l.lt Introduction 98
11.2t Integers 100
11.3t Division algorithm 100
11.5t Factors 101
11.8t Euclid's algorithm 101
11.9t Primes 101
11.12t Prime factorisation theorem 102
11.13t Rational numbers 102
11.16t Ruler and compass constructions 104
11.20t Radicals 107
11.21 t Transcendental numbers 108

12 Cardinality 109
12.1 Counting 109
12.2 Cardinality 110
12.4 Countable sets 112
12.14 Uncountable sets 118
12.17t Decimal expansions 119
12.20t Transcendental numbers 121
12.23t Counting the uncountable 122
12.24t Ordinal numbers 124
12.25t Cardinals 126
12.26t Continuum hypothesis 127

Notation 128
Index 129
 INTRODUCTION

This book contains an informal but systematic account of the logical and
algebraic foundations of mathematical analysis written at a fairly elemen-
tary level. The book is entirely self-contained but will be most useful to
students who have already taken, or are in the process of taking, an
introductory course in basic mathematical analysis. Such a course nec-
essarily concentrates on the notion of convergence and the rudiments of the
differential and integral calculus. Little time is therefore left for con-
sideration of the foundations of the subject. But the foundational issues are
too important to be neglected or to be left entirely in the hands of the
algebraists (whose views on what is important do not always coincide with
those of an analyst). In particular, a good grasp of the material treated in
this book is essential as a basis for more advanced work in analysis. The
fact remains, however, that a quart will not fit into a pint bottle and only so
many topics can be covered in a given number of lectures. In my own
lecture course I deal with this problem to some extent by encouraging
students to read the more elementary material covered in this book for
themselves, monitoring their progress through problem classes. This seems
to work quite well and it is for this reason that substantial sections of the
text have been written with a view to facilitating 'self-study', even though
this leads to a certain amount of repetition and of discussion of topics which
some readers will find very elementary. Readers are invited to skip rather
briskly through these sections if at all possible.
This is the first of two books with the common title
Foundations of Analysis: A Straightforward Introduction.
The current book, subtitled
Logic, Sets and Numbers,
was conceived as an introduction to the second book, subtitled
Topological Ideas
and as a companion to the author's previous book
Mathematical Analysis: A Straightforward Approach.
Although Logic, Sets and Numbers may profitably be read independently of
these other books, I hope that some teachers will wish to use the three books
together as a basis for a sequence oflectures to be given in the first two years of a
mathematics degree.

ix
x Introduction

Certain sections of the book have been marked with a t and printed in
smaller type. This indicates material which, although relevant and interest-
ing, I regard as unsuitable for inclusion in a first year analysis course,
usually because it is too advanced, or else because it is better taught as part
of an algebra course. This fact is reflected in the style of exposition adopted
in these sections, much more being left to the reader than in the body of the
text. Occasionally, on such topics as Zermelo-Fraenkel set theory or
transfinite arithmetic, only a brief indication of the general ideas is attem-
pted. Those reading the book independently of a taught course would be
wise to leave those sections marked with a t for a second reading.
A substantial number of exercises have been provided and these should
be regarded as an integral part of the text. The exercises are not intended as
intelligence tests. By and large they require little in the way of ingenuity.
and, in any case, a large number of hints are given. The purpose of the
exercises is to give the reader an opportunity to test his or her under-
standing of the text. Mathematical concepts are sometimes considerably
more subtle than they seem at first sight and it is often not until one has
failed to solve some straightforward exercises based on a particular concept
that one begins to realise that this is the case.
Finally, I would like to thank Mimi Bell for typing the manuscript for me
so carefully and patiently.

June 1980 K. G. BINMORE

1 PROOFS

1.1 What is a proof?

Everyone knows that theorems require proofs. What is not so
widely understood is the nature of the difference between a mathematical
proof and the kind of argument considered adequate in everyday life. This
difference, however, is an important one. There would be no point, for
example, in trying to construct a mathematical theory using the sort of
arguments employed by politicians when seeking votes.
The idea of a formal mathematical proof is explained in §1.5. But it is
instructive to look first at some plausible types of argument which we shall
not accept as proofs.

1.2 Example We are asked to decide whether or not the expression

n 3 - 4n 2 + Sn- 1
is positive for n = 1, 2, 3, .... One approach would be to construct a table of
the expression for as many values of n as patience allows.

n n 3 - 4n 2 + Sn- 1
1 1
2 1
3 5
4 19
5 49
6 101

From the table it seems as though n3 - 4n 2 + Sn- 1 simply keeps on

getting larger and larger. In particular, it seems reasonable to guess that
n3 -4n 2 +5n-1 is always positive when n=1, 2, 3, .... But few people
would maintain that the argument given here is a proof of this assertion.

1.3 Example In this example the situation is not quite so clear. We

2 Proofs

are asked to decide whether or not the expression

x 2 -3x+2
is negative for all values of x satisfying 1 < x < 2. Since x 2 - 3x + 2 =
(x-1)(x-2), it is easy to draw a graph of the parabola y=x 2 -3x+2.

From the diagram it seems quite 'obvious' that y = x 2 - 3x + 2 is negative

when 1 <x<2 and positive or zero otherwise. But let us examine this
question more closely.
How do we know that the graph we have drawn really does represent the
behaviour of the equation y = x 2 - 3x + 2? School children learn to draw
graphs by plotting lots of points and then joining them up. But this
amounts to guessing that the graph behaves as we think it should in the
gaps between the plotted points. One might counter this criticism by
observing that we know from our experience that the use of the graph
always leads to correct answers. This would be a clinching argument in the
field of physics. But, in mathematics, we are not supposed to accept
arguments which are based on our experience of the world.
One might, of course, use a mathematical argument to deduce the
properties of the graph, but then the graph would be unnecessary anyway.
We are forced (reluctantly) to the conclusion that an appeal to the graph
of y = x 2 - 3x + 2 cannot be regarded as a proof that x 2 - 3x + 2 is negative
for 1 <x<2.

1.4 Example In the diagram below, the point 0 has been chosen as
the point of intersection of the bisector of the angle A and the perpendicular
bisector of the side BC. The dotted lines are then constructed as shown.
With the help of this diagram we shall show by the methods of elemen-
tary geometry that AB= AC - i.e. all triangles are isosceles.
The triangles AEO and AFO are congruent and hence
AE=AF (1)
OE=OF. (2)
 Proofs 3

Also the triangles OBD and OCD are congruent. Thus

OB=OC. (3)

From (2), (3) and Pythagoras' theorem it follows that

EB=FC. (4)
Finally, from (1) and (4) we obtain that
AB=AC.
The explanation of this well-known fallacy is that the point 0 should lie
outside the triangle ABC. In other words, the diagram does not represent
the way things 'really are', and we have been led into error by depending on
it. The objection that the diagram was not 'properly drawn' carries no
weight since it is clearly not acceptable that a mathematical proof should
depend on accurate measurement with ruler and compasses. This means, in
particular, that the classical arguments of Euclidean geometry are not
acceptable as proofs in modern mathematics because of their dependence
on diagrams.

1.5 Mathematical proof

So far we have seen a number of arguments which are not proofs.
What then is a proof?
Ideally, the description of a mathematical theory should begin with a list
of symbols. This should be a finite list and contain all of the symbols which
will be used in the theory. For even the simplest theory quite a few symbols
will be needed. One will need symbols for variables - e.g. x, y and z. One
will need symbols for the logical connectives (and, or, implies, etc.). The
highly useful symbols ) and ( should not be forgotten and for a minimum of
mathematical content one should perhaps include the symbols + and =.
Having listed the symbols of the theory (and those mentioned above are
just some of the symbols which might appear in the list), it is then necessary
4 Proofs

to specify how these symbols may be put together to make up formulae and
then how such formulae may be put together to make up sentences.
Next, it is necessary to specify which of these sentences are to be called
axioms.
Finally, we must specify rules of deduction which will tell us under what
circumstances a sentence may be deduced from other sentences.
A mathematical proof of a theorem S is then defined to be a list of
sentences, the last of which is S. Each sentence in the list must be either an
axiom or else a deduction from sentences appearing earlier in the list.
What is more, we demand that all of the processes described above be
specified so clearly and unambiguously that even that arch-idiot of in-
tellectuals, the computer, could be programmed to check that a given list of
sentences is a proof.
Of course, the ideas set out above only represent an ideal. It is one thing
to set a computer to checking a list of several million sentences and quite
another to prepare such a list for oneself. Apart from any other considera-
tion, it would be extremely boring.

1.6 Example The list of sentences given below shows what a formal
proof looks like. It is a proof taken from S. C. Kleene's Introduction to
Metamathematics (North-Holland, 1967) of the proposition 'a=a'. This does
not happen to be one of his axioms and therefore needs to be proved as a
theorem.
(1) a=b =(a=c =h=c)
(2) 0=0 =>(0=0 =>0=0)
(3) (a=b =(a=c =>h=c)} => {[0=0 =(0=0 =0=0)] =>
[a=b =>(a=c =h=c)]}
(4) [0=0 =>(0=0 =0=0)] => [a=b =>(a=c =h=c)]
(5) [0=0 =>(0=0 =0=0)] => l;ic[a=b =>(a=c =h=c)]
(6) [0 = 0 =>(0 = 0 =>0 = 0)] => \;7' b\;7' c[a = b =(a =c =>h =c)]
(7) [0 = 0 =>(0 = 0 =>0 = 0)] => \;7' a\;7' b\;7' c[a = b =(a =c =>b =c)]
(8) \;7' aVbVc[a=b =>(a=c =>h=c)]
(9) \;7' a\;ibl;ic[a=b =>(a=c =h=c)] => VbVc[a+O=b =(a +O=c =>b =c)]
(10) VbVc[a+O=b=(a+O=c=b=c)]
(11) \;7' b\;7' c[a + 0= b =(a+ O=c =>h =c)]=> \;7' c[a + 0 =a =(a+ 0 =c =>a =c)]
(12) Vc[a+O=a=(a+D=c=a=c)]
(13) \;7' c[a +O=a =>(a+O =c =a =c)]=> [a +O=a =(a +O=a =>a =a)]
(14) a+O=a=(a+O=a=a=a)
(15) a+ O=a
(16) a+O=a=a=a
(17) a=a.
 Proofs 5

The above example is given only to illustrate that the formal proofs of
even the most trivial propositions are likely to be long and tedious. What is
more, although a computer may find formal proofs entirely satisfactory, the
human mind needs to have some explanation of the 'idea' behind the proof
before it can readily assimilate the details of a formal argument.
What mathematicians do in practice therefore is to write out 'informal
proofs' which can 'in principle' be reduced to lists of sentences suitable for
computer ingestion. This may not be entirely satisfactory, but neither is the
dreadfully boring alternative. In this book our approach will be even less
satisfactory from the point of view of those seeking 'absolute certainty',
since we shall not even describe in detail the manner in which mathematical
assertions can be coded as formal lists of symbols. We shall, however, make
a serious effort to remain true to the spirit of a mathematical proof, if not to
the letter.

1.7 Obvious
The word 'obvious' is much abused. We shall follow the famous
English mathematician G. H. Hardy in interpreting the sentence 'P is
obvious' as meaning 'It is easy to think of a proof of P'. This usage accords
with what was said in the section above.
A much more common usage is to interpret 'P is obvious' as meaning 'I
cannot think of a proof of P but I am sure it must be true'. This usage
should be avoided.

1.8 The interpretation of a mathematical theory

Observe that in our account of a formal mathematical theory the
content has been entirely divorced from 'reality'. This is so that we can be
sure, in so far as it is possible to be sure of anything, that the theorems are
correct.
But mathematical theories are not made up at random. Often they arise
as an attempt to abstract the essential features of a·'real world' situation.
One sets up a system of axioms each of which corresponds to a well-
established 'real world' fact. The theorems which arise may then be in-
terpreted as predictions about what happens in the 'real world'.
But this viewpoint can be reversed. In many cases it turns out to be very
useful when seeking a proof of a theorem to think about the real world
situation of which the mathematical theory is an abstraction. This can often
suggest an approach which might not otherwise come to mind. It is
sometimes useful, for example, to examine theorems in complex analysis in
terms of their electrostatic interpretation. In optimisation theory, insight
can sometimes be obtained by viewing the theorems in terms of their game-
theoretic or economic interpretation.
6 Proofs

For our purposes, however, it is the interpretation in terms of geometry

that we shall find most useful. One interprets the real numbers as points
along an ideal ruler with which we measure distances in Euclidean geo-
metry. This interpretation allows us to draw pictures illustrating prop-
ositions in analysis. These pictures then often suggest how the theorem in
question may be proved. But it must be emphasised again that these
pictures cannot serve as a substitute for a proof, since our theorems should
be true regardless of whether our geometric interpretation is a good one or
a bad one.
2 LOGIC (I)

2.1 Statements
The purpose of logic is to label sentences either with the symbol T
(for true) or with the symbol F (for false). A sentence which can be labelled
in one of these two ways will· be called a statement.

2.2 Example The following are both statements.

(i) Trafalgar Square is in London.
(ii) 2+2=5.
The first is true and the second is false.

2.3 Exercise
Which of the following sentences are statements?

(i) More than 10 000 000 people live in New York City.
(ii) Is Paris bigger than Rome?
(iii) Go jump in a lake!
(iv) The moon is made of green cheese.

2.4 Equivalence
From the point of view of logic, the only thing which really
matters about a statement is its truth value (i.e. T or F). Thus two
statements P and Q are logically equivalent and we write
P~Q

if they have the same truth value. If P and Q are both statements, then so is
P~Q and its truth value may be determined with the aid of the following truth
table.

7
8 Logic (I)

p Q P"""'Q
T T T
T F F
F T F
F F T

In this table the right-hand column contains the truth value of 'P"""'Q' for
all possible combinations of the truth values of the statements P and Q.

2.5 Example Let P denote the statement 'Katmandu is larger than

Timbuktu' and Q denote the statement Timbuktu is smaller than
Katmandu'. Then P and Q are logically equivalent even though it would be
quite difficult in practice to determine what the truth values of P and Q are.

2.6 Not
If Pis a statement, the truth value of the statement (not P) may be
determined from the following truth table.

P not P
T F
F T

2.7 And, or
If P and Q are statements, the statements 'P and Q' and 'P or Q'
are defined by the following truth tables.

p Q P and Q p Q P or Q

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

The English language is somewhat ambiguous in its use of the word 'or'.
Sometimes it is used in the sense of 'eitherfor' and sometimes in the sense of
'andjor'. In mathematics it is always used in the second of these two senses.

2.8 Example Let P be the statement The Louvre is in Paris' and Q

the statement 'The Kremlin is in New York City'. Then 'P and Q' is false
 Logic (!) 9

but 'P and (not Q)' is true. On the other hand, 'P or Q' and 'P or (not Q)'
are both true.

2.9 Exercise

(1) If P is a statement, (not P) is its contradictory. Show by means of truth

tables that 'P or (not P)' is a tautology (i.e. that it is true regardless of
the truth or falsehood of P). Similarly, show that 'P and (not P)' is a
contradiction (i.e. that it is false regardless of the truth or falsehood of
P).
(2) The following pairs of siatements are equivalent regardless of the truth
or falsehood of the statements P, Q and R. Show this by means of truth
tables in the case of the odd numbered pairs.
(i) P, not (not P)
(ii) P or (Q or R), (P or Q) or R
(iii) P and (Q and R), (P and Q) and R
(iv) P and (Q or R), (P and Q) or (P and R)
(v) P or (Q and R), (P or Q) and (P or R)
(vi) not (P and Q), (not P) or (not Q)
(vii) not (P or Q), (not P) and (not Q).
[Hint: For example, the column headings for the truth table m (iii)
should read

There should be eight rows in the table to account for all the possible
truth value combinations of P, Q and R.]
(3) From 2(ii) above it follows that it does not matter how brackets are
inserted in the expressions 'P or (Q or R)' and '(P or Q) or R' and so we
might just as well write 'P or Q or R'. Equally we may write 'P and Q
and R' instead of the statements of 2(iii).
Show by truth tables that the statements '(P and Q) or R' and 'P and
(Q or R)' need not be equivalent.
(4) Deduce from 2(iv) that the statements 'P and (Q 1 or Q 2 or Q 3 )', '(P and
Qd or (P and Q2 ) or (P and Q3 )' are equivalent. Write down similar
results which arise from 2(v), 2(vi) and 2(vii). What happens with four or
more Qs?

2.10 Implies
Suppose that P and Q are two statements. Then the statement
'P implies Q' (or 'P =Q') is defined by the following truth table.
10 Logic(/)

p Q P implies Q

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

In simple terms the truth of' P implies Q' means that, from the truth of P,
we can deduce the truth of Q. In English this is usually expressed by saying
'If P, then Q'
or sometimes
'P is a sufficient condition for Q'.
It strikes some people as odd that 'P implies Q' should be defined as true
in the case when P is false. This is so that a proposition like 'x > 2 implies
x > 1' may be asserted to be true for all values of x.
Consider next the following truth table.

p Q P implies Q not Q not P (not Q) implies (not P)

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

Observe that the entries in the third and sixth columns are identical. This
means that the statements 'P implies Q' and ~(not Q) implies (not P)' are
either both true or both false- i.e. they are logically equivalent. Wherever we
see 'P implies Q' we might therefore just as well write '(not Q) implies (not
P)' since this is an equivalent statement.
The statement '(not Q) implies (not P)' is called the contrapositive of 'P
implies Q'. In ordinary English it is usually rendered in the form
'P only if Q'
or sometimes
'Q is a necessary condition for P'.
These last two expressions are therefore two more paraphrases for the
simple statement 'P implies Q'.

2.11 Exercise
(1) Given that the statements 'P' and 'P=Q' are both true, deduce that Q is
true. [Hint: Delete from the truth table for P=Q those rows which do
 Logic (J) 11

not apply.] If, instead, you are given that the statements 'Q' and 'P=Q'
are true, show that no conclusion may be drawn about the truth
value of P (unless further information is available).
[Note: The first rule of deduction described above is called 'Modus
Ponens'. To deduce P from 'Q' and 'P=Q' has been called 'Modus
Morons'.]
(2) Given that P=Q is true but Q false, show that P is false.
(3) The great philosopher Descartes based his system of philosophy on the
principle 'cogito ergo sum' (I think, therefore I am). Dr Strabismus
(whom God preserve) of Utrecht has founded a rival system based on
the principle 'Non cogito ergo non sum' (I do not think, therefore I am~
not).
Express both these principles in the form 'P=Q' and hence clear Dr
Strabismus (and the Daily Express, where his thoughts were once
published) from the insinuation that his principle may be deduced from
that of Descartes.
(4) Rain on Tuesday is a necessary condition for rain on Sunday. If it rains
on Tuesday then it rains on Wednesday. But it rains on Wednesday
only if it rains on Friday. Moreover no rain Monday implies no rain on
Friday. Finally, rain on Monday is a sufficient condition for rain on
Saturday.
Express each of these statements in the form 'P=Q'. Given that it
rains on Sunday, what can be said about Saturday's weather?
(5) Show that the statement 'P implies Q' is equivalent to '(not P) or Q'.
Deduce that 'P implies Q' is also equivalent to 'not {P and (not Q)}'.
(6) What conclusion (if any) may be drawn from the truth of '(not P)=P'?

2.12 If and only if

Consider the truth table below.

p Q P=Q Q=P (P=Q) and (Q=P) P=Q

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

Observe that the entries in the fifth and sixth columns are identical. Thus to
say that 'P is logically equivalent to Q' is the same thing as saying
'(P implies Q) and (Q implies P)'.
In ordinary English this statement is usually expressed in the form
'P if and only if Q'
12 Logic (I)

- i.e. '(P only if Q) and (if Q then P)'. Alternatively it may be paraphrased as
'P is a necessary and sufficient condition for Q'.

2.13 Proof schema

Most theorems take one of the two forms 'If P, then Q' or 'P if
and only if Q'. The second of these really consists of two theorems in one
and is usually proved in two parts. First it is shown that 'P implies Q' and
then that 'Q implies P'.
To show that 'P implies Q' we normally use one of the following three
methods.
( l) The most straightforward method is to assume that P is true and try
and deduce the truth of Q (there is no need to worry about what
happens when P is false since then 'P implies Q' is automatically true).
(2) A second method is to write down the contrapositive '(not Q) implies
(not P)' and prove this instead. We then assume the truth of (not Q) and
try and deduce the truth of (not P).
(3) Finally, we may argue by contradiction (reductio ad absurdum). For this
argument we assume the truth of both P and (not Q) and seek a
contradiction.
From this we conclude that our hypothesis 'P and (not Q)' is false-
i.e. 'not (P and (not Q))' is true. But this is equivalent to 'P implies Q'
(exercise 2.11 (5)).
In practice Q may often be quite a complicated statement. In this case the
effectiveness of the second and third methods depends on the extent to which the
contradictory of Q (i.e. not Q) can be expressed in a useful form. In general, it is a
good idea to get the 'not' as far inside the expression as possible. For example,
'not {(Pand Q)or (not R)}'is more usefully expressed in the form'{ (not P)or (not
Q)} and R'. We return to this topic again in the next chapter.

2.14 Example We give three different proofs of the fact that, if

x 2 -3x+2<0, then x>O.
Proof 1 Assume that x 2 - 3x + 2 < 0. Then
3x > x 2 + 2 ~ 2 (because x 2 ~ 0).
Hence
It follows that 'x 2 - 3x + 2 < 0 implies x > 0'.

Proof 2 The contrapositive statement is that 'x:;;:; 0 implies

xx 2 - 3x + 2 ~ 0'. We therefore assume that x:;;:; 0. Then
x-1 :;:;o and x-2:;:;0.
 Logic (I) 13

Hence x 2 - 3x + 2=(x -l)(x- 2)~0.

It follows that 'x :;=; 0 implies x 2 - 3x + 2 ~ 0' and hence that 'x 2 - 3x + 2 < 0
implies x>O'.

Proof 3 Assume x 2 - 3x + 2 < 0 and x :;=; 0. Then

x 2 < 3x - 2 :;=; - 2 < 0.
This is a contradiction and hence 'x 2 - 3x + 2 < 0 implies x > 0'.
3 LOGIC (11)

3.1 Predicates and sets

A set is a collection of objects which are called its elements. If a is
an element of the set S, we say that a belongs to S and write
aES.
If b does not belong to S, we write b rf S.
In a given context, there will be a set to which all the objects we wish to
consider belong - i.e. the set over which we want our variables to range.
This set is called the universal set V. It is important to emphasise that the
universal set will not.always be the same. If we are discussing the properties
of the real number system, we shall want V to be the set of all real numbers.
If we are discussing people, we shall want V to be the set of all human
beings.
When it is clearly understood what the universal set is, we can discuss
predicates. A predicate is a sentence which contains one or more variables
but which becomes a statement when we replace the variables by objects
from their range.

3.2 Examples
(i) Let the universal set be the set IR of all real numbers. Some examples
of predicates which are meaningful for this universal set are:
(a) x>3 (b) 2x=x 2 (c) x+ y=z.

These predicates can be converted into statements by replacing x, y and z

by objects from their range. For example, the substitutions x = 2, y = 1, z = 3
yield the statements
(a) 2>3 (b) 2·2=2 2 (c) 2+ 1 =3
of which the first is false and the others true.
(ii) Let the universal set be the set of all people. Some examples of
predicates which are meaningful for this universal set are:
(a) x is president (b) x loves y.

14
 Logic (II) 15

If x and y are replaced by Romeo and Juliet respectively, we obtain two

statements of which the first is false and the second true.

One use of predicates is in specifying sets. The simplest way of specifying

a set is by listing its elements. We use the notation
A={t, 1, j2, e, n}
to denote the set whose elements are the real numbers t, 1, j2, e and n.
Similarly,
B = {Romeo, Juliet}
denotes the set whose elements are Romeo and Juliet. But this notation is,
of course, no use in specifying a set which has an infinite number of
elements. For such sets one has to name the property which distinguishes
elements of the set from objects which are not in the set. Predicates are used
for this purpose. For example, the notation
C={x:x>3}
denotes the set of all real nnmbers larger than 3 provided that it is
understood that the variable x ranges over the universal set IR1. Similarly,
D = {y: y loves Romeo}
denotes the set of people who love Romeo, provided that the variable y is
understood to range over the universal set of all people.
It is convenient to have a notation for the empty set (/). This is the
set which has no elements. For example, if x ranges over the real numbers,
then
{x: x 2 + 1 =0} =(,Z>.
This is because there are no real numbers x such that x 2 = - 1.

3.3 Exercise
(1) Let the universal set V be the set N of all natural numbers (i.e. 1, 2,
3, ... ). Then, for example, {x: 2 ~x ~4} = {2, 3,4}. Obtain similar identities
in each of the following cases.
(i) {x:x 2 -3x+2=0} (ii) {x:x 2 -x+2=0}
(iii) {x:x 2 +3x+2=0} (iv) {x:x 2 ~3+x}.
(2) Let the universal set V be the set IR1 of all real numbers. If
S={x:x 2 -3x+2~0},
16 Logic (11)

decide which of the following statements are true:

(i) lES (ii) 2~S (iii) 2ES (iv) 4~S.

3.4 Quantifiers
A predicate may be converted into a statement by substituting for
the variables objects from their range. For example, the predicate 'x > 3'
becomes the false statement '2 > 3' when 2 is substituted for x.
Another way that predicates may be converted into statements is with the
use of the quantifiers 'for any' and 'there exists'.
For example, from the predicates 'x > 3' and 'x loves y' we may obtain the
statements
'For any x, x> 3'
'For any y, there exists an x such that x loves y'.
These statements may be paraphrased in the more natural forms 'All real
numbers are bigger than three' and 'Everybody can find somebody to love
them'.
It is sometimes convenient to use the abbreviations 'V' instead of 'for any'
and '3' instead of 'there exists'. With this notation the statements above
become
Vx(x> 3)
Vy 3x(x loves y).

3.5 Exercise
(1) Paraphrase in ordinary English the following statements. Venture an
opinion in each case as to whether the given statement is true or false.
(i) 3x(x>3) (ii) Vx(2x=x 2 ) (iii) VxVz3y(x+y=z)
(iv) 3x(x is President) (v) 3xV y(x loves y).
(2) Examine carefully the meaning of the two statements
(i) Vy3x(x<y) (ii) 3xVy(x<y)
and explain why they are not the same.
(3) Introduce the abbreviations V and 3 into the following sentence:
'For any number x, we can find a number z such
that for every number y, xy = z'.
(4) If the universal set U is the set of all natural numbers, find the elements
 Logic (If) 17

of the sets
(i) {x: li y(xy= y)} (ii) {x: 3y(xy=12)}.

3.6 Manipulations with quantifiers

The contradictory of the statement 'li x(x > 3)' is simply 'not
li x(x > 3)'. In the previous chapter we noted that it is desirable to get the
'not' as far inside the expression as possible. How does one go about this
when quantifiers are involved?
In the example given above, the variable x ranges over an infinite set,
namely the set of all real numbers. It is instructive to consider first a case
where the variable ranges over only a finite set.

3.7 Example Let the universal set be the set of all human beings and
consider the statement
li x(God loves x).

This means the same as

'(God loves Romeo) and (God loves Juliet) and .. .'
where dots indicate that we continue until we have listed all human beings.
From chapter 2 (exercise 2.9(4)) we know how to write down the con-
tradictory of this statement. It is
'(God does not love Romeo) or (God does not love Juliet)
or .. .'.
That is to say, 'There exists at least one person whom God does not love'-
I.e.

3x{not (God loves x)}.

This mode of reasoning leads us to the rules embodied in the table below.

Statement Contradictory
Vx P(x) 3x(not P(x))
3x P(x) V x(not P(x))

As we have seen above, these rules only have something new to say in the
case when x ranges over an infinite set.
18 Logic (11)

3.8 Example

Statement Contradictory
Vx(x>3) 3x(x;;:23)
3x(2x=x 2 ) Vx(2x#x 2 )
:Jx V y(x loves y) Vx 3y(x does not love y)
\fx \fz 3y(x+y=z) :Jx :Jz lfy(x+y#z)

The third of these may be obtained in two stages. First one notes that 'not
:Jx Vy(x loves y)' is equivalent to 'V x {not Vy(x loves y)}' which is in turn
equivalent to 'Vx :Jy {not (x loves y)}'.

3.9 Exercise
(1) Write down the contradictories of the following statements in a useful
form.
(i) Vy :Jx(x<y) (ii) :Jx Vy(x<y)
(iii) :Jx(x>3 and x=4)
(iv) Everybody can find someone to love them.
(2) Apart from the rules for forming contradictories discussed above there
are some other rules for use with quantifiers. The table below contains a
list of equivalent statements.

Q and (V x P(x)) Vx(Q and P(x))

Q or (V x P(x)) Vx(Q or P(x))
Q and (:Jx P(x)) :Jx(Q and P(x))
Q or (:Jx P(x)) :Jx(Q or P(x))

Justify the third of these equivalences in the case when x ranges over a
finite set.

3.10 More on contradictories

We often have to form the contradictory of a statement like
'For any x>O, x 2 +x-2>0'.
This tells us that, for the purposes of this statement, the range of the
variable x is the set of positive real numbers instead of the set of all real
numbers. This makes no difference to the way in which we form the
contradictory, except that we must remember to keep the range of the
variable the same in the contradictory as it is in the statement.
 Logic (JJ) 19

Thus the contradictory of the statement above is

'There exists an x > 0 such that x 2 + x- 2 ~ 0'.

3.11 Examples
(i) The contradictory of the statement 'There exists an x < 1 such that
x 2 =1' is 'For any x<1, x 2 #1'.
(ii) The contradictory of the statement 'For any x<4 there exists a y>2
such that x + y = 3' is 'There exists an x < 4 such that for any y > 2, x + y # 3'.

3.12 Exercise
(1) Write down in a useful form the contradictories of the following
statements:
(i) There exists an x < 3 such that x > 2.
(ii) For any x satisfying 0 < x < 1, x 2 < x.
(iii) For any s > 0 there exists a c5 > 0 such that for any x satis-
fying 0 <x < c5, x 2 <s (i.e. x 2 ~0 as x~o + ).
(iv) Some Montague is hated by every Capulet.

3.13 Examples and counter-examples

To prove a statement of the type 'V x(P(x))' can be quite demand-
ing. One has to give an argument which demonstrates the truth of P(x)
whatever the value of x. It is certainly not enough to give some examples of
values of x for which it can be seen that P(x) is true.
To disprove a statement of the type 'V x(P(x))' is much easier. This is the
same as proving ':lx(not P(x))' and to do this one need only find a single y
for which P(y) is false. We say that such a y provides a counter-example to
the statement Vx(P(x)).

3.14 Example Show that the statement

'For any x>O, x 2 -3x+2~0'
is false. A single counter-example will suffice and an appropriate value of x
is l We have that

3.15 Example Show that it is false that rxP is irrational for all positive
irrational real numbers rx and p.
20 Logic (11)

Either cx 1 = {3 1 = J2 provides a counter-example, or else

C(2 = (j2)J2
is irrational. In the latter case, take {3 2 = )2. Then
cx/2 = { (j2)v' 2 }J2 = (j2) 2 = 2
and hence cx 2 and {3 2 provide a counter-example.
This example is somewhat unusual in being non-constructive, i.e. we
demonstrate that a counter-example exists without being able to say which
of (ex~> /3d and (cx 2, /3 2) it is.
4 SET OPERATIONS

4.1 Subsets
If S and T are sets, we say that S is a subset of T and write
SeT
if every element of S is also an element of T - i.e. xE S implies xE T.

4.2 Example Let A= {1, 2, 3, 4} and let B= {2, 4}. Then Be A. Notice
that this is not the same thing as writing BE A (i.e. B is an element of A). The
elements of A are simply 1, 2, 3 and 4 and B is not one of these.

It is often convenient to illustrate the relations which hold between sets

by means of a diagram (a Venn diagram). The diagram drawn illustrates the

relation SeT. The universal set is represented by the square and the sets S
and T by the shaded regions within the square.

4.3 Exercise
(1) Arrange the sets given in exercise 3.3(1) in a list, each item of which is a
subset of the item which follows it.

21
22 Set operations

(2) Draw a Venn diagram to illustrate the relation 'S is not a subset of T'.
(3) Justify the following
(i) S c U (ii) (/) c S (iii) S c S.
[Hint: Recall that(/) denotes the empty set. Thus, for any x, xE0 is false
and therefore implies anything!]
(4) Prove that S= T if and only if SeT and TcS. [Hint: S= T means
'xES~xET'.]

4.4 Complements
Ifs is a set, its complement es is defined by
S={x:x~S}.

In the accompanying diagram, es is represented by the shaded region.

When using the above notation for the complement of a set, it is

obviously important to be very clear about what universal set U is being
used.

4.5 Example Let the universal set U be the set of all real numbers
and let S={x:x>O}. Then
e S={x:x~O}.

4.6 Exercise
(1) Let U = {1, 2, 3, 4, 5, 6}. Write down the complements of the sets {1, 2}
and {1, 3, 5}.
(2) Prove the following.
(i) e (e S)=S (ii) eu=(/) (iii) e(/)=U.
 Set operations 23

4.7 Unions and intersections

Suppose that S and T are sets. Their union Su T and their
intersection Sn T are defined by
SuT={x:xES or xET}
Sn T= {x: xES and xE T}.

~SUT

4.8 Examples
(i) {1, 2}u{1, 3, 5} = {1, 2, 3, 5}
(ii) {1, 2}n{1, 3, 5} = {1}.

4.9 Exercise
( 1) We use the notation A \ B to denote the set of all elements of A which
do not belong to B - i.e. A\ B =An e B. Indicate the set A\ B on a
Venn diagram.
(2) Two sets A and Bare called disjoint if they have no elements in common
- i.e. A nB = (j). Illustrate this situation on a Venn diagram.
(3) Use exercise 2.9(2) to obtain the following identities.

(i) An(BnC)=(AnB)nC
(ii) Au(BuC)=(AuB)uC
(iii) Au(BnC)=(AuB)n(AuC)
(iv) An(BuC)=(AnB)u(AnC)
(v) e (AnB)= eAu eB
(vi) e (AuB)= eAn eB.

Results like those of exercise 4.9(3) are conveniently illustrated by means

of Venn diagrams. For example, problem (vi) may be illustrated as below.
24 Set operations

/
~ e(A UB) :sCAn CB

4.10 Exercise
(1) Illustrate each of the identities of exercise 4.9(3) by means of a pair of
Venn diagrams.

So far we have considered unions and intersections of pairs of sets. We

can equally well take the union or intersection of a whole collection of sets.
Suppose that W denotes a collection of subsets of a universal set U. Then
we define

U S = {x: there exists an SE Wsuch that xES]

SEU'

(\ S={x:for any SEW, xES}.

SEU'

4.11 Examples
(i) Suppose that W contains only three sets, P, Q and R - i.e.
W={P, Q, R}. Then

U S=PuQuR (\ S=PnQnR.
SE"U' SEW

The appropriate Venn diagrams are

~/ s.w
us ~ ns
'-
" s,U'
 Set operations 25

(ii) Let W be any collection of subsets of a universal set U. Prove that

e(u s)=n es.

SEW SEW

(See exercise 4.9(3vi).)

Proof e(u s)={x:not (xEU s)}

SEW SEW

= {x: not (there exists an SEW such that xE S)}

={x:for any SEW, not (xES/}
={x:for any SEW, xEe S}

4.12 Exercise
(1) Let W be the collection {A, B, C, D} where A={l, 3, 4}, B={l, 2, 4},
C={2, 3, 4}, D={l, 4}. What are the elements of the sets

(i) u s (ii) n s?
SEW SEW

(2) Let W be any collection of subsets of a universal set U. Let A E W and

let B be any other set in U. Prove the following.
(i) AcU S (ii) A::Jr1 S
SEW SEW

(iii) Bu{~, s}=~, {BuS} (iv) Bn{~, s}=~. {BnS}

(v) e(~, s)= ~~s
t(3) Explain why

(i) U S=0 (ii) ( l S=U

SEI!J SEI!J

4.I3t Zermelo-Fraenkel set theory

In Zermelo-Fraenkel set theory the idea is to express all of mathematics
in the language of set theory. The price one has to pay for this is that all
mathematical objects have to be defined as sets. The reward is that all mathematical
assertions can be expressed in terms of a single predicate

XEY

and all proofs referred to a single set of axioms - i.e. the axioms of set theory.
 26 Set operations

We do not attempt a systematic account of the Zermelo-Fraenkel programme in

this book. An attempt to do so would leave room for very little else. In later
chapters, however, we have been careful to indicate at each stage how the ma-
thematical objects being introduced can be defined as special kinds of sets (although
we shall certainly not insist on such an interpretation). Those seeking a more formal
account of the theory will find A. Abian's Theory of Sets and Transfinite Arithmetic
(Saunders, 1965) a useful reference.
In this section, we propose to make some remarks about the basic set-theoretic
assumptions on which the Zermelo-Fraenkel programme is based. The nature of
these assumptions is such that it is natural to take them completely for granted
without a second thought and this will be our attitude to the assumptions in the
main body of the text. This section is therefore one which can be skipped without
remorse if its content seems dull or difficult.
The basic assumption of the Zermelo-Fraenkel theory is that 'every property
defines a set'. One has to be a little careful over the formalisation of this idea
because of Russell's paradox. Suppose that we assume the existence of the set y
consisting of all sets x which do not belong to themselves - i.e.
y={x:xlfx}.
If yey, then y must satisfy the defining property of y- i.e. yify. On the other hand, if
yif y, then y satisfies the defining property of y and hence ye y. In either case, a
contradiction is obtained. The popular version of this paradox concerns a certain
barber who shaves everyone in his town who does not shave himself. The question is
then: who shaves the barber? All possible answers lead to contradictions and one
concludes that there is no such barber. Similarly, in Zermelo-Fraenkel set theory
one concludes that it is meaningless to speak of 'the set of all sets which do not
belong to themselves'. It is also meaningless to speak of 'the sets of all sets'. There is
no such set.
The assumption that asserts that 'properties define sets' is called the axiom of
replacement. For our purposes, the following version is adequate. Suppose that u is a
set and that P(x) is a predicate. Then
{x:xEu and P(x)}
is a set. Here, of course, u plays the role of the universal set U introduced in the
previous chapter and the fact that there is no 'set of all sets' explains our insistence
that U will depend on the context.
Next one needs an assumption that asserts that, if x is a set, then the union and
intersection of all sets in xis also a set. This assumption is called the axiom of unions.
One also needs an assumption that asserts the existence of the set of all subsets of a
given set s. The set of all subsets of s is called the power set of s and denoted by fl' (s).
(The reason for this nomenclature is that, ifs contains n elements, then fl' (s) contains
2" elements.) The axiom which asserts the existence of f1' (s) is therefore called the
power set axiom.
In Zermelo-Fraenkel theory, even the idea of 'equals' is not taken for granted.
Since all mathematical objects are to be regarded as sets, we only need a definition
of what it means to say that two sets are equal. The obvious thing to do is to define
two sets to be equal if and only if they have the same elements- i.e. x = y=V z(zex=
zey). Another way of saying this is that two sets are equal if and only if each is a
 Set operations 27

subset of the other. To make the definition useful, another assumption is required.
This is called the axiom of extensionality. Essentially, it asserts that, if x = y, then y
can be substituted for x in any statement without altering the truth value of the
statement.
Zermelo-Fraenkel theory requires two further assumptions which it is convenient
to postpone to later chapters. These are called the axiom of infinity and the axiom of
choice. It is a remarkable fact that the whole of traditional mathematics can be
based on the principles of logic and these six simple assumptions about the
properties of sets.
5 RELATIONS

5.1 Ordered pairs

The use of an ordered pair (a, b) of real numbers to label a point
in the plane will be familiar from co-ordinate geometry.
y

b - - - - - - - - - -, (a, b)

(0, 0) a X

We say that (a, b) is an ordered pair because the order in which a and b
appear is relevant. For example, (3, 4) does not represent the same point in
the plane as (4, 3).
How can we define an ordered pair in general? We certainly do not wish
to identify (a, b) with the set {a, b}. Both {3, 4} and {4, 3}, for example,
denote the same set. For this reason, the set {a, b} is often called an
unordered pair.
A viable alternative is to define
(a, b)= {a, {a, b}}
- i.e. (a, b) is defined to be the set whose elements are a and the set {a, b},
However, the precise form of the definition is irrelevant for our purposes.
Any definition which ensures that (a, b)= (c, d) if and only if a= c and b = d
will do just as well.

5.2 Cartesian products

The Cartesian product of two sets A and B is defined by
A xB={(a, b):aEA and bEB}.

28
 Relations 29

The notation A x B is used because, for example, if A has two elements

and B has three elements, then A x B has 6 = 2 x 3 elements.
When A and B are sets of real numbers, we can represent A x B as a set of
points in the plane.

AXB

We use the abbreviation A x A= A 2 • Thus IR1 x IR1 =IR1 2 represents the

whole plane.
In a similar way, one can introduce ordered n-tuples (a 1 , a 2 , ••• , a") and
consider the Cartesian product of n sets. In particular,

5.3 Relations
Any subset R of A x B defines a relation between A and B. If
(a, b)E R, we say that the relation R holds between a and b and write

a R b.

A XB

B
30 Relations

Obviously a relation R is determined if and only if, for each aE A and

bEB, it is known whether or not it is true that a R b.

5.4 Examples
(i) Let A and B both be the set of all human beings and write a R b if and
only if 'a loves b'. In accordance with the remarks above we may identify
the relation R with the set
R={(a, b):a loves b}.
(ii) Let A be the set N of natural numbers and let B be the set 71. of
integers. We write alb if and only if 'a divides b', i.e. b = ma for some integer
m. Some ordered pairs in the set
R={(a, b):alb}
are (2, 6), (3, -21), (1, 7).

5.5 Equivalence relations

The idea of equivalence is important not only in mathematics but
in life in general. Indeed, all abstractions are based on this idea. A Slovenian
peasant, for example, who considers that the only relevant criterion in
choosing a wife is that she be sturdily built is splitting the set of available
women into two 'equivalence classes'. He has invented an equivalence
relation with respect to which all sturdy women are equivalent, regardless of
their personal appearance or domestic skills. We have met the same idea in
logic. Two statements were said to be equivalent if they had the same truth
value, regardless of the subject matter with which they were concerned.
In mathematics, an equivalence relation R on a set A is defined to be a
relation between the set A and itself which satisfies the following require-
ments for each a, b and c in A:
(i) a R a (reflexivity) (ii) a R b<=>b R a (symmetry)
(iii) a R b and b R c=a R c (transitivity).
The most important example of an equivalence relation in mathematics is
the relation 'equals'. When we write x = y we mean that y may be sub-
stituted for x in any statement without altering the truth value of the
statement. (See §4.13.)

5.6 Examples
(i) An example of an equivalence relation on the set A of all human
beings is the relation R defined by a R b if and only if 'a and b have the
same mother'.
 Relations 31

(ii) An equivalence relation on the set 7L of integers may be obtained by

writing a R b if and only if a and b have the same remainder when divided
by 3.

Let R be an equivalence relation on A. If a 1 EA write

A 1 ={a:a R ad.
Then A 1 is the set of all aEA which are equivalent to a 1 • We call A 1 an
equivalence class of R.
As an example, consider logical equivalence on the set of all statements.
There are two equivalence classes: the class of true statements and the class
of false statements.

5.7 Theorem Two distinct equivalence classes are disjoint (i.e. have no
points in common).

Proof Let R be an equivalence relation on a set A. If a 1 EA and

a 2 EA, write A 1 ={a:aRad and A 2 ={a:aRa 2 }.
Suppose that A 1 and A 2 are not disjoint. Then they have an element bin
common. We shall show that this implies that A 1 =A 2 - i.e. A 1 and A 2 are
not distinct.
Since bE A 1 and bE A 2 , b R a 1 and b R a 2 • By the symmetric and transitive
properties for R it follows that a 1 R a 2 •

Now suppose that cEA 1 • Then c R a 1 • Hence c R a 2 by the transitive

property. Thus cE A 2 • It follows that A 1 c A 2 •
A similar argument shows that A 2 c A 1 and so we conclude that A 1 = A 2 •

5.8 Orderings
An ordering ~ on a set A is a relation between A and itself which
satisfies the following properties for each a, b and c in A:
(i) a~b or b~a (totality)
32 Relations

(ii) a~b and b~a=>a =b (antisymmetry)

(iii) a~b and b~c =>a~c (transitivity).

If the totality condition is replaced by reflexivity (i.e. a~a), we call ~ a

partial ordering. With a partial ordering, certain pairs of elements in A may
not be comparable. When discussing both partial orderings and orderings,
we sometimes stress the difference by calling an ordering a total ordering.

5.9 Examples
(i) The set ~ of all real numbers is ordered by the relation ~ of
increasing magnitude. This is the ordering with which we shall be chiefly
concerned in this book.
(ii) If A is a set, its power set S' (A) is the set whose elements are the
subsets of A. For example, if A={l, 2}, then 9'(A)={<P, {1}, {2), {1, 2)}.
Observe that the relation c is a partial ordering on S' (A).

5.10 Exercise
(1) Let A= { 1, 2, 3, 4, 5}. Let R be the relation between A and itself defined
by a R b if and only if a and b have the same remainder when divided by
2. Prove that R is an equivalence relation on A and determine the
equivalence classes it induces on A.
(2) Write aib if a and b are natural numbers and a divides b exactly. Show
that the relation so defined is a partial ordering on N.
(3) Explain why <=> is an equivalence relation on the set of all statements.
t(4) What is wrong with the following argument which purports to show that the
reflexive property for an equivalence relation may be deduced from the other
two properties? By the symmetry property, a Rh and bRa. Taking c =a in the
transitivity property then yields a R a.
Show, however, that the reflexivity property for an ordering may be deduced
from the totality condition.
t(5) LetS' (A) denote the set of all subsets of a set A.
(i) Prove that c is a partial ordering on S' (A).
(ii) Show that the relation R defined on S' (A) by
a R h=lfx(xEA<=>.YEB)
is an equivalence relation on S' (A).
t(6) Let ~ be a total ordering on a set A. Define the associated 'strict ordering'
relation <l by
a<:Jh=(a:;::Jh and a"# b).
Prove that <l is a transitive relation. Is <l a total relation? Is <l antisymmetric?
6 FUNCTIONS

6.1 Formal definition

A function f: A--> B is usually said in elementary texts to be a rule
which assigns a unique element yE B to each element XE A. But this is not a
very satisfactory definition because it leaves unanswered the question: what
is a rule? An answer to this question which is adequate for most elementary
applications is that a rule is an algebraic formula. Thus, for example, the
formula
y=g(x)=x 2 +1

defines a function g: IR: --.IR:. Any value XE IR: substituted in the right-hand
side will yield a unique corresponding value of yEIR: on the left-hand side.
But we shall wish to define functions in more complicated ways than this.
The expressions h(1)= 1 and

h(n + 1) =!{ h(n) + h~n) }'

for example, define a function h: 1\J --.IR; but one does not calculate h(n)
simply by substituting n in an algebraic formula. This is an example of a
recursive or inductive definition of a function.
In order to accommodate this and other even more complicated ways of

AXB

(x, y)

33
34 Functions

defining a function, we use the following formal definition. If A and B are

sets, we say that a function f: A-> B is a relation between A and B with the
property that, given any xE A, there exists a unique yE B such that (x, y)Ef
This definition amounts to identifying a function with its graph.
The importance of the idea of a function is attested to by the large
number of synonyms for the word 'function'. The words 'mapping', 'operator'
and 'transformation' are just three of the many alternatives. Which word is
used depends on the context. For example, it is sometimes useful to
interpret a function f: A-> B as a 'black box' into which an element xE A is
inserted as an input. The 'black box' then does something to x, the result of
which is the output f(x).

In this context one often calls the function an operator or transformation.

Thus one would think of the function g: IR ->IR given above as transforming
x into y by squaring it and adding one.
Alternatively, one may think of a function f: A-> B as describing the
efforts of a mapmaker who seeks to draw a map of country A on a piece of
paper B. It is in this context that one refers to a function as a mapping. A
point xE A is said to be mapped onto the point f(x)E B. Sometimes f(x) is
said to be the image of x under the function f

When thinking in these terms, it is necessary to bear in mind that the

mapmaker may not use up all of the piece of paper B in drawing the map of
A - i.e. there may be points of B which are the images of no points of A. It
may also be that several points of A are all mapped onto the same point of
B. For example, on a large scale map all of the points in the city of Paris
might be represented by a single point on the map.
What is not admissible is for a single point in A to be mapped onto
 Functions 35

several points of B. Each point xEA has a unique image yEB. One
sometimes reads of 'one-many functions' but this is an abuse of language
which we shall rigorously avoid.

6.2 Terminology
If f: A--> B is a function from A to B, we call the set A the domain
off and the set B the codomain off If S c A, we call the set
f(S) = {f(x): XE S}
the image of the set S under the function f In particular, f(A) is called the
range off Note that the range of a function need not be the whole of the
codomain - i.e. it need not be true that f(A) =B.

If Tc B, we call the set

f -I(T)= {X :f(.~)E T}
the pre-image of the set T under the function f

The notationf- 1(T) is in some ways an unfortunate one since it seems to

imply the existence of an inverse function to f Note, however, that it makes
36 Functions

perfectly good sense to talk about the pre-image of a subset T of B even

though an inverse function does not exist.
Let f: A--+ B be a function from A to B. It need not be true that B = f(A).
However, if it is true that B =f(A) we say that f is a function from A onto B
or that f is a surjective function. Thus, f is surjective if and only if each
element y of the codomain B is the image of an element x of the domain.
Again letf: A-+B. Suppose that, for each yEj(A), there is a unique xEA
such that y=f(x). Then we say thatfis a 1:1 function from A to B or thatf
is an injective function. Thus, f is injective if and only if f(x d =
f(xz)~xl =Xz.
If f: A--+ B is a 1: 1 function from A onto B (i.e. f is both surjective and
injective), then we call f a bijection. The requirement that f: A-+B is a
bijection can be rephrased as the assertion that the equation
y=f(x)

has a unique solution xE A for each yE B. But this is precisely what is

required in order that the equation y =f(x) define x as a function of y - i.e.
that there exists a function f- 1 : B--+ A such that
x =f- 1(y)=-y =f(x)
for each xE A and yE B.
We call f- 1 : B--+ A the inverse function of the function f: A--+ B. Note that
an inverse function to f exists if and only if f is a bijection.

6.3 Examples
(i) A sequence is simply a function whose domain is the set N of all
natural numbers. The nth term of a sequence f: N -+IR is defined to be
x" = f(n). We use the notation <x") to denote the sequence whose nth term is
x .. Thus the sequence <n 2 + 1) is to be identified with the function g: N -+IR
defined by
g(n)=n 2 + 1 (n= 1, 2, 3, ... ).
The first few terms of this sequence are
2, 5, 10, 17, 26, 37, 50, ....
(ii) The equations
2
u=x +
V=X2- y2
i}
define a function f: IR 2 -+IR 2 • The image of (x, y) under f is
(u, v)=(x 2 + y 2 , x 2 - yZ).
 Functions 37

Observe that f IS not surjective. If u and v are given by the above

equations, then
u+v=2x ~0}
2

u-v=2y ~0. 2

and hence, for example, the point (u, v) = ( -1, - l) is not the image of
anything under this function. In fact
f(IR 2 )={(u, v):u~v and u~-v}.
Nor is f injective. The equations
2
5=x +
3=xz- Yz
l}
have four solutions for (x, y)- namely (2, 1), (2, -l), ( -2, 1) and ( -2, -1).

y V u=v

I
xz + yz = 5\
f

(iii) Let A= {x: x ~0} and B= {y: y~ 1}. The function[: A --->B defined by
f(x)=x 2 +1 (x~O)

is a bijection and hence has an inverse functionf- 1 : B--->A. Since, for each
x~O and y~ 1,

x =f - 1(y)=-y =f(x),
a formula for f - 1 can be obtained by solving the equation y = x 2 + 1 to
obtain x in terms of y. Because y~ 1, the equation has a solution. Moreover,
as x~O, the solution is unique and is given by x=J(y-1). (Remember
J
that, if z ~ 0, then z denotes the non-negative number whose square is z.)
Thus
38 Functions

f X

X
A B

Note that either graph can be obtained from the other by a rotation about
the line x = y.

6.4 Exercise
(1) Consider the function/: ~ 2 -+~ 2 defined by f(x, y)=(u, v) where

u=x+y}
v=x-y.
Prove that f is a bijection and obtain a formula for its inverse
function. Findf(S) and/- 1 (T) in the case S=T={(x, y):O~x~1 and
O~y~1}.
(2) Let A={O: O<O~tn} and B={<P: -n<<P~n}. A function
g: A x B-+~ 2 is defined by (x, y)=g(8, <P) where

X=a sin 8 COS <P}

y=b sine sin <P.
Prove that the range of g is the set
x2 y2 }
F = { (x, y) I 0 < a 2 + b2 ~ 1

and show that g is injective.

(3) Let/: A-+B. If S 1 cS 2 eA, show that /(S 1 )cf(S 2 )cB. If T1 c T2 cB,
show that f- 1 (Tt)cf- 1 (T2 )cA.
(4) Let X denote a collection of subsets of A and Ya collection of subsets of
B. Iff: A-+ B, prove that

(i) 1(u s)=u

SeX SeX
f(S) (ii) 1(n s)cn
SeX SeX
f(S)
 Functions 39

(iii) ~-~(u r)=u f- 1(T)

TeY TeY

Give an example to show that equality need not hold in (ii).

(5) Let f: A--+ B.
(i) Prove that, for each S c A,
J- 1
(/(S))~s.

Show that f is injective if and only if f - 1(/(S)) = S for each S c A.

(ii) Prove that, for each T c B,
f(f- 1 (T))c T.
Show that, for each Tcf(A),f(f - 1 (T)) = T. Deduce that f is surjective if
and only if/(/- 1 (T))=T for each TcB.
(6) Suppose that A 1 c A 2 and consider two functions / 1 : A 1 --+ B and
/ 2 : A 2 -+B which satisfy

for each xE A 1 . We say that / 1 is the restriction of / 2 to A 1 and that / 2 is

an extension of / 1 to A 2 •
Define f IR -+IR by f(x) = lxl. Let g be the restriction off to (0, oo ).
Find an extension of g to IR which is differentiable at every point of IR.

6.5 Composition
Suppose that f: B--+ C and g: A--+ B. Then their composition
fog:A-+C is defined by
fog(x)=f(g(x)) (xEA).

Suppose that f: A--+ B is a bijection. Then it has an inverse function

f- 1 : B-+A. The composite functionsfof- 1 : B-+B and f- 1 of: A-+A are then
both identity functions - i.e. they map each point onto itself. To see this,
Exploring the Variety of Random
Documents with Different Content
damaged disk or other medium, a computer virus, or computer
codes that damage or cannot be read by your equipment.

1.F.2. LIMITED WARRANTY, DISCLAIMER OF DAMAGES - Except for

the “Right of Replacement or Refund” described in paragraph 1.F.3,
the Project Gutenberg Literary Archive Foundation, the owner of the
Project Gutenberg™ trademark, and any other party distributing a
Project Gutenberg™ electronic work under this agreement, disclaim
all liability to you for damages, costs and expenses, including legal
fees. YOU AGREE THAT YOU HAVE NO REMEDIES FOR
NEGLIGENCE, STRICT LIABILITY, BREACH OF WARRANTY OR
BREACH OF CONTRACT EXCEPT THOSE PROVIDED IN PARAGRAPH
1.F.3. YOU AGREE THAT THE FOUNDATION, THE TRADEMARK
OWNER, AND ANY DISTRIBUTOR UNDER THIS AGREEMENT WILL
NOT BE LIABLE TO YOU FOR ACTUAL, DIRECT, INDIRECT,
CONSEQUENTIAL, PUNITIVE OR INCIDENTAL DAMAGES EVEN IF
YOU GIVE NOTICE OF THE POSSIBILITY OF SUCH DAMAGE.

1.F.3. LIMITED RIGHT OF REPLACEMENT OR REFUND - If you

discover a defect in this electronic work within 90 days of receiving
it, you can receive a refund of the money (if any) you paid for it by
sending a written explanation to the person you received the work
from. If you received the work on a physical medium, you must
return the medium with your written explanation. The person or
entity that provided you with the defective work may elect to provide
a replacement copy in lieu of a refund. If you received the work
electronically, the person or entity providing it to you may choose to
give you a second opportunity to receive the work electronically in
lieu of a refund. If the second copy is also defective, you may
demand a refund in writing without further opportunities to fix the
problem.

1.F.4. Except for the limited right of replacement or refund set forth
in paragraph 1.F.3, this work is provided to you ‘AS-IS’, WITH NO
OTHER WARRANTIES OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR ANY PURPOSE.

1.F.5. Some states do not allow disclaimers of certain implied

warranties or the exclusion or limitation of certain types of damages.
If any disclaimer or limitation set forth in this agreement violates the
law of the state applicable to this agreement, the agreement shall be
interpreted to make the maximum disclaimer or limitation permitted
by the applicable state law. The invalidity or unenforceability of any
provision of this agreement shall not void the remaining provisions.

1.F.6. INDEMNITY - You agree to indemnify and hold the Foundation,

the trademark owner, any agent or employee of the Foundation,
anyone providing copies of Project Gutenberg™ electronic works in
accordance with this agreement, and any volunteers associated with
the production, promotion and distribution of Project Gutenberg™
electronic works, harmless from all liability, costs and expenses,
including legal fees, that arise directly or indirectly from any of the
following which you do or cause to occur: (a) distribution of this or
any Project Gutenberg™ work, (b) alteration, modification, or
additions or deletions to any Project Gutenberg™ work, and (c) any
Defect you cause.

Section 2. Information about the Mission

of Project Gutenberg™
Project Gutenberg™ is synonymous with the free distribution of
electronic works in formats readable by the widest variety of
computers including obsolete, old, middle-aged and new computers.
It exists because of the efforts of hundreds of volunteers and
donations from people in all walks of life.

Volunteers and financial support to provide volunteers with the

assistance they need are critical to reaching Project Gutenberg™’s
goals and ensuring that the Project Gutenberg™ collection will
remain freely available for generations to come. In 2001, the Project
Gutenberg Literary Archive Foundation was created to provide a
secure and permanent future for Project Gutenberg™ and future
generations. To learn more about the Project Gutenberg Literary
Archive Foundation and how your efforts and donations can help,
see Sections 3 and 4 and the Foundation information page at
www.gutenberg.org.

Section 3. Information about the Project

Gutenberg Literary Archive Foundation
The Project Gutenberg Literary Archive Foundation is a non-profit
501(c)(3) educational corporation organized under the laws of the
state of Mississippi and granted tax exempt status by the Internal
Revenue Service. The Foundation’s EIN or federal tax identification
number is 64-6221541. Contributions to the Project Gutenberg
Literary Archive Foundation are tax deductible to the full extent
permitted by U.S. federal laws and your state’s laws.

The Foundation’s business office is located at 809 North 1500 West,

Salt Lake City, UT 84116, (801) 596-1887. Email contact links and up
to date contact information can be found at the Foundation’s website
and official page at www.gutenberg.org/contact

Section 4. Information about Donations to

the Project Gutenberg Literary Archive
Foundation
Project Gutenberg™ depends upon and cannot survive without
widespread public support and donations to carry out its mission of
increasing the number of public domain and licensed works that can
be freely distributed in machine-readable form accessible by the
widest array of equipment including outdated equipment. Many
small donations ($1 to $5,000) are particularly important to
maintaining tax exempt status with the IRS.

The Foundation is committed to complying with the laws regulating

charities and charitable donations in all 50 states of the United
States. Compliance requirements are not uniform and it takes a
considerable effort, much paperwork and many fees to meet and
keep up with these requirements. We do not solicit donations in
locations where we have not received written confirmation of
compliance. To SEND DONATIONS or determine the status of
compliance for any particular state visit www.gutenberg.org/donate.

While we cannot and do not solicit contributions from states where

we have not met the solicitation requirements, we know of no
prohibition against accepting unsolicited donations from donors in
such states who approach us with offers to donate.

International donations are gratefully accepted, but we cannot make

any statements concerning tax treatment of donations received from
outside the United States. U.S. laws alone swamp our small staff.

Please check the Project Gutenberg web pages for current donation
methods and addresses. Donations are accepted in a number of
other ways including checks, online payments and credit card
donations. To donate, please visit: www.gutenberg.org/donate.

Section 5. General Information About

Project Gutenberg™ electronic works
Professor Michael S. Hart was the originator of the Project
Gutenberg™ concept of a library of electronic works that could be
freely shared with anyone. For forty years, he produced and
distributed Project Gutenberg™ eBooks with only a loose network of
volunteer support.
Project Gutenberg™ eBooks are often created from several printed
editions, all of which are confirmed as not protected by copyright in
the U.S. unless a copyright notice is included. Thus, we do not
necessarily keep eBooks in compliance with any particular paper
edition.

Most people start at our website which has the main PG search
facility: www.gutenberg.org.

This website includes information about Project Gutenberg™,

including how to make donations to the Project Gutenberg Literary
Archive Foundation, how to help produce our new eBooks, and how
to subscribe to our email newsletter to hear about new eBooks.
Welcome to our website – the ideal destination for book lovers and
knowledge seekers. With a mission to inspire endlessly, we offer a
vast collection of books, ranging from classic literary works to
specialized publications, self-development books, and children's
literature. Each book is a new journey of discovery, expanding
knowledge and enriching the soul of the reade

Our website is not just a platform for buying books, but a bridge
connecting readers to the timeless values of culture and wisdom. With
an elegant, user-friendly interface and an intelligent search system,
we are committed to providing a quick and convenient shopping
experience. Additionally, our special promotions and home delivery
services ensure that you save time and fully enjoy the joy of reading.

Let us accompany you on the journey of exploring knowledge and

personal growth!

ebooknice.com