nm0863: er a number of you went to the first year discussion evening yesterday 
and i wasn't able to be there myself but if any of you here have any feedback 
about this particular course that you'd like to relay to me that came up at 
that meeting i'd be very grateful to hear it so come and see me after the 
session if there are any special points that i can address let's just cast our 
mind back over the last two weeks what have we been doing in this course we've 
been looking at arithmetic from a new point of view we've taken familiar ideas 
like adding subtracting multiplying dividing ordinary numbers and looking at 
them from different structural viewpoints through division with remainder 
Euclid's algorithm using that to prove formally the fundamental theorem of 
arithmetic which says every natural number can be uniquely expressed as a 
product of prime powers we've also taken time out to study very quickly the 
complex numbers those of you who hadn't met them before are strongly advised to 
get plenty of practice at 
using them and if you have trouble with the ideas to consult a mate a buddy who 
does know about them and er we also er took time out to study mathematical 
induction and er i thought you'd be amused to see this [laughter] alternative 
image for the falling dominoes as an indication of how induction works so 
basically we've been doing two things we've been bridging the gap looking at 
arithmetic in a a more professional way and we've been filling a gap of 
knowledge in complex numbers and we've been studying at least one method of 
proof namely mathematical induction well today i want to focus on the 
foundations aspect of the course and i want to go right back to the very 
beginning do you read these notes i produced do you actually read them or do 
you i mean in your own time they are meant to be read i don't have time within 
the lecture to read out every word and i hope you do look for the er the 
details when you take them away i hope the assignments i set give you the 
motivation to go away and read them er today we're talking about the fact that 
mathematics could be entirely based on set theory and that the notion of a set 
is a primitive undefined concept and i'd like to make the point that however 
good your dictionary is it cannot define everything without some kind of 
circular definition and to check this out i took a couple of words at random er 
and i pursued them through a list of definitions mathematics the science of 
magnitude and number i looked up science knowledge ascertained by observation 
and experiment critically tested systematized brought under general principals 
knowledge that which is known to know is to be informed of and then we get our 
first circular definition to inform is to pass on knowledge so at some point 
you must reach words in the dictionary which cannot be defined without making a 
circular argument i looked up another word at random i don't know why i chose 
cow but it very 
quickly became circular cow the female bovine animals bovine of or pertaining 
to cattle er cattle bovine animals of the genus Bos especially oxen bulls and 
cows and we're back in the circle again so i say there are only a finite number 
of English words so it's impossible to avoid circular definitions unless you 
accept certain basic words as primitive undefined concepts which we all know 
the meaning of but don't need or not even able to define and mathematicians of 
course are bound by the same rules we're very big on definitions but we can't 
define absolutely everything however we do rather well we make just one we make 
do with just one primitive idea the concept of a set so i'm not going to define 
the concept of a set but i'm going to talk about it and hope that your idea of 
what a set is coincides closely with my idea and that of most mathematicians it 
turns out that the whole of mathematics can be founded on this one simple 
notion and a subtext of this 
course of lectures a not so hidden agenda is to show how this can be achieved 
so we we can't offer a formal definition of a set because that's our primitive 
undefined object but we can make an informal definition as to what we mean by 
it and we now come to A-point-one definitely not a definition a set is just a 
collection of things and the things in the set are called elements whoops or 
[laughter] the members of that set and we have a bit of standard notation 
typically we use upper case letters for the sets themselves not always but very 
often and we use lower case letters often related closely to the upper case 
letter in the alphabet to denote the members or the elements of that set so 
here's a bit of standard notation X this funny epsilon sign big-X this should 
be read out loud as the element X is a member of or belongs to or is in the set 
of capital-X if we have a finite set we can list its elements X-one X-two up to 
X-N if we know what N is we can write them all out but we 
don't always deal with just finite sets er the integers themselves are an 
example of an infinite set and even integers you can describe in this way we 
use these braces a set of integers N elements little-N in Z the set of all 
integers two-divides-N that's a way of describing in set theoretical notation 
the even integers or sometimes we suggest what the set looks like this is meant 
to indicate the set of all even integers but this sort of notation depends on 
the tacit understanding that i've given enough information for you to see 
what's going on and that you've cottoned on to what i mean someone who is 
bloody-minded might say well why isn't the next one seven there's no reason why 
it shouldn't be but i've meant to indicate what i'm up up to there so what do 
we expect of a set these are important properties a set is determined by its 
elements and that sounds rather trite but a lot of people have trouble deciding 
when two sets are equal so let's be very 
clear about this two sets are equal if and only if they contain the same 
elements so we have the notion of equality which we use the usual equal sign 
for between sets the elements of a set must be distinguishable from each other 
we only count each element once so if we wrote down one and one it's really 
only got one element and we should accept the convention of writing it as a 
single one so we think of all the elements of the set when we list them as 
being different now this is an important one when you write out a set the order 
the way you write them out the l-, the order in which you write them out or 
label them is unimportant so the set containing X and Y can be written that way 
or that way those two sets are the X and Y have the same elements therefore 
they are equal even though they're written out in different order so th-, the 
property of being a set takes no account of the ordering or the labeli-, or the 
labelling of the elements if you've got a set it's not well defined unless we 
have some method of deciding whether anything is in the set or not so there's 
got to be some well defined procedure that tells you if i give you this is it 
in your set or not if you can always do that then your set is a genuine set and 
well defined now this last one i-, is er is just perhaps important to stress a 
lot of people think the objects of a set should be somehow related to each 
other like a set of numbers or a set of er students in a room or whatever but 
they can be totally er different have n-, no relation to each other no 
uniformity no common property so for instance er a particular cat and a 
particular fiddle and a particular cow and the moon and a certain dog and the 
word laughter can all be elements of this set with one two three four five six 
elements if you've got any questions about sets i'll give you a break in the 
middle to have you got one now i'm happy to take questions at any point but if 
you it's often hard to ask questions in a big audience if you've got some 
questions i'll let you 
have a chance to talk to your neighbours about it and then you might feel more 
confident about asking so here are some examples of s-, sets the students 
attending the first foundations lecture you here today i presume are a subset 
of that set probably a proper subset it being now nine o'clock in the morning 
although the first one was at nine too but you were er bit less er inured to 
the ways of the world on the first day on the first Wednesday of term er here's 
an interesting set the set of real numbers that satisfy this equation if you 
draw the graph so the graph lies the X axis completely so there are no real 
numbers satisfying that so that's another way of defining the empty set however 
if we allow the variable X to be in the field of complex numbers rather than 
the field of real numbers there are indeed two numbers in that set so be very 
specific where the elements come from if you are using this notation the set of 
certain things with a straight line and then a certain 
property the set of all X in here satisfying that property some non-examples 
there are a set of people in the first foundations lecture who will be alive on 
January the first two-thousand we hope that is the same set but we won't know 
until the first of January two-thousand-and-fifteen er but i certainly shan't 
be around and so that's one less peop-, one less person we won't know until two-
thousand-and-fifteen er whether what what set is who belongs to it er the set 
of water in the Atlantic Ocean well there are lots of problems with that set 
water doesn't have any discreteness so you could talk about the molecules of 
water perhaps but water is er er an amorphous structure er you could talk about 
the molecules of water in the Atlantic Ocean you'd still have trouble er 
because the Atlantic Ocean isn't terribly well defined where does it stop and 
where does it begin and molecules of water are constantly dancing er above the 
surface of the water are they in or are they out and if someone gave you 
[laugh] a molecule how 
could you ever tell whether it came from the Atlantic Ocean or not because all 
molecules of water are the same so i wouldn't accept this as a set and then er 
there are also problems in logic with making sets too big and in particular the 
set of all sets is not allowed for reasons that we shall see later okay 
everyone happy about sets anybody got any questions right the first important 
idea in sets is to talk about subsets 
nm0863: i don't think it's a very difficult idea a subset of a set is a set 
consisting of some possibly all the elements i haven't done that very clearly 
er the sub-, er B is a subset of A if any element of B is in A that's all it 
says er the notation is important however er for any old subset we use this 
curly less than or equal to sign that allows the possibility that B is equal to 
A note from the definition that A is one of the subsets of A A itself's a whole 
set and that the empty set of course is also a subset if we want to highlight 
the fact that we have a a proper subset we use 
the slightly different notation if we remove the bottom line there and this 
notation means B is a subset of A and B is not equal to A that means there's 
something in A but not in B er so the remarks i've already made don't forget 
that A is one of the subsets of A note that every set contains the empty set as 
a subset because the condition is vacuously satisfied now this is very 
important you're often asked to show that two sets described in different ways 
are actually equal and there's one standard and infallible technique for doing 
that what does it mean to say two sets are equal means they've got you've got 
to show they have the same elements and the way you do it is to show that if 
you've got anything in B it's in C if you got anything in C it's in B those two 
together tell me that the elements in B are the same as the elements in C and 
therefore the two sets are equal so the routine is this is what i call a double 
inclusion argument to show that B equals C you show first that B is a subset 
of C then you show C as a subset of B er and you've got a safe way of checking 
that the two sets have the same elements and finally the observation i already 
made if B is a proper subset of A there's at least one element of A which is 
not in B let's have some examples every non-empty set has a least two subsets 
mainly the whole set and the empty subset for each X in a non-empty set A 
there's always a one element subset and we use the notation X with braces round 
it and it's important to distinguish X as an element of X and this subset or 
sometimes a singleton er is a subset and therefore it's known to the set of all 
subsets of A so X is distinct from it's different from the set containing it 
and this is an excuse to remind you of some important subsets of the real 
numbers that crop up time and time again in analysis i don't know if you've met 
them yet but if not you soon will er round brackets A comma B the assumption 
there is that A and B are 
real numbers and that A is less than B and this set stands for all the X that 
lie between A and B so if this is your real line if you're assuming that A is 
less than B then all the points in there are denoted by the open interval A-B 
and if you stick in both the end points as well you use the square bracket 
notation so you get this set by adding the two end points to that set notice 
that these intervals are always infinite however close A is to B and then 
you've got the choice of a half open interval this is called a closed interval 
because you've closed it off at the ends it can have half open intervals with A 
missing or with B missing and this notation speaks for itself and you can even 
use the symbol infinity symbolically to be A to infinity it's all real numbers 
strictly bigger than A er minus-infinity A in square brackets is all real 
numbers less than or equal to A and in this notation minus-infinity plus-
infinity would be another way of describing the whole real line 
that's just the symbolic notation which is useful 
nm0863: so we've talked about sets we've talked about subsets and now we come 
to some useful notation in making new sets from given sets we defined three 
important binary operations a binary operation is something that has an input 
of two things and an output of one so when you feed in two sets A and B the 
intersection is a subset consisting of all elements that are both in A and B if 
the union again a binary operation feed in two sets A and B the union just 
consists of all elements that are in X or in B or possibly in both it's not er 
i-, i-, it's not the exclusive or it's the inclusive or so A-union-B contains 
everything in A everything in B together with everything in both that's the 
union intersection union and the set theoretical difference everything in A 
take away from A everything that lies in B that's called the set theoretical 
diff-, difference er difference the set of elements that lie in A but not in B 
and one of my 
standard bits of advice to anyone studying mathematics if you don't understand 
it draw a picture and that's what John Venn did he had this rather nice er idea 
of representing a set as an area and then visually the intersection is 
everything in er common the union is everything in both and the difference is 
everything in A but not in B do you find those pictures helpful i do i've 
always found them helpful so thanks to John Venn for being brave enough to draw 
a picture and letting us all know about it so the diagrams above show two sets 
A and B in general position with separate regions for each of the three subsets 
er A-minus-B A-intersection-B and B-minus-A there are three different connected 
regions here and these shaded regions are made up in different ways of the 
three connected regions Venn diagrams can be used to show special relationships 
between sets such as inclusion this picture suggests that A is entirely 
contained in B so A is a subset of B 
now one important thing in studying sets is to have a safe space in which to do 
your set theory if you allow too much extraneous possibility you get into 
logical difficulties which we will see er so what we tend to do i-, when we're 
working with set theory is to fix some genuine set some bona fide set U that's 
big enough to contain all the sets that we're likely to consider in a given 
setting and er to call that the universe the the set everything happens in so 
in this case i've drawn the universe as a sort of square containing box and the 
assumption is that while i'm doing set theory everything will happen inside 
that box if you find the universe you chose is to small to begin with you can 
obviously enlarge it er so that er you include new sets if you have to so if we 
started out with the real numbers as the universe and we came upon an equation 
which had complex roots it might be convenient just to enlarge the universe to 
U and then you'd include those roots er the only 
important thing is that once you've chosen your universe for a given discussion 
you'd better stick to it and once we've got a universe we can define a 
complement if we've got a universe then the complement denoted by this little 
exponent C is everything in the universe that's not in A er it's denoted by the 
shaded region and obviously what the complement is depends entirely on which 
universe you're working in so you could define A-to-the-C with our other 
notation it's U- minus-A if you change your universe you obviously change your 
complement so i've defined the complement here to it's the shaded region in the 
Venn diagram and er i'm going to have a little break there to focus on a 
problem that's of some interest typically er people draw circles for their sets 
when they're using Venn diagrams so let this blackboard be the universe if i 
draw one set it divides the universe into two parts the inside and the 
complement outside if i draw two sets circles how many regions do i get 
one two three and everything not in those four so with two sets i get four 
regions in the plane how many do i get if i have three sets i'm looking at all 
possible intersections of these various sets and i'm looking at the connecting 
regions i get let's do a count the outside one two three four five six have i 
left some out the outside one two three four five six seven and the outside was 
eight side two what do you think i get in general well you've guessed it you 
should get two-to-the-N sets because every time you draw a new set you divide 
in half each of the existing sets my question is if you stick to circles do you 
always get two-to-the-N regions so i want you to look at the region for four 
sets and decide whether now you get get your paper out get your pen out and see 
if you can get sixteen regions with four circles 
nm0863: that's one thing i didn't make clear was that i was talking about what 
i call simply connected regions those are the regions that if you were a fly 
you could move 
around in you get chambers here without crossing any of the boundaries and the 
general consensus here is that there are fourteen rather than sixteen does 
anyone know why 
sm0864: 
nm0863: yeah i mean the reason is that two circles intersect in how many points 
ss: two 
nm0863: two exactly two no more than two and therefore by the same argument as 
the pizza problem the number of new regions you can introduce by drawing a new 
circle is strictly limited so you can't using circles get all the regions you'd 
like to to show the disposition of N sets in its greatest generality so if you 
allowed yourself the luxury of rectangles rather than circles could you then do 
it now i'm offering a small prize to a written solution to the first one handed 
in which is lucid mathematically correct and is either a proof or a counter-
example the object is to get two-to-the-N connected regions and sets okay and 
for your delectation we have a number and your object here is to come up with a 
plausible reason why that number of the 
week is an interesting number and i will tell you next week okay any questions 
at this point 
sm0865: now i don't see how you can 
nm0863: you don't see how the 
sm0865: er are you saying that all rectangles 
nm0863: if instead of using circles you use rectangles could you represent the 
two-to-the-N connected regions that you get by intersecting 
sm0865: so how can you 
nm0863: well this was a counter-example with circles here you you can actually 
prove that you can't get more than fourteen by counting the intersections with 
the existing circles 
sm0866: 
nm0863: sorry 
sm0866: 
nm0863: it means that you can never get sixteen i can 
sm0866: 
nm0863: prove that you can never get sixteen regions which you should get if 
you're using circles so it may be that you can never get sixteen regions using 
rectangles or even if you can get sixteen it may fail at the next level thirty-
two or it may fail at sixty-four so that's your problem can you always do it 
for all N or does it fail at some point with rectangles now there are lots of 
rules about intersections and here are er two examples of these so-called 
identities for sets De Morgan's Laws when you fix some 
universe as usual you take two sets and then one of De Morgan's Laws says the 
complement of the intersection is the union of the comp-, complement so the 
rule there is whenever you apply complementation to a case of two things with 
an intersection to complement each of the constituents and put a union and vice 
versa if you had a union row this gives you this gives you an algorithm for 
converting er the complement of a complicated expression using intersections 
and unions into er the intersection and union as complements so i'll just give 
you an idea of how you prove that two sets are equal so i'm going to prove the 
left-hand log and the point about that it holds for all sets A and B it's not 
dependent on their being a particular set and when something holds for all sets 
like that we call it an identity set theoretical identity so we've got to go 
we've got to do the double inclusion argument so we start out with the left-
hand set and we take X in the complement of A-intersect-B 
so X is not in the intersection so it's not in both A and B so X is not in at 
least one of A and B so it's either not in A or not in B so X is either in the 
complement of A or the complement of B or possibly both and therefore it's in 
the union of A-complement B-complement that proves that inclusion now you take 
the right-hand side you take an element of the right-hand side er the right-
hand side of the first De Morgan Law will let us but if it's in the left-hand 
that's the left-hand side of this inclusion if X is in there then it's either 
not in A or it's not in B it's therefore never in both and hence it's not in 
the intersection so this is in there we've shown the inclusion both ways and 
that's the way we show two sets are equal if in doubt you er draw a picture and 
er so the first the left-hand side of the first De Morgan Law is the complement 
of er the intersection there's the intersection and the complement of that is 
everything not er it's everything not inside there that's 
the only bit that's not in the set if you take the right-hand side you have to 
take the complement of A the complement of A is everything outside A and the 
complement of B is everything outside B and anything that's not in the union of 
those two the pink and the white is again the intersection of the two so the 
two sets are equal in Venn terms as well but because you can't fully represent 
the sets using traditional Venn diagrams with circles you have to be very 
cautious about saying the Venn diagram is a proof it's okay up to three sets 
but you get into difficulty if you have more than three so De Morgan's Laws are 
examples of set theoretical identities they're equations that hold whatever 
sets are substituted for A and B we can think of the symbols A and B as 
variables that range over all possible sets an identity is an equation between 
two set theoretical expressions that hold for all values of the variable there 
are lots and lots of identities involving two sets er there are 
some fairly obvious ones like the u-, the intersection of A and B is the same 
as the intersection of B and A the same with unions er not quite so obvious are 
these distributed laws A intersect the union of B and C is the union of A-
intersect-B and A-intersect-C and similar one with unions and intersections 
interchange and this raises the principle of duality and if you have any 
identity er involving sets intersections and unions you will automatically get 
another identity interchanging all the unions and intersections so it's all 
from the first distributed law there i swap over the unions and the 
intersections and i get another true identity and the reason for it here is 
spelled out using De Morgan's Laws i'll leave you to read that one in your own 
time because in the last few minutes i want to come on to some logical problems 
that you get if you allow too many sets to arise it's it's worth knowing that 
er this book which i will circulate on a list of recommended books for the 
course in due course it's a di-, it's rather large book called Discrete 
Mathematics with Application it's pretty strong on set theory and it has a very 
comprehensive list of all the basic identities for sets of this kind yep there 
is a snake lurking in the grass er incidentally if you like this kind of there 
was a splendid book er by Raymond Smullyan the title of the book is What is the 
Name of this Book and er it has lots of er splendid examples of logical and 
verbal paradoxes anyway consider this particular one you've got a certain town 
there's a barber who shaves all the men who do not shave themselves I go there 
but no one else if they shave themselves the barber doesn't shave so let the 
universe U consist of all the men in that town and let the set A consist of all 
the men who shave themselves by definition of the universe either someone 
shaves themselves or they don't and the question is does the barber belong to A 
or A-complement if he belongs to A and he shaves himself but that's not 
possible because he only shaves men not in A on the other hand if he belongs to 
the complement of A by definition of A he shaves himself and so he belongs to A 
so you have the contradiction that the barber is in the set and its complement 
which is the set to the empty set er there are two ways to escape from this 
paradox you can either assume the barber had a beard or you can point out that 
er er the paradox is just a logical booby trap er because it's not possible for 
the statement the barber shaves all men who do not shave themselves and shaves 
no one else it's not possible for that be a true statement if you allow the 
barber in the universe so that was er a trick but a more serious problem er was 
pointed out by Bertrand Russell who spent years er trying to er flog himself to 
death in using set theory mathematical logic to prove all mathematics er he's 
sometimes defined as the philosopher who shaves all people who do not shave 
themselves er but his problem was the following his paradox take the 
universe to be the set of all sets and then you can define the subset of that 
universe er to consist of all sets that don't contain themselves i point out 
that er the set of integers that's not an integer so Z is not in Z Z does not 
contain itself so Z that set is in our set A on the other hand the set of all 
sets is a set so it belongs to itself and so the complement of A contains U so 
there are both kinds of sets those that contain themselves those that don't now 
the question er we have to ask is does A the set of all sets that don't contain 
themselves does it contain itself or not does it belong to A or the complement 
of A well if A belongs to itself then what does A define it must be one of 
those sets that do not belong to itself in other words A is not in A so it's in 
the complement on the other hand if A 
belongs to the complement then A belongs to itself or it symbols A is in A 
either way we get A in A- intersect A-complement which is the empty set so 
that's a serious objection if we allow the set of all sets to be a set so we 
don't so we have to be much stricter about what sets are allowed in the scheme 
of things and er there are ways of for getting round this basically you start 
with the em-, the empty set and build up and what you can get by that process 
is what's allowed and you don't end up with a set of all sets er poor old 
Russell got his comeuppance because in nineteen-thirty-one Gödel showed it 
wasn't possible to prove rigorously that mathematics is free from 
contradictions so we always have to live with a cloud of doubt over our heads