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