okay so i have to admit this is extremely awkward lecturing to an empty room so i have to imagine there's somebody on the other end actually listening to me at some point um perhaps this is what youtube stars have to go through at some point in their career um so what is the purpose of this course so this is for 18 100 a real analysis so the purpose of this course is twofold the really i think the first primary purpose of this course is to gain experience with proofs so that means being able to read a proof being able to write a proof and second statement which or the second purpose which is supposed to be kind of a way to obtain the first purpose is to prove statements about the real numbers functions and limits so the second part this is the uh analysis part okay so for the first few lectures we're going to do um what maybe to some will be kind of review um and most and for most of you a lot of this material in the first few lectures will be review so but it's a nice way to ease into the material and things will most definitely pick up um after a few lectures so the first set of objects we're going to define and and try to prove some statements about are sets so definition and because i use a lot of shorthand i will mostly write dfn from now on instead of the entire word definition so a set is a collection of objects called elements or members okay now this course is supposed to be probably the first uh really rigorous course in math that many of you will deal with so essentially everything that we talk about will be rigorously and unambiguously defined but we do have to start somewhere and so maybe you think this word collection is a little ambiguous and perhaps you should um but to actually build up set theory from the ground up would take us quite beyond the scope of this class and too far afield of the things that we want to do or at least that what i want to do okay so a set is just a collection of objects called elements or members there is the simplest set to define the empty set is set with no elements and we denote it by this uh symbol here circle with a dash through it okay so with new math typically comes new notation new symbols that you use so let me introduce a few shorthand notations we'll use throughout the course i mean you know quite honestly this is a little bit of the fun of doing higher math you get all these funny symbols um and a very accomplished mathematician at the university of chicago one time said you're really only interested in the math where that has the symbols you like to write over and over again so some notation a and this symbol which looks like an e s means a is an element of s a with dash through this little e means everything here but so a is not an element of s this upside down a means for all shorthand for all backwards e means there exists and a couple more if you see an arrow like this this mean this means implies so i've written down one thing this implies the next statement i'll put an arrow between them and an arrow going both ways means if and only if meaning if i have a statement p if and only if q that means statement p implies q and statement q implies p all right and if you need a quick refresher on kind of uh basic logic you can find that in the appendix of the textbook okay so that's the basic definition of set empty set um so in set a another definition is that a is subset of b which we write a uh this little symbol that looks like a c b if every element in a is an element in b hey a little a's and capital a means uh little a is in capital b so two sets are equal we write a equals b if a is a subset of b and b is a subset of a okay and so and a is a proper subset of b if a is a subset of b and a does not equal b okay and we typically write that by a and with a dash going through a line underneath this c to signify that it's not equal so think of it as not uh so less than or equal to but not equal to is one way to think about it okay so let me say something since i'm now one two three definitions in so definitions are a fact of life when it comes to math in the beginning of any subject there's going to be a lot of definitions because we have to have objects we want to talk about and we have to have these unambiguously defined objects so um it may seem like there's going to be a lot of definitions now uh but this will let up and we will start proving some theorems which are facts about these objects these are the things that we're really after we're not really after just making up definitions definitions are meant to be a rigorous way of defining an object we're interested in studying we're interested in proving theorems facts about so again a lot of this is just probably review when we describe sets we will use these uh braces and maybe list the elements in here or we will describe it as x in some set a satisfying some property p of x or we won't write this x and a part we'll just write all objects x satisfying x as uh being an element of whatever universe we're in that satisfied property p of x okay so again this you should read this as all x satisfying property p of x so the basic examples and this is you should expect this after kind of seeing any kind of non-trivial definition if you were here i would ask you to call me out so i'll have to police myself but after every kind of semi-interesting definition you should see examples okay this is how you actually learn about these things um or at least digest what these things are so we have the natural numbers which everyone's familiar with since they started to count one two three four and so on we have the integers which is zero one minus one two minus two so all the natural numbers along with their additive inverses along with the zero element an additive identity we have rational numbers so this is written as m over n such that m and n are integers and n does not equal to zero and we have r the real numbers which i as of right now cannot actually write down what they are in terms of set builder set building notation um in fact this will be our first goal of the course is to give a proper description or definition of what r uh actually is um but you can think of this as so as you did in calculus as q along with so rationals and irrationals like pi 2 and these things so this is fine to think about for now um so of course i didn't have to use these i could have maybe i'm interested in odd numbers that's the set of numbers of the form 2m minus 1 where m is a natural number so this is just 1 3 5 and so on okay and so note that we have the inclusions natural numbers are contained in the integers which are contained in the rational numbers which are contained in the real numbers okay and you know if you kind of look at the history of why these things were thought up in the first place i mean they were thought up to solve uh you know kind of polynomial equations that you couldn't solve in the number system before integers were created because i could not solve the equation x plus 1 equals 0 in the natural numbers rationals were thought of because i could not solve the equation 2x plus 1 equals 0 and the integers and the real numbers were thought of because i cannot solve the equation x squared minus 2 equals 0 in the rational numbers now i can't solve the equation x squared plus 1 equals 0 in the real numbers which led to the creation of complex numbers but we will not deal with complex numbers in this class although hopefully if you keep studying analysis you get on you go on to complex analysis which is really a beautiful subject of study to this day so as i said um let me write this here our first goal real goal of the class and this is something to keep in mind we're not going to do it uh right now our first real goal is to describe what r is okay mean if we're gonna be proving uh statements about the real numbers functions of real numbers and limits whatever you know those limits that you learned in calculus then we have to be able to really describe what we're starting with the real numbers okay so let's get back to sets to our review of sets um so there were some examples we have a few more definitions the union of two sets a and b is the set which we write so this is how we denote it a u b this is the set of all elements x x is in a or x is in b the intersection of a and b so this was defining the union this was defining the intersection is to set a cat b and this is a set of all x's so that x is in a and x's and b so the union is take all the things from a take all the things from b and put them together in one big basket the intersection is just take the things that a and b have in common the uh set difference of a with respect to b is the set a backslash b this is the set of all elements in a such that x is not in b the complement of a is the set a so this is how i'm denoting the set uh kind of the next part is how i'm defining this set this is a set of all elements in our universe that is not in a and when i say universe i don't mean this universe necessarily i mean if we're looking at subsets of r the complement is you know resp generally with respect to r um or if all of our sets are subsets of q then our universe would be q the rationals and we're taking the complement in there two sets are disjoint if their intersection is empty okay so it took me quite a long time to figure out this complement has an e in the middle as opposed to an i as in the complement you would give a friend i had to do a lot of spell checking in my thesis when my advisor pointed that out so this is just something to keep in mind this complement has an e in the middle of it um okay so let me just kind of draw a quick picture so uh this blob over here is a this is a set b this is a set c in fact let's make this a little more okay let's keep see there then what i have here that's a intersect b um this bit over here with the lines going this way but not including this this is a take away b a backslash b and okay so that was not meant to be along the same direction as this one so let's go vertical and everything with a vertical line is a intersect b okay so a backslash has the lines going this direction a intersect has the lines going this direction a union b has the lines going vertical and c is way over here not touching any of a and b so a a and c are disjoint and b and c are destroyed okay they have nothing in common okay so this is a lot of definitions we have not proven a single statement yet so it's about time we do this is probably one of the most basic theorems one can prove at the start of a real analysis class or any class about proofs this is you know analogous to when you write your first hello world program in a programming class so let me state the theorem which is de morgan's laws and the statement is the following so if abc are sets then i have several things i can say the union of b and c taking their complement this is the intersection of the complements so the complement of the union is the intersection of the complements if i take their intersection and take the complement this is the union of the complement so the complement of the intersection is the union of the complements now these are complements meaning i in some sense taking a set difference with respect to the entire universe but i can make these things relative to some set a so a take away b union c this is the same as a take away b intersect a take away c really again this is you should think of this as a special case of one um or at least if you were to write the proof i'm not going to because it's all going to be contained in the first two then you would see it's really just the proof of this guy um a take away b intersect c equals a take away b union a take away c okay so again for a quick refresher about logic i would look at the appendix of the textbook in general so let me make a few remarks um before we move on to the proof about typically how this is going to look so this is some remarks typically a theorem is a statement of the type p implies q let me write this out in english if some statement p holds then q for us it's if i have any three sets then i have these equalities between these operations of sets uh so the general structure you'll see of the class is i have objects which i define unambiguously i want to prove theorems now meaning uh true statements about these objects and the real meat is the proof part so what is in this mysterious guy the proof it's quite simple you start with you assume p meaning what you're given the hypotheses or the hypothesis p and i'm going to put dots here through logic and most definitely most of the time some calculations you arrive at q is true and most proofs are ended with this little box here okay so most proofs have this structure i take my hypotheses and these hypotheses mean something in terms of the definitions i have given and now i need to use these uh unambiguous definitions along with logic and maybe some calculations to conclude that statement q is true that is the essence of a proof that is um all there is to it um now that doesn't mean it's a simple thing to learn how to do that's the point of this course but distill down that's what uh a proof is okay and q so i said p usually means something in terms of the definitions we have but also q will usually mean something in the definitions that we've given and so our job is to verify q so let's go with proving this theorem and in fact i'm only going to prove property one property two three and four i'll likely put on the homework so b and c be set so i mean this is the only hypothesis i get i'm trying to prove that uh b union c complement equals uh the intersection of the complements so what does that mean so we want to prove so this is it's quite helpful especially when you're first starting to do proofs to write down what you're actually trying to prove so even though i have this statement here it's an equality between two sets equality between two sets means something specifically right we have that in our definition uh where is it over there that two sets are equal if one is a subset of the other and vice versa so that's what we have to prove we have to prove that the left side b union c complement is a subset of b complement intersect c complement and vice versa so we want to prove that there's a subset of b and okay so that's what the equality means that's what we have to prove we have to prove those two statements now okay and that's as distilled down as far as we can go um so let's prove this now we'll prove this using uh again logic and what these things actually are so let's prove this first statement uh here so i have to show that every element in this set is an element of this set so i'll even write this down as wts that means want to show uh this is the first thing we'll show as we go on i'm not going to write as much as i'm doing right now but this is the first theorem and proof you're seeing so i should write down quite a bit so the first thing we want to show is we have this inclusion okay that means every element here is an element here so let x be in b union c complement and now we're going to trace what this means and we'll eventually arrive at x is in this so then x is not in b union c that's just the definition of uh the complement now x is not in b union c means x is not in b and x is not in c right because the union is something's in the union if it's in b or c so something's not in the union if it's not in b and not in c now this implies simply again by the definition of what it means to be in the complement x is in b complement and x's and c complement but this again is simply the definition of x being in b complement intersect c complement okay so you see we started off with an element in this guy and we showed that it's also an element of the right hand side so thus b union c complement is contained in b complement intersect c complement now we want to do this other inclusion here now this is one of those kind of rare situations where you get to essentially reverse the entire argument and get what you want so but let's just go through it in a linear fashion let's take something from here and show it's in here so let x be in the intersection of the complements then that means x is in b complement and x's in c complement that means x is not in b so that's this statement that's the definition of being in the complement and x is not in c that's again the definition of being in the complement now just like we used here in this step this is equivalent to so really i should in this statement i should have written this statement is equivalent to this statement but we'll remove that so x is not in b and x is not in c this means x is not in their union which implies that x is in the complement of the union okay so thus we've proven is the subset of b and since we've shown both sets are a subset of each other that means by the definition of two sets being equal they are equal again this box means really nothing it just means that's the end of the proof all right let's move over here this is terrible yeah not everybody uses that little box to finish or proof um some people don't put anything i was when i was in graduate school i was a ta for uh this guy named paul sally who was a fantastic teacher and really loved math who would end so amazing story about this guy is you know when i was his ta he was in his 70s i think but he had also had diabetes so he had lost both of his legs beneath his knees he was also legally blind and he had a patch over one eye so he himself often referred to himself as the pirate mathematician but he would end his proofs with at least in his textbook he didn't ask me to do this on the board thankfully he would end his proofs with a picture of himself with this cob pipe that he had very much in the pirate fashion anyways okay moving on from things that in proofs let's go on to uh next subject induction so induction is a way to prove theorems about natural numbers okay that's you know the theorem itself is um more of a tool rather than uh an interesting fact on its own okay so let me state the theorem and then we'll go over a couple examples on how to use induction so let me recall from i think i just erased it n is the natural numbers and it has an ordering meaning um so we'll precisely define what ordering means but just in your head this means the usual thing one is less than two is less than three is less than four um so a property of the natural numbers which we'll take as an axiom is the well ordering property so an axiom is not something you prove you assume this about the objects that you've defined or studying up to this point and so the statement is if i take a subset of natural numbers which is non-empty then s hat has a least element or smallest element now what does this mean let me write this write this last statement out i.e there exists an x and s st i will often write meaning such that or so that such that x is less than or equal to y for all y and s okay so every non uh empty subset of the natural numbers has a smallest element okay we're going to take that as an axiom as just a property of the natural numbers which we'll assume now using this axiom we're going to prove it's not really a you'll often hear it called as the principle of mathematical induction but this will state it as a theorem instead of a principle whatever a principle is supposed to be so induction so this is uh due to pascal or at least in the its first rigorous formulation is let p n be statement depending on natural number n okay so maybe we have some equality between two quantities that involves a natural number n okay that could be our statement p of n um now we're going to assume so what are our hypotheses about this uh statement what are what's our if assume that this statement satisfies two properties this first property is usually recall referred to as a base case that is that p of one is true and the second property is called the inductive step so this statement satisfies the following property that if you assume p of m is true then you can prove that p of n plus one is true so i have a statement which satisfies both of these uh properties okay in particular since i'm assuming p of one is true by the second property p of two is true and then again by the second property p of three is true and then p of four and then p of five and so if you follow that last line of reasoning this means you should kind of be able to guess what the conclusion of this theorem is then pn is true for all natural numbers okay all right so we're going to use the well ordering property of the natural numbers to prove this theorem about induction okay so we have our assumptions i'm not going to although i said you know over there let bc be sets i'm not going to rewrite the assumptions that we have about our statement p we're just going to start trying to prove um p of n is true for all n so let me write our conclusion slightly differently let s be the set of all natural numbers such that p of n is not true so what i want to show is that p of n is true for all n so that's equivalent to saying we want to show that s is empty okay set of natural numbers where p of n is not true this is empty this is equivalent to saying p and p of n is true for all n and the way we're going to do this is [Applause] um kind of another staple of mathematical proofs is trying to prove this by contradiction okay so what does that mean [Applause] make a few comments about what that means proof by contradiction okay so in a proof by contradiction so this is what i'm about to write down is not part of the proof this is commentary uh not to be included in the proof what does it mean to say we're going to prove s is equal to the empty set by contradiction we're going to assume that the statement we want to prove is false or are we not false but we want to assume that the uh negation of the statement we want to prove is true and then arrive at a false statement okay so we want to assume this is what we're going to do we're going to assume the negation of the statement we want to prove namely s is non-empty okay and from this we want to derive a false statement okay and so if we are to do if we were able to do that then let me just say again you can check in the appendix or you can just believe me that the rules of logic then say that that our initial assumption that s was not empty is false to begin with okay so rules of logic meaning i cannot start from a true assumption and derive in a logically consistent way a false statement okay um that is if we believe that the rules of logic we're using are uh consistent which that's a little bit hairy to talk about but you for our purposes of our class um you can believe me that the rules of logic we use or at least except that the rules of logic we're going to use are consistent and sound okay so back to the proof at hand we have this set of natural numbers where the statement is not true we want to show it is empty we're going to do it by contradiction meaning we're going to assume the negation of the statement we want to prove namely s is non-empty and we're going to derive a false statement from that assumption okay and by the rules of logic that means that our initial assumption that s is not empty is in fact false okay all right so towards the contradiction suppose that s is non-empty okay now we're going to use the well ordering property of the natural numbers by uh the well ordering property of the natural numbers s has a least element x okay now what do we know about x so first off x cannot be one okay s is a set where this property does not hold x cannot be one because let me again rewrite that this fact that s is the least element uh let me just reiterate that s has the least element in the set okay now x cannot be 1 because we're assuming the base case meaning p of 1 is true so since p 1 is true that means 1 is not an s which means x is not one particular x must be bigger than one so x is some magical natural number out there bigger than one that's the least element of this set s okay [Applause] since x is the least element of s so let me draw along the number line we have one two three four out there some magic point x which is the least element of s and the rest of the subset s lies to the right of this number x right because it's the least element of s and therefore x minus 1 cannot be an s so since x is the least element of s and x minus 1 is less than x this means that x minus 1 is not an s otherwise it would be a smaller element than x in s so thus what does it mean to not be an s it means that p of x minus 1 is true by the definition of s this means p of x minus 1 is true okay but by the second property we're assuming about our statement p this means that the next guy in line x minus 1 plus 1 is true which is just x which means that x is not an s okay so from the assumption so let me just uh recap from the assumption that s is non-empty we've derived two facts one x has a least element in s and that element is also not an s so written out we've concluded there exists a natural number which is both ns and not in this and this is a false statement you cannot have uh an object the member that's both in the set and not in the set okay and but at the end of contradiction arguments i'll usually put two arrows hitting each other so that's a contradiction therefore our initial assumption that s is non empty has to be false and therefore s is the empty set okay so i encourage you to kind of go through that proof a little slowly because maybe you got turned around by taking the compliments or or the general scheme of how proof by contradiction works but don't spend too much time on it because as i've said this theorem itself and its proof are not the thing we're really interested in or at least it's not the most interesting it's more of a tool that we'll use to prove more interesting statements okay so how do we actually use this theorem induction to prove other statements so i guess i should include this here you know this is falls under the umbrella of logic meaning we're going to approve previous we're going to use previous statements we've proven to prove new statements but anyway so so how do we use induction and practice so if we want to prove some statement for all n p n is true in the print then this theorem about induction this theorem of induction tells us we just have to do two things [Applause] okay we have to prove the base case and this is usually easy okay you just stick the number one into the statement that you want to prove and that's uh that's the end of the story and the second step is usually or the second thing we have to prove is the more involved part which is we have to prove that the statement that if pm is true then p of n plus 1 is true okay it's kind of if we want to do a proof by induction there's kind of two smaller proofs we have to do first we have to prove p of one is true and then we have to prove this statement if p of m then p of n plus one okay so again this is usually referred to as the base case this is the inductive step so let's try and actually do this all right so and so another question i get at the beginning of a course especially about proofs you know because there's a lot of uncertainty about what you can assume is true what can you use what can you not use right now at this point you can use whatever you know about any of the algebraic properties you know about the real numbers the comp the rational numbers and by algebraic properties i mean you know of a plus b equals c then a plus b times d equals c times d and what you know about um inequalities so we're going to go much more in depth into ordering which is what you know inequality uh is a part of but you can use all the properties you know about solving inequalities or manipulating inequalities meaning um if i have one number is less than or equal to another number then when i multiply both sides by a positive number that doesn't change the inequality so you can use all of these algebraic properties of rationals and real numbers from here on out there will be it i mean so we're going to be proving things about calculus so you certainly cannot use anything about continuity differentiation or anything like that but for now you can use all the algebraic properties you know so the first statement we're going to try and prove using induction is the statement that for all c not equal to 1 we're all in a natural number 1 plus c plus c squared plus c to the n equals 1 minus c to the n plus 1 over 1 minus c okay so this here is our statement p of n it depends on a natural number n okay so we're going to do this by induction which means we're going to do those two things we're going to prove the base case p of 1 which i said is easy and then we're going to prove the second case in the second property the inductive step which is a little more involved but not so much involved at least in the in the beginning so let me call this inequality star we're going to prove star by induction so first we will do the base case and like i said the base case is usually you just plug in n equals 1 and verify that p of n is true and that's what we do um 1 plus c to the 1 which is the left hand side does in fact equal one minus c to the one plus one over one minus c because this right hand side one minus c squared is one minus c times one plus c the one minus these cancel and so the base case is proven all right now we do the inductive step okay so we're going to assume that star holds for n equals m so we're going to assume p of m so assume that 1 plus c plus c to the m equals 1 minus c over 1 minus c okay now we want to show again let's write out what we want to do what's our plan i want to prove that this equality that this line star holds for n equals n plus one okay so again this is what i wrote here this is basically star for n equals m okay and let me call this second inequality the second equality two star so this is my assumption for m n equals m okay so let's take the left side for n equals n plus one and see if we cannot massage it to get the right hand side uh for i should say the right hand side for n equals n plus one so so here is the calculation part so we have one plus c plus c to the m plus c to the n plus one this is the m plus one case of the left hand side of star which we want to show is to the is equal to the n equals n plus one case of the right hand side now this is equal to now we already know what this is equal to by our assumption this is by the second star there which is what we're assuming is true this is equal to one minus c n plus one over one minus c plus c n plus one and so now we just do a little bit of algebra this is equal to 1 over 1 minus e n plus 1 plus c n plus 1 minus c n plus 2 over 1 minus c those cancel and i'm left with 1 minus c to the n plus 2 and i'll write it just so that you can see this is really the n plus 1 case all right so again we arrived at this first step by our assumption the second starred equation okay so the star holds for n equals n plus one so by induction or really i should say the theorem of induction that we proved our equality between those two objects or two expressions is valid for all n okay okay okay so let's do one more example of using induction so let's prove if c is a real number bigger than or equal to minus one then for all n natural number 1 plus c to the n is bigger than or equal to 1 plus n times c okay all right so we're going to do this by induction again that means we need to prove the base case and we need to do the inductive step so base case as always we'll so this is just right here we're going to do this by induction so as you can see the base case is again n equals 1 is clear just by looking at it 1 plus c to the 1 in fact equals 1 plus 1 times c so it's certainly bigger than or equal to 1 plus n times c so um i think that's the last stars i'll use for this uh lecture so our statement our inequality uh star star star holds for n equals 1. all right so that's our base case now we're going to assume that this inequality holds for n equals m and try to prove that it holds for n equals n plus one so we're assuming this when n equals m so 1 plus c to the m is bigger than or equal to 1 plus m times c and we want to prove this inequality with n equal to n plus one okay and we're just assuming um this guy okay so i want to get the statement for n equals n plus one one way to do that is this left side i want to get let's look at the n equals m plus one side and see what we can do with it so again this is a calculation part and logic so we have one plus c to the m plus one so that's the n equals n plus one side of uh this this is equal to one plus c times one plus c to the m now we're assuming again this inequality this is the n equals m case so we can use it so we're assuming it we use it this and since c is bigger than or equal to minus 1 1 plus c is non-negative so this thing is bigger than or equal to this thing so if i multiply both sides by 1 plus c i preserve the inequality so this is bigger than or equal to 1 plus m c okay again this just follows from essentially the assumption multiplied through by 1 plus c okay and now so now i'm gonna finagle this so let me just i'm not i'm not doing anything different here i'm just going to rewrite this over here so that i can have a chain of inequality so i have 1 plus c to the n plus 1 is greater than or equal to 1 plus c 1 plus m c all right so now this is bigger than or equal to this and this here so when i write it equal i do not mean that this left side is now equal to what i'm about to write here that means the previous thing on here is equal to what i'm about to write here okay this is a typical um fashion in writing down inequalities or i guess practice so this is equal to one so just doing the algebra n plus 1 times c plus m times c squared okay now this part is exactly the n equals n plus 1 side of this and i have a little room to give because now this is um plus something that's non-negative let me just rewrite this again this means that 1 plus c to the n plus 1 is greater than or equal to 1 plus so again i'm kind of writing a lot here i will stop writing as much as the course goes on um and but i encourage you especially in the beginning to write um you know all the steps in logic okay um so again i'm not rewriting anything i'm just summarizing what i've done here now this right hand side so i have this is bigger than or equal to this and this right hand side since i have a number plus something non-negative m times c squared m is a natural number this is bigger than or equal to uh 1 plus n plus 1 times c thus 1 plus c to the n plus 1 is greater than or equal to which is the n equals n plus one case so by induction this inequality triple star holds for all n all right