20150922 Discrete Structures Set Theory

alright so any questions from yesterday we were just kind of getting started and I did an overview of kind of what the course includes all right so I wanted to mention the engineering computer science club meets here Friday’s twelve o’clock if you haven’t been to the club meetings before I highly recommend at least checking them out it’s it’s a group of students who just get together once a week and talk about or do whatever if you’re interested in working with people on projects or just sharing interesting ideas it’s a good place to do it sometimes they organize trips sometimes there’s talks that are given we had someone come in last year and talk about their work on building a space elevator so there with a company of north that’s actually trying to design an elevator that goes from here into space as an alternative to launching things with rockets and some people actually ended up doing some work with this company the result so it’s a cool opportunity for networking it’s a cool opportunity to just sort of listening to other people’s ideas sharing your ideas and so on I definitely come check it out if you’re interested so I want to start talking about set theory this is our first topic for the course and we said yesterday that must a tidge is the collection of things like an unordered collection of things so set is an unbored collection of objects sounds more scientific than things so for example those are Seth’s this is also a set it happens to be a collection of no objects but it’s called the empty set please stow a set collection of zero authors and sometimes we just use this symbol 0 with a slash through it to mean the empty set a set can also consist of just one thing and we call that a singleton set so this is a set consisting of no objects a singleton set is a set containing just one object and we can talk about the membership in a set for example a is a member this set B is also a member of us that X is not a member of that set so to be a member of a set means you’re one of the objects in that set and we have a shorthand for that which is this epsilon symbol and when you think of that as saying as a member of that saturday is contained in that set and if something is not contained in that set we can put a slash through it and say X is not a member of that and sets can be pretty much anything instead of integers instead of audience instead of prime numbers the set of rational numbers the set of irrational numbers a set of animals you can find at the Oregon Zoo a set of foods you can buy on campus with a leg table kind of except tables are usually ordered and

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

what snicker girls are great that Snickers in it no it doesn’t which is really weird but it has cream of tartar it’s one of the few cookies with FEMA tartar and foods with chocolate in them put em and I was in there if you’re taking nutrition don’t show these to your teacher and I’ve drawn these set representations so that they overlap why is that because there are things that are in both sets for example this might be chocolate chip cookie and it’s both a cookie and the food with chocolate and it’s a food that you can eat so as we start talking about subsets intersections of sex unions of sets compliments of sets will come back to Venn diagrams as a visual way of describing some of these things that we’re going to describe mathematically okay so it’s another tool for for visualizing some of these notations that we’re going to talk about we have ten minutes left those so before we start talking about subsets and intersections and things like that I want to back up a little and I wanted to toss something out for you to think about and I mentioned yesterday that set theory can be done in two ways there’s naive set theory and there’s what’s called axiomatic axiomatic sounds more technical right axioms we talked about them in geometry or maybe some other math courses axiomatic set theory is very rigorous we don’t use words like things and objects naive set theory is what we’re talking about and it’s what we’ll talk about in this this this week’s lectures but I want to show you what can happen if you follow naive set theory and you don’t go to the rigor of an axiomatic set theory so let’s continue thinking of sets as collections of objects and sets can be a collection of anything for example this is also a set this set contains three objects first object is number one the second object is the number to the third object is a set of prime numbers nothing wrong with that and we might think that this has an infinite number of things in it cuz there’s an infinite number of primes but this said itself s has three elements 12 and a set now this element itself to set of crimes that’s an infinite set has an infinite number of prime numbers and edgy but as itself three members but this can get us into trouble once we start having sites that contain other sets we’ve got to be a little careful so I want you to follow me on this this thought experiment so here’s a definition a set s is called self consuming if it’s a member of itself if it contains itself as one of its elements and I don’t have a self consuming set example I can put on the board because yeah it would be a recursive example here’s a stat it contains two elements this does not happen to be one of the elements right and if I wanted to include that that’s a perfectly fine set

but it’s still not self consuming because they would need this to be an element and it’s not the only elements or 12 and this set with two elements this does not contain a step with three elements so it’s hard to come up with an example of self consuming says I don’t know but that’s okay we’re not going to need to know whether it exists right because this is math right we can do what we want doesn’t matter if it’s absurd as long as it’s logical so we have a definition that may never apply to any set but if a set contains itself will call it’s all-consuming ok so I’m going to define a set W equals a set of all sets that are not self-consumed you and we know there’s at least one element in this satchel because we said this is not self consuming it doesn’t contain us whole so this would be contained in w and the integers would be contained in w and the primes and the set of animals at the zoo and there’s a lot of things in w it’s a really big set maybe it contains all sets i don’t know but this is our definition if a set is not self consuming it’s inside w clear on the definitions so question is w soft consuming set so we have two choices yes or no it’s a simple yes/no proposition so two possibilities one suppose we say yes W is self consuming what does that mean it means W contain itself but W only hold set behind the W only hold sets that are not self consuming so W cannot be a member of itself so this leads to a contradiction so the answer must have been no W is not self consuming which means W is not contained in w but if w is not self consuming it’s a member of the set but then w is contained in w contradiction so we’re doing either way if this statement is true we get a contradiction if this statement is false we get a contradiction so is it true or false so we’ve got the proof that it doesn’t it is it’s going to be to possibly but we don’t know yet fw itself is all-consuming if we could prove from this that there’s no such thing as all-consuming said then we’ve got our answer w is not self consuming but hoops we’ve got a contradiction anything that leads us to conclude that this is true or false forces us into a contradiction the only conclusion is that we cannot determine whether this is true or false it’s undecidable or perhaps it’s neither true nor false talk about raining on your parade so this was Russell’s paradox and it comes out of the fact that we were too generous in our definition of what is that was we let us that be anything and down here to say that it’s all sets allows it to possibly improve itself and that’s not kosher so when you do axiomatic set theory you have a more precise definition of these concepts and you can avoid the sorts of paradoxes but around the turn of the century 1900s people were thinking of sets as collections of objects and you came up with this and it’s like okay we got to

be a little more careful now this I think is part of what bonds Whitehead and Russell perhaps on to their principia mathematica where they tried to make everything rigorous in mathematics at 300 some pages later you can lay the foundation for one plus one equals two the bummer of it all came out in 1939 by a mathematician named Kurt guru who presented a very small paper at a pretty obscure conference and most of the attendees had already read this paper and said that’s cool he didn’t really understand what it was a few people did and they were horrified because what girdle showed was that this doesn’t just happen with set theory this happens with arithmetic this happens with all the mathematics anytime that you define a system of axioms to develop something like arithmetic you have two options you build in contradiction or you building things that you cannot prove or disprove things that are undecidable and it’s somehow systemic it’s somehow fundamental to any time we try to develop one of these axiomatic systems and it’s called girls incompleteness theorem and we’ll talk about it later on in the course and it ties into something called the halting problem which is an application of this basic concept to computer science and it’s a proof that there’s some programs you cannot write programs I cannot exist or should really annoy you don’t tell me I can’t write a program to do this but but there’s ways to prove this to some degree so that’s your paradox for the week tomorrow we’ll go back to closer to earth and we’ll start looking at operations we going to fly on Smith’s obsessed intersections unions complements and we’ll move from their in-house times in the digital logic and then we’ll go on to some other weird stuff again alright so tomorrow I look puggy prime numbers having a set number is fairly straightforward but that we can actually do before we can actually get to a page where say ok SS is to end a lot of what we are you in this class is group we assume something to get to a contradiction so assume there’s a finite number of primes we can get a contradiction so but things like this whichever way you make this is the movie that is it could also produce questions there kind of is there’s notion of undecidability which basically says you can’t prove your hand or more precisely whether you