# 20150922 Discrete Structures Set Theory

these are really unordered so this is exactly the same thing as this that make sense again okay we’ll talk about how these relate to certain kinds of tables though and that may clarify it so sets can be anything if the set only has a few elements we can write it by just listing all the elements in the set if it had many elements will sometimes use short hands like as equals and most of us would interpret this as saying that s contains 1 2 3 but also a 4 5 6 7 8 9 all the way up to and including 98 99 and 100 if you want to write all hundred numbers you can use a short hand like this and so this set contains the first hundred positive integers or we could write something like which implies this includes 1 2 3 but it keeps going so it’s all positive integers and these aren’t really rigorously defined their kind of based on our understanding that one two three means a set of sequential integers but if we meant something more subtle like would you think that nine is a member of that said what you might be wrong because I might have meant prime numbers 3 5 7 11 13 or I might have been odd numbers so this can be ambiguous so we want a more precise mathematical looking way to specify that we have a number of options so for example I could stay p equals so all prime numbers but that’s too much English ya know this can be infinity yes instead of all the New Jersey’s is there so we could just use words if we know how to describe what we’re interested in if we wanted the set of even numbers bigger than 0 again that might be obvious or that could be something different so here’s a more precise way to define this I could say e is the set of all to N and this colon you can read as such that so this set is a set of all 2 times n such that or where n is an integer bigger than or equal to watch so if n is 1 this is 2 if n is 2 this is 4 if n is 3 this is 6 if n is a million this is 2 million and our set is the collection of all things which are 2 times n where n is something that you’re bigger than 1 so that’s a way to define the set of even numbers there than 0 what’s set with this define instead of all to n plus 1 such that ended every odd numbers above 1 and if you want to see that just start plugging in values

of N and look for a pattern if n is 1 this will be 3 if n is 2 this will be 2 times two is four plus 1 is 5 the finest 3 it’ll be six plus 1 is 7 and you’ll end up with all the odd numbers bigger than one if I wanted odd numbers that included one I have a few options one option would be to let n be bigger than or equal to 0 because now if n is 0 then this would be 2 times 0 plus 1 that would include one or I could do to n minus 1 because now if n is 1 this is 2 minus 1 is 1 if n is 2 it’s 4 minus 1 is 3 and so on so we can extend that and there’s no rigorous strict way to to say how do I go from a set to a description like this it’s kind of a trial mirror thing it’s an experience it’s more straightforward to go from here to this than to go from here to this if you’re trying to define a set you need to find some sort of way of expressing it but if you’re given an expression like this you can just start writing the elements and see what the set is so what about about this is there anything in that set so that’s an empty set because to be an element of that set X it has to be bigger than 0 and less than zero and we know from our experience that there’s nothing to cochlear unless how about that set it’s a singleton set containing one element which is the number zero so we could write C equals but you don’t want to get overly excited and write something like that because that’s wrong this is saying Z is the number zero that’s not true but Z is a set consisting of one element which is zero that’s correct so sets are different from numbers even though they do contain numbers and so we have some steps that will encounter again and again this funny-looking end is called a set of natural numbers and this is integers bigger than or equal to zero this funny-looking Z is a set of all integers funny-looking Hugh is a set of all rational numbers so what’s a rational number it can be expressed as a ratio yes right that’s aight i do it as a Z I just put an extra line here on this bar if you use a good text processor there’s a built-in for it so a

rational number is a fraction something / something we each other some things is an integer so i can also write this as a set of all P over Q such that p is an integer these contained in the set of integers q is contained in the set of integers and I need one more requirement q naught equal to 0 so there’s a nice mathematical looking definition of rational numbers is that is that ok would be right that like depended to Z or we need to also show what is um the funny-looking Z will assume throughout his course main the set of integers I mean like as I’m exactly technology could it put in a set of good asset be indeed we depended on another stage absolutely yeah that could be some other set if you can find somewhere else to be a set of happy integers so q is the set of rational numbers funny r is a set of real numbers what’s an example of a non-rational number or an irrational number pi you can’t write by the fraction eating approximated 22 over 7 but you can’t write it exactly that’s square root of two play with that 142 too so yeah 1.41 for something something something and you can approximate it pretty easily with arbitrary accuracy but you can’t find an exact fraction that’s equal to square root of two and the Greeks discovered this and really keep them off Pythagoras was in some ways a cult leader he had a secret society of people who worshipped numbers and they worshipped integers in particular and they were fascinated with ratios of integers and they felt that through whole numbers or fractions of whole numbers they could represent anything they were almost godlike to these people and unfortunately somebody discovered that a simple triangle with length one on each side the length of this could not be written as a fraction and they proved this and this through a big monkey wrench in their beliefs because they thought that through whole numbers and ratios of whole numbers they could acquire all knowledge and suddenly they realized that couldn’t even represent the length of the simplest triangle with these fractions and that was forbidden knowledge for a while and one person actually like tried to tell some people about this and they took them out on a boat and they pushed him off and he swam back to shore he lived but um but this was this was a real cloud on their parade and this length turns out to be square root of two and it’s a pretty straight forward through the square root of two is not a rational number and we’ll look at that when we do proves a number theory but it’s a really weird with kind of elegant proof so there are things that are real numbers but that are not rational numbers when pi is 101 would even simple things like square root of two and c is a set of complex numbers so what’s a complex number rationals and irrational is give you the real real real real and unreal well imagine imaginary right so you throw in the square root of minus 1 which we can call I here because we’re not doing engineering you throw this in with the rails and you get the complexes so bigger and bigger and bigger sets every

integer is also rational and is also a real number and is also a complex number it just happens to have nothing after the decimal point no I component and nothing on the denominator these sets get bigger and bigger and bigger but there are numbers here that aren’t in here and so on so those are some of the symbols that will use so how else can we define sets so we can use what’s called interval notation for example we will sometimes want to use a set like the set of all X coming from the real numbers such that X is bigger than or equal to a and X is less than or equal to B so what does this said look like what sorts of things are in there a and B will definitely be in there because assuming that a less than b and b’s bigger than a lot of stuff in between a and B so think of a number line and let me go ahead and send a is less than B so we don’t be able to weird edge cases so on a number line a is sitting to the left of me so this set describes this point and this point and everything in between ok so it’s an interval it’s an interval starting at a ending it be and including the endpoints and we have a shorthand for that which is just a comma B inside square brackets and we call this a closed interval now we can also have a set of numbers coming from the reels which are strictly greater than a and strictly less than B how does that differ from our closed interval the unlimited AMD are not included but everything else is the same so here’s a here’s B and typically this is drawn with a little circle around a and B say those points aren’t included in this line but everything in between is and we have a shorthand for that which is a common baby with parenthesis instead of brackets and we call this an open interval and we can combine these and do things like half opener half closed intervals so this would include a would not be this would not include a one would include B and this is a pretty simple definition but it’s a really sophisticated concept because open and closed intervals are very different from each other and let me show you one way in which they differ what’s the largest number in this stage an interval is a set right it’s us a collection of real numbers what’s the largest number and that said what’s the

smallest number that said no problem what’s the largest number in this set there isn’t one you tell me it’s 1.99 I’ll find a number bigger if you tell me any number that’s in that set I’ll find a number bigger than that that’s a little weird isn’t it every number has some element that’s bigger than it does that happen in real life everybody in this room have someone who’s older than them I’m pretty sure I’m the oldest does everybody have someone who’s younger than them up on the set of people in this room yeah so with finite sets of numbers there’s always a biggest number with an infinite set of numbers sometimes there’s a biggest number sometimes there’s not and in the second example there’s no smallest number either you can get smaller and smaller no matter which number you pick and that’s a little freaky and we can actually derive calculus from these two notions you can do something called point set topology it’s an abstract version of calculus calculus is like points that topology apply to real numbers what we can do it more abstractly on general sets and open and closed intervals these get into notions of continuity and limit points and you can sort of branch off from there that’s a wonderful field alright so other ways to define sex interval notation open closed or partially open closed intervals equality of sets so when we write a equals B what do we mean by that precisely HP to Sonoma they each contain the same elements so i’m going to write that as follows x is contained in a if and only if x is contained in B from all possible objects pics so to say two sets or evil means that for any object I pick number says not member or said any object I can think of it’s contained in here if and only if it’s contained in here if and only if means if it contained in there is contained in here and if it’s contained in B is contained in a will use if and only if a lot so we have an abbreviation iff that means it we have and we have an abbreviation instead of saying for all X i can use what’s called the universal quantifier it’s an upside-down a it means for all so this would be the more classic way of writing what we mean by a will be so clearly those two are equal but these are not equal why those are equal an element is in here if and only if it’s also in here even though I’ve written this with three elements why are

these not equal to each other because the one of the week one on the Left does not have a three so there is a particular x3 which is contained in here but not contained in here wait so go to those ways it could be contained in here if it’s contained in here and that’s not the case you this is a set of all X which is an integer from Z who square is equal to 5 so what does this said look like is that an integer so is there anything in this set this is empty this is a set of all numbers q which are bigger than 10 and are an even prime number are there any even prime numbers bigger than 10 if you have an even number bigger than 10 is divisible by 2 it can’t be Prime so this is the empty set so this said in this set are equal to each other their descriptions are obviously very different from one another but as a set equality they’re equal make sense all right how many people here in the wind diagrams whoo and it was one of Google’s doodles within the past year to the birthday of then I think so that diagram is a way to describe sets that may have some relationship with each other so we can draw pictures to correspond with so for example this is called the universe this is the set of every object that you’re considering and for this example this is going to be a set of all foods all things that you canĂ­t each which I get into the rocks and dirt technically and I’m going to draw a set C which is a set of all cookies and theoretically every cookie is a food you can eat them so I’m drawing this as something inside in this larger object and I’m going to draw some other set H H is a set of all foods that have chocolate so candy bars and chocolate pudding and everything else is in the set age and so outside here we might have a member of this set which is a salad and over here we might have a member of the set which is a snickerdoodle we not know