Transcription
[SQUEAKING] [RUSTLING] [CLICKING]
Zachary Abel: Thank you so much. Welcome to 6.1200, 6.120. I don't know how you want to pronounce it. Anything goes. Either way, welcome. Really looking forward to a great semester with all of you.
So a couple salient points, structure-wise, schedule-wise, we have lectures on Tuesday, Thursday, 2:30 to 4:00, which I suppose you know if you're here in person. We have recitations on Wednesdays and Fridays. We do take attendance at recitations. It's worth 10% of your grade. So we highly recommend that you go, both for your grade. And also, it's some of the most useful time that you'll have this semester. You'll be working with your peers to solve problems in small groups. You'll have a TA there to offer advice and suggestions. It's really valuable time, and I highly recommend you go. I guarantee you'll get a lot out of it.
Since it's such a valuable time and such a limited resource, just two hours per week, we have what we call warmup problems, which are just quick, multiple choice problems right there on Canvas, to get you thinking about the lecture material a little bit. They're not meant to be hard. They're not meant to be stressful. But we do want you to think about the problems a little bit and answer them and get the answers right. Getting the answer right is not as strenuous as it sounds. Because you get infinite retries and instant feedback up until the deadline. So as long as you remember to do it, you're going to get full points. You could, if you want, just option A, click. Nope, that's wrong. Option B, click. Nope, that's wrong. Option C-- we don't recommend that. Ideally, it's in your favor to actually think about the problem a little bit, might even be a little faster. But the point is to be a reminder to think about the lecture material a little bit before you come to recitation.
What we want to avoid is everyone shows up to recitation and says, wait, what are we covering today? I don't even know. I wasn't able to go to lecture. I don't know what was covered. Can someone fill me in? I would prefer that we do the catching up before recitation. So by the time we get there, we know what we're going to talk about. We can ask any questions we have. We can start working on the problems and use that time as productively as possible.
So that's recitations and warmups. We have problem sets. We'll have weekly problem sets, due on Monday nights. I hope everyone turned it in yesterday. They'll be released on Tuesdays. Oh, I got a thumbs up. Where did you send that? We release problem sets Tuesdays. They'll be due on Monday nights, 11:59 PM, so as Monday night as we can get. And I want to say a few words about these problem sets, about the structure and about the collaboration. We want you to collaborate. We want you to work with your peers. We want you to get help from us in office hours and on Piazza and things like that. We want you to solve these problem sets collaboratively, if you so choose. We are signed up for pset partners. So once a week, shortly after the problem sets go out, the pset partner site will match you with other problem set solvers that have similar schedules. So if you want to find a group that way, you're more than welcome to. We'll set it to go off a couple days after each problem set releases. So just be sure to sign up on time. If you miss the first round, you can sign up in the second round. Or you can come to office hours and find friends there. You can work with friends at your dorm. However you want to find partners, go ahead and do it, if you want. And we encourage you to solve these problems correctly-- or sorry, collaboratively-- also, correctly-- [LAUGHTER] --not the worst Freudian slip. We encourage you to solve collaboratively. Figure things out. Some of these problems are challenging. Some of them have tricks that you might not see immediately, and you have to figure out what's going on.
However, there's a second step to the problem set process that I want to call attention to. And that's the writing step. One of the main goals of this course, one of the main exports for this course, is proof writing, the ability to write precise, concise, correct mathematical arguments. And that is a skill that we will be practicing and developing all semester. And everyone has a slightly different style. Everyone thinks about these things differently. And the act of just constructing a proof, even if it all makes perfect sense in your head, the act of translating that into a proof on paper that's able to be read and consumed and believed by others is its own special skill. And we want you to get lots of practice with that, keyword being "you," not your group. So go ahead and solve the problems collaboratively. Whatever notes you've generated, that's fine. Keep them. Study from them. But when you're going to write your problem set, put those notes aside, please, and piece things together yourself in your words, showing your understanding. So solve together, write alone.
Just to emphasize this one more time, the reason I'm spending all this time belaboring this point is something I like to call the P versus NP fallacy, which just says that reading and understanding someone else's proof is easier than constructing that proof yourself. And it's really tempting to think that these two tasks are equivalent. When you're studying for a test, you read through our problem set solutions, like, yeah, that makes sense. That makes sense. That makes sense. Great. I'm convinced. That doesn't immediately translate to, I therefore could have put it together myself. So understanding a proof and writing a proof-- two different skills. We want you to get practice with both. Any questions about that, about the intent behind our collaboration policy?
Awesome. Let's see. Late problem sets, last thing I want to talk about, we do accept late problem sets. We accept very late problem sets. So we put a lot of effort into making these problem sets, at least trying to make these problem sets, both interesting and useful. And so we want to incentivize all of you to work the problem sets as much as you can in as many ways as you can, even if that means it's late. If the schedule doesn't line up, you had to miss some problem sets, we want you to be able to catch up by doing the problem sets. So we allow late problem sets up to and including the last day of classes. If you forget to do problem set one, and you remember, oh, in the last week, maybe I should go back and solve those problems-- probably would have been more useful to do it before the first quiz, but better late than never. You can still turn in that problem set late for half credit. More precisely, our late problem set policy is that for the first 50 hours, the late penalty or the percentage of points that you will earn from your submission goes from 100%, if it's on time, down to 50%, if it's 50 hours late, and 1% each hour for those first 50 hours, those first two-ish days. And then after that, it stays at 50 for the rest of term. That also means that if it's 11:45, and you have one problem left-- you know how to do it. You just down to the wire for writing it down. Or you want to take another hour or 30 minutes or something to think about that problem. Go ahead and be a little late. It's not a big deal. If you're one hour late, you're still going to get 99% of the points that you would have otherwise. It's worth it to take that extra time. It means that there isn't a sharp cutoff between before the deadline and after the deadline. It's not a big deal. Don't worry about it. We want to reduce stress for everyone involved. Any questions about that?
Excellent. All right. Like I said, lots more details there on the course information policies PDF on our Canvas site. And with that, let's talk about some math. So as I said earlier, one of the main skills and tools that we want you to have, coming out of this class, is the ability to write proofs, and read proofs, and evaluate proofs. As one of my colleagues says, this class could have been called Proofs, Proofs, and More Proofs. We're going to talk about proofs a lot, especially today, where we're going to start with, what is a proof? And I'm going to write that down because it's important enough. What is a proof? And I'm going to give a starting answer. And we're going to elaborate on this a little bit. Here's a question and answer. It's a method of ascertaining truth. A proof is how you show that something is true. And we as a society have lots and lots of methods for determining what's true. I'm going to give you a couple. For example, we have experiments, and observation, and the scientific method. That is how we determine what's true in the physical sciences. We have sampling. If you want to know who's likely to win an election, you pick a random sample, and you ask who they're going to vote for. And you generalize. We have legal proceedings. You hold a trial-- two different L's-- who knew? You hold a trial to determine what happened and who's culpable. That is how we determine truth in those cases. Who can give me some others? How do we determine truth?
Yes?
STUDENT: The investigation, like in detective movies.
Zachary Abel: All right, yeah investigation, absolutely, investigation, looking for evidence, looking for the most likely explanation that fits the observation, so actually, pretty similar to some of the other ones.
Yes?
STUDENT: Asking questions?
Zachary Abel: Asking questions? Absolutely. Cool. Let me give you a couple more. Authority. If your professor says this is true, then it's true, right? [LAUGHTER] Please don't do that. We make mistakes all the time, and we want you to call us out on that. We have religion. This is what our religion says. This is what our deity says. Therefore, it is true, and it is how I should live my life. These are the values I should value. We have inner conviction. I just feel like it should be this way. Deep in my gut, I know it's true. It came to me in a dream. Sometimes, that is how things work; so lots of different ways of determining truth, lots of different meanings of the word truth in those situations. And as mathematicians, we have our own procedures for determining truth. And that is a mathematical proof.
So definition, a mathematical proof is a verification of a proposition by a chain of logical deductions from a base set of axioms. A mathematical proof is a verification of a proposition by a chain of logical deductions from a base set of axioms. And there are three terms inside of that definition that we're going to focus on today and tomorrow. We'll break them down one at a time and hopefully, make this make more sense. Let's start with proposition. What is a proposition? Definition-- a proposition is a statement that is true or false. Today is Tuesday. Proposition?
STUDENT: Yeah.
Zachary Abel: Oh, that is true, yeah. Today is Thursday. Proposition?
STUDENT: Yeah.
Zachary Abel: Yeah. It's false, but it's still a proposition. Let's see, examples-- 2 plus 3 equals 5. Yeah, proposition. 2 plus 3 equals 4, still a proposition. Here's one. For all n in the natural numbers, n squared plus n plus 41 is prime. This is new notation. Let's break it down. This says, for all. So for every n that is in the natural numbers, this, what's called, blackboard bold capital N is the natural numbers, also known as the set 0, 1, 2, 3 and all the way up. It starts at 0, starts counting upwards. Outside of this class, you might see people trying to convince you that 0 is not a natural number. They're wrong. At least for the purposes of this class, 0 is always a natural number. So every natural number for every natural number n, n squared plus n plus 41 is prime. Is this a proposition? Yeah, it's a statement where it at least makes sense to ask, is this true or false?
There's a related concept, by the way. So this thing in here, just n squared plus n plus 41 is prime, is that a proposition? Let me give an even easier example. Oh, my examples were already on that board. Sorry. Even easier example, p is prime. Is that a proposition? I'm seeing some thumbs down. I'm seeing some thumbs down. Yeah, it's not a proposition, not a proposition. Because it's incomplete information. What p are we talking about? If you tell me a p is 7 prime, that's a proposition; is 12 prime, that's a proposition. So this is sort of a proposition with a variable that we need to fill in before it becomes a proposition. This is what's called a predicate. This is a predicate. And I was bringing back the old board so I could write down that definition. A predicate is a proposition whose truth depends on variables. So it's a parametrized proposition. Once you tell me what the variables are, then it's a proposition. And we just saw an example up here. I hope no one's getting dizzy from all the boards moving around. We just saw an example here, where this inside is a predicate that depends on n. And this for all is able to take that predicate depending on n and wrap it up into what is now a proposition. It says that this predicate about n needs to be true for every natural number. And now it's a proposition. It's either true or false. Is it true or false? Let's see if we can figure it out. We know it's a proposition. But is it true? Is it false? Well, let's do the natural thing and try some examples. OK, well, here's n. Here's n squared plus n plus 41. Is it prime? Great. So natural numbers, remember, start at 0. So when n is 0, this is 41-- absolutely prime. When n is 1, this is 43, still prime. Looking good so far. How about 2? I think we get 47, also prime. And if you check 3, 4, 5, 6, prime, prime, prime, prime. It keeps being prime. What if we go all the way up to 39? We get 1,601, if my notes are to be believed, which is also prime. This is looking pretty convincing, right? There we go. And in some fields of study, just doing a sufficient number of examples would be enough evidence for it to be true, or effectively true, or as good as true. Unfortunately, for us mathematicians, if we say for all n, we need all of the n. Just these 40 examples isn't enough. And of course, if you go one more-- did I write this down? Oh, here. Let's jump to 41. 41 looks a good example because that's going to be a multiple of 41, multiple of 41, multiple of 41. It turns out, what you get is 41 times 43, which is not prime. And so we found an example where this is not prime. And therefore, this proposition is false. If it's supposed to be true for every natural number, to disprove it, all we need to find is a single counterexample, a single number n that doesn't satisfy the required conditions. Does that make sense? Cool. Turns out, if you go to 40, I'm pretty sure you get 41 squared, which is also not prime. So 0 through 39 are really the most you're going to get in that run.
Let's look at another example of a fun proposition, just to get more familiar with this. Let's see Goldbach's Conjecture. Let's see. Every even number greater than 2 is the sum of two primes. Every even number greater than 2 is the sum of two primes. For example, can we do 12? Who can tell me? Let's see.
Yes?
STUDENT: 7 plus 5.
Zachary Abel: 7 plus 5, excellent. 7 plus 5, prime plus prime, so 12 is a sum of two primes. The claim is that every even number starting at 4 can be written as the sum of two primes. And it's called a conjecture because we don't know if it's true. I love, in math, and often, especially in number theory, you can state these very simply stated conjectures, theorems, questions, that are just beyond human understanding. They're beyond the scope of what modern mathematical tools are able to tackle. And it's really pretty, that right here is beyond the cutting edge of math. We've already gotten their first lecture, yeah, really pretty problem. And in fact, in, I think, 1995, it was highlighted in The Globe as one of the biggest unknown questions in math, right here, Goldbach's Conjecture. For example, 20 can be expressed as 9 plus 11. Oops, 9 isn't prime. So have we disproven Goldbach's conjecture? No. Why not?
Yes?
Yeah, it's 17 plus 3. 20 is 17 plus 3; so really pretty question, wish the reporting had been better. But we can forgive them. Are there any questions about propositions and predicates so far?
Yes?
STUDENT: The p is prime, which is not a proposition. And define predicate as a proposition?
Zachary Abel: Yeah, that's a very good point. That wording is maybe not great-- is a proposition that depends on variables except that-- it depends on variables. It becomes a proposition after you give values to the variables. Yeah, I agree we should fix that for the next go around.
All right. Now that we have propositions and predicates, really useful thing is to be able to combine them into bigger and more complicated and new propositions and predicates. And we have a couple, what are called. Boolean operators, that help us do that. For example, if A and B are propositions, propositions, we have what's called not A. This is a new proposition. It's sometimes written instead as A with a bar on top. It's sometimes also written as that weird right angle symbol next to the A. These all mean the same thing. They're just different notations for the same thing. And this is just the proposition that A is false. A is false. So you read it as not A. And it means A is false. We can clarify this with what's called a truth table. So here's A. And A is a proposition, which means there are really only two possibilities. It's either true or it's false. And so let's write down both of those options. It can be either true or false. And then we can look at not A and ask, what is not A when A is true? Well not A is supposed to flip it, so not A is false. And when A is false, not A is true. So this truth table can be taken as the definition of not, so truth table. And let's do some more interesting truth tables. Let's use two propositions now. If we have A and B, well, then there are four possibilities. They might both be true. A might be true, and B is false, or false and true or false and false. And our truth table is supposed to cover all the possibilities. So we're going to have four rows this time. And let's look at A and B. This is a new operator. And it means what you think it means because it's also an English word. A and B means that both A and B are supposed to be true. So if A and B are both true, then A and B is true. Otherwise, it's false. A and B means both A and B have to be true. Likewise, we have A or B, which means at least one of A and B has to be true. So if they're both true, that's fine. If only A is true, that's fine. If only B is true, that's fine. The only way for this to fail is if both A and B are false. So I want to emphasize this is an inclusive OR. It's fine if both of them are true. It just means that at least one of them has to be true. Notation-wise, A and B is also sometimes denoted A and this little wedge symbol, B. You can remember it because that looks kind of like a capital A for And, but you don't put the cross in. But honestly, if we're looking for clarity, I think that's a lot clearer, especially because A or B is also often denoted with the same symbol upside down. And I don't have a clever mnemonic for that one. So if you're trying to remember which one to use, just use these. That's my advice.
But back to this OR, I said this is an inclusive OR. So it's totally fine if A and B are both true. In English, that's not always what we mean. "And," "or," "not," these are words in spoken English as well. And when we're talking about math, when we're using these words in a math formula, we mean exactly what's written here. But when we use these words in English, we don't always mean that. Spoken colloquial English or other spoken languages are imprecise and context-dependent. And that really makes it difficult to communicate precise things, especially given the fact that as humans, we communicate math using spoken language. We're trying to communicate precise things with an imprecise channel, with an imprecise language. So as an example of how bad this can get, let's look at this word "or." Say you're at a nice wedding. The waiter comes around and says, did you order the chicken or the pasta? And when the waiter asks this question, they're trying to communicate some set of allowable responses. So are you allowed to say, I ordered the chicken, just the chicken? Yeah, seems reasonable. Pasta, you can say I ordered the pasta. Can you say I ordered both? Probably not. The catering company got all the RSVP cards in advance. And everyone was told to pick just one. So they did. So if you tell the waiter you picked both, first of all, you're lying. Second of all, stop trying to make their jobs harder. It's hard enough. They have hundreds of people to serve. So you're probably not expected to say that one. Likewise, you're probably not expected to say neither. I mean, I could go back and forth on that one. But let's say everyone filled out the RSVP card correctly, and so the waiter isn't expecting a Neither. So here, chicken or pasta, they were allowing this response and this response, but not these other two responses. This is not how we defined "or" in a math sense. This is what's called exclusive OR. You have to pick one or the other, but not both and not neither. So this is what mathematicians would call XOR, for exclusive OR. So after dinner, the waiter comes around again and says, you can have coffee or tea. Excellent. What responses are they expecting this time? Can you say just coffee? Yeah. Can you say, I want tea? Yeah, absolutely. Can you say I want both? Waiter is going to look at you side-eyed and say, there's only one mug in front of you, and I am not mixing them. This is a fancy venue. So, no, they're probably not expecting an answer of both. Can you say neither? I don't want coffee or tea. Yeah, that's fine. Not everyone wants a hot drink. Even at a fancy restaurant, not everyone wants-- a fancy wedding-- I apologize. Not everyone wants a hot drink after dinner. So now you can ask for coffee or tea or neither, but not both. Surely, that's how we defined OR in a math sense, right? No. These two are swapped. This isn't OR. This is what mathematicians call NAND. It's the Not of the And, NAND. Well, waiter used the word "or" twice. Let's try one more. Maybe they'll get it right this time. You ask for the coffee, and they say you can have cream or sugar. Can you ask for cream? Yeah, absolutely. Can you ask for sugar, just sugar? Yeah. Can you ask for both? Yeah, some people like a really sweet and creamy drink, both. Can you ask for neither? Yeah, some people like black, bitter coffee, inexplicably. So all four of these options are valid. This use of the word "or" also doesn't mean what mathematicians mean by the word "or." This one means anything goes. I'm just telling you what your options are. I don't have a math term for that.
STUDENT: True.
Zachary Abel: True, yes. So three uses of the word "or," none of them mean what "or" means. Isn't language fun? The moral here is, first of all, when you see these in an actual formula with other predicates and quantifiers and whatnot, we mean exactly what's written here. If we use it in a sentence, ideally, we also mean what's written here. But we might mess up, as well, and slip into colloquial, context-dependent English. And if you're ever confused, ask. If you're right, And. We messed up the wording, we will thank you and fix it if you're wrong, and we meant what we wrote, well, now you have confidence that that is what we meant to write. And both parties are happier because of it. So please ask for clarity if you're ever unsure of the wording we use, whether it's these specific words or anything else. Any questions?
Wonderful. Let's look at one other operator. We've looked at AND and OR and NOT. XOR and NAND, I mean, they're there. They're less important. I would master those three first. I want to look at one more that's really important, both for this class and for proof writing. And that is Implies, implication. We're going to write it as A implies B. Sometimes, you'll see it written as A arrow B or A double arrow B. There's no difference. These are all notations for the same thing for this concept of implication. A implies B And when read aloud, I recommend reading it as A implies B, or equivalently, if A, then B. If A, then B. This is already starting to look like a programming language. And IF statements in programming languages are exactly doing what implication in math is doing. So let's talk about what that is. As before, we can figure out what these terms mean by drawing the truth table. So we have A and B, true, true, false, false, true, false, true, false. A implies B. If A and B are both true, does A imply B? Yeah, seems pretty intuitive, yeah. If A and B are both false, if false, then false, again, seems OK to me. If A is true, and B is false, if true, then false, does that sound good to you? I saw a couple head shakes, a couple nods, more head shakes, though. Yeah, if true, then false. That's kind of the whole purpose of this wording. If A is true, then B is true. So if A is true, then B better be true. And if it's false, we're sad. Last case, if A is false and B is true, should this be true or false? Think about it for a second. And let's take a poll. Who thinks False Implies True should be true? Raise your hand. Who thinks False Implies True Should. Be false? Raise your hand. Who just wants the answer and doesn't want to think about it? Raise both hands. OK, the both hands win. It was about an even split. This answer is not so intuitive in this abstract setting. If A then B, well, what does it mean? What do we want it to mean? I claim, However, this-- what?
STUDENT: Last line.
Zachary Abel: Last line-- oh, yeah, sorry. Thank you. This should be true. Thank you. See, I do make mistakes. It's not so clear, but I claim this is a task that you are all familiar with in a different context, in many different contexts. So let's make it concrete. Let's pick an example. Let's see. On Wednesdays, we wear pink. Said differently, if it's Wednesday, then wear pink. Wednesday implies pink. Wednesday implies pink. Now it's an implication. And let's go through the cases and see what's happening. So if it's Wednesday, and I'm wearing pink, am I obeying the rule or violating it? On Wednesdays we wear pink. Yeah, I'm doing what it says. On Wednesdays, we wear pink. Great. So that one's fine. If it's Tuesday, and I'm wearing that color, whatever it is, and not pink-- let's hide this- if it's not Wednesday, and I'm not wearing pink, am I obeying the rule or violating it? Yeah, I'm obeying that rule. That's fine. If it's Wednesday, and I'm wearing blue, am I obeying the rule or violating it? I'm violating it. On Wednesdays, we wear pink. I'm supposed to wear pink. And if I'm not wearing pink on a Wednesday, I'm not doing what the rule says. And now we get to the confusing case. If it's Tuesday, not Wednesday, and I am wearing pink, Am I obeying the rule or violating it? Thumbs up. Anyone think I'm violating it? No. In this way, in this concrete setting, it makes total sense that on Wednesdays we wear pink. On all other days, I don't care. Anything goes. I only have an opinion on what you're wearing on Wednesday. So we're going to define this to be true. False implies true is true. As I said, confusing in an abstract setting makes more sense if you think about it as obeying a certain rule. If it's Wednesday, you have to do something specific. If it's not Wednesday, anything is fine.
Yes, question?
STUDENT: So with the example of, say, if it's Wednesday, and you're wearing-- you're violating the rule, what if you're wearing pink as well?
Zachary Abel: Yeah, good question. What if it's Wednesday, and you're wearing blue? So that's what we called the true and false case. But what if you're wearing blue and pink? Yeah. That was a less precise phrasing on my part. I should have said, you're wearing only blue. I assume if you're wearing pink and some other colors, I think that is OK here. I don't know. I'd have to watch the movie again. Anyway, implication is confusing. Let's talk a little bit more about implication. In English, when we say A implies B, often there's a connotation of causality. A causes B. And often, there's a connotation of time. A happens, and then after that, B happens because of A. So B is after is a consequence. And neither of those is what we mean. There's no causality. There's no time. How do you put a time on Goldbach's Conjecture. When it was conjecture maybe. But that's not what we mean. When we say Goldbach's Conjecture implies that I'm wearing pink on a Wednesday. As mathematicians, when we say the word "implies," we mean this truth table and only this truth table. There's no additional connotation. There's no causality. There's nothing else. It's just this truth table. Does that make sense? It can be hard to flip that switch and redefine this term that we're familiar with from somewhere else. Because it does mean something different now. It means that. And if you see this in class, even if it's written in a paragraph, you should assume we mean that first. Was that your question? Please?
STUDENT: So [INAUDIBLE].
Zachary Abel: So clarification on the concept of time, if A then B, do we need to know whether A is true or not before we decide about B? I would recommend thinking about and B as two separate propositions. They each have their own truth value. A is either true or false. B is either true or false. We don't necessarily know what they are, now or in the future. But they're still propositions. A might be the Goldbach Conjecture, where we don't know if it's true or false. But it's still a proposition. It's still going to be true or false. We just don't know yet. Likewise, we can always combine propositions A and B into this bigger proposition, if A, then B. A implies B. It's just a new proposition where once we know whether A and B are true, we'll know whether the implication is true. Does that make sense? Cool.
Let's see. So another example of implication, you might be familiar with less than 3. This is a preemoji heart, means I love you. Got some chuckles. I don't know why. I'm showing my age maybe. So less than 3 means I love you. What I have seen, I have seen occasionally less than 4 as an intensifier, like I really love you. I love you more than 3, I love you 4. And this irks me. I hate this, not because I'm against love, but because this is the stronger mathematical statement. Less than 3 implies less than 4. If we know x is less than 3, some number x, well, then we know that x is less than 4. And in fact, we know more information than that. We know it's not pi. Right? So this implies that. So this is the stronger statement. So you've weakened it. You love me less. [LAUGHTER] It should be less than 2, or something. But only mathematicians would get that. So I don't actually recommend sending that to your Valentine. But that's always bothered me. Let's do one other quick example. Who's familiar with Descartes, I think, therefore I am? Excellent. So, I think, therefore I am. I think, therefore I am. And this one has two claims to it. It's not only saying that thinking implies am-ing. But it's also saying that I think. So it's asserting that T is true, and T implies am. Yeah? So that's Descartes. What I have seen that bothers me is a shirt and a pillow and a meme. And you can go off and buy all of this. I don't recommend giving it money. "I do not think, therefore I do not am," which I find hilarious, but also frustrating. So "I do not think" implies "I do not am." So it's also claiming I don't think. I don't have an opinion on that. But it's saying this implication, not thinking implies, not am-ing. And it irks me because that's not equivalent. It's not equivalent to Descartes. Let's go out on a limb here, and let's assume-- big ask, I know. Let's assume that my shoe doesn't think, my right shoe specifically. But it still exists, let's assume. If my shoe thinks and doesn't-- sorry, doesn't think, but still exists, Descartes is fine with that. False implies true is fine. But the meme isn't. Not thinking is supposed to imply not am-ing. But my shoe ams even if it doesn't think. So these two statements are not equivalent. It should be, I do not am. Therefore, I do not think. Which gets zero hits on Google. We need to fix this.
Question?
STUDENT: Looking at the truth table, right implementation has certain [INAUDIBLE]
Zachary Abel: Ooh. All right, that's a great comment. Let's see. Let's go back to the front. What your colleague suggested was we can write A implies B by combining the earlier operators. Oops. A implies B is equivalent to-- and can you remind me what you said?
STUDENT: It was B or NOT A and NOT B.
Zachary Abel: OK, B or Not A and Not B-- and the claim is that this is equivalent to A implies B, has the same truth table as A implies B. In fact, if you check it, we can simplify it even further. We don't need this extra clause on B. B or not A. This is equivalent to A implies B. What this is really saying is that the only way to violate this, the only way to violate A implies B, is for A to be true and B to be false. And so if either of these is true, then you're fine. Yeah, absolutely, there are relationships between these operators, really nice observation. But going back to Descartes for just a second, we looked at a implies B and we also looked at not a implies B. Let's look at some others. B implies A. Not B implies Not A. If this is our statement, A implies B, if we flip them around, B implies A, that's called the converse. That's the converse of the original statement. And this one here, Not B implies Not A, that's what's called the contrapositive. And the one we saw over there with Not A implies Not B, that's called the inverse. You don't really need to know all of these terms. It's just nice to know they're there. Because A implies B is equivalent to one of these two. And it's not the nice one. A implies B is equivalent to its contrapositive. Not B implies not A Wednesday implies pink. So if you're not wearing pink, it better not be Wednesday. A implies B. Not B implies Not A. So these two are equivalent. And also, the converse and the inverse are equivalent for the same reason. They're contrapositives of each other. So that Descartes meme was using the inverse, when they probably meant to use the contrapositive, I assume, because I assume they thought that deeply about it. That is everything I wanted to say about implication. Does anyone have more questions before we move on?
All right. Now, very briefly, I've mentioned sets a few times. And I've used set notation a few times. So let's go ahead and make that more precise. Because we're going to be talking about sets all term, I just want us to have that common language to fall back on. So a set is a collection of objects. I'm not going to be more precise than this. If you want to dig into set theory, into the foundations of mathematics, it's really interesting. There's a lot of stuff there. But that's not what we're doing in this course. A set is a collection of objects. Let me give lots of examples. An example is the set that contains 6, 1, 2, and 0. And we're going to write sets with these curly braces. Crucially, when we're talking about a set, the order doesn't matter. And there's no such thing as a repeat. All I care about is, which things are in your set and which ones aren't? So this set is exactly equal to 2160 because they have the same four elements. This set is exactly equal to 6-- yeah, 6, 1, 2, 0, 0. It's kind of weird to write 0 in there twice, but technically, it's OK. I don't recommend doing that. But this has the four numbers 0, 1, 2, and 6 in it. And so these other sets, they're exactly the same set. We already saw, N, the natural numbers, this is the set 0, 1, 2, 3, and so on, all the way up. We also have the set-- that's a Blackboard bold z, which includes the integers, natural numbers, and their negatives, 1 and minus 1 and 2 and minus 2, and so on, all the integers, integers. A couple more useful ones, we have Q is the set of rationals, so fractions you can get by dividing some integer by some non-zero integer. We have the real numbers. That's a bold R. Blackboard bold R. And we also have C, the complex numbers, complex numbers. So those are five sets that we will very frequently talk about.
Let's give some more examples of sets. There's the empty set, Which? Is written as a circle with a through it. It's also sometimes written as an open curly brace and a closed curly brace with nothing inside. These two mean the same thing. They're just different notations for the same thing. The empty set is a set that contains nothing. It is a set. It is a thing. It does exist. It just has zero elements. Whereas, this set over here has four elements. This set over here has infinitely many elements. These other sets have infinitely many elements as well. But is it the same infinity? No, not always. And that's a confusing thing. Come ask me if you're curious. Let's see, one other set I wanted to give an example of. Let's call this one A, just so we have a name for it. Let's define B is-- what did I want to write? Yeah, 2, 3, 4, and empty. set. B is a set with three elements. It has the number 2 as an element. It has this set as an element. And it has the empty set as an element. Is 3 an element of / We would write this as 3 is an element of B. There's that notation again. Is three an element of B? No it's inside one of the elements of B, but it's not one of the elements itself, so no. So we have this notation. Oh no, I just used that. Let's move over here. Eraser, help. Found it. We have this notion of being an element a set that we have already talked about a few times. You can also ask a set to be a subset of another one. So x in A means x is an element of A. A and then this new symbol-- this is a sideways-- or this is a curly C with a line underneath it. A is a subset or equal to B. A is a subset or equal to B. Note the similarity of two A's. Less than or equal to B, less equal doesn't really make sense for sets, but this one does. Subset means everything that's in A is also in B. And B might contain more besides. For example, the set that contains 2 and 1, is that a subset of A? A was over there. Yeah, everything that's in here is also in here-- totally fine. Let's see. Is the empty set a subset of A? Cool. All right, I got some thumbs up. I got no thumbs down. I got a lot of blank faces. I'm going to assume that means Yes. Yeah, everything that's an element of the empty set should also be an element of A. Well, it's kind of weird, right? Because there are no elements of the empty set. And we can't really check this rule for any elements of the left. So it kind of feels like this shouldn't be true, because there's nothing to instantiate. There are no elements here to talk about. But a better way to think of it is prove me wrong. Show me an element on the left that isn't an element on the right. You can't. You can't violate the rule, and therefore, the rule is satisfied. A little bit confusing, but when you look at it the right way, hopefully it makes sense.
Just like we were able to combine propositions- A and B, A or B-- we can combine sets. We can look at A union B-- this is the union-- which is the set of elements that are in A or B or both. So in this case, A union B for our example, it certainly includes 6 and 1 and 2 and 0. And also-- well, it already has 2, so we don't need to write that again. And it has the set 3, 4, and it has the empty set, so everything in A or B or both. And remember, I don't have to say, the Or Both because OR is inclusive by default. We can likewise do a intersect B, which is the elements that are in both, so the intersection. In this case, A intersect B is-- well, what's in both A and B? I think it's just the two. There's a 2 in both, and nothing else is in common. So that's going to be just the set containing 2. There's also the set difference, A minus B, sometimes written as A backslash B. And that's the set difference. It's the things in A that aren't in B. So it's A, but take away everything in B. So in this case, it's going to equal 6 and 1 and not the two, but we still keep the 0.
Yes?
STUDENT: So that set is-- we basically [INAUDIBLE] the subset of everything, right?
Zachary Abel: Yep.
STUDENT: So [INAUDIBLE] also both in A and B and [INAUDIBLE]?
Zachary Abel: Good question. So the question was, we've already said that the empty set is a subset of everything. So shouldn't it be in both A and B and therefore, in their intersection? Really good question. And the difference is that we have two different meanings of "in." We said that the empty set is a subset of everything, but not an element of everything. So the empty set is an element of B because it was written as one of the elements. But it's not an element of A, because these are all four elements of A. There's nothing else in there. So A is a subset-- sorry, the empty set is a subset of A and a subset of B. But it's not an element of both. Great question. Thank you for asking.
Yes?
STUDENT: Why does A have two zeros if there's no repeats?
Zachary Abel: Why can A have two zeros if there's no repeats? Good question. It's because it doesn't actually have two zeros. I just wrote the two zeros. Each of them says, 0 is an element of this set. By the way, did you forget? 0 is an element of the set. So it doesn't have two. There's no way for it to remember it has two. But sometimes, in some weird cases, it might make sense to write a set where the same element is written twice. And so there's that example.
Yes, question?
STUDENT: Can you have A [INAUDIBLE]?
Zachary Abel: That's a great question. So if A also had a 3 and 4 in it-- so let's pretend this also has a 3 and 4 in it. And then we ask about A minus B. We take away from A everything that's in B, everything that's an element of B. So would we be removing the 3 and 4? So if we have a 6 and 1 and a 2 and a 0 and a 3 and 4, and we subtract the set-- what was it? 2 and 3, 4, and empty set. And the answer is no, the 3 and 4 don't go away. Because we want to take all the elements of the first set that are not elements of the second set. And 3 and 4 are not elements of the second set. They're nested too deep. 3 Is not an element of this set. This whole set is an element of this set. Make sense? Cool. So this difference would keep the 6 and the 1, not the 2, would keep the 0 and keep the 3 and keep the 4. Awesome. Similar to sets, we
Have--oh, sorry, before that, one of the reasons I'm talking about sets right now, beyond the fact that we need to talk about sets, is the fact that sets and propositions and predicates are very closely related. And they can both be useful for the other. Specifically, I want to talk about set builder notation. And that is where you take a set, and you describe a subset of a set by using a predicate. So for example, we can look at the set of all n in the natural numbers such that n is prime. So we have this predicate of n over here on the right. And we're pulling out all of the elements of this set, the natural numbers, but only the ones that satisfy our predicate. So this is set builder notation. You have elements of a set such that this predicate is satisfied. This is the notation we'll use. And this set, of course, will return the set of primes-- 2, 3, 5, 7, not 9, 11, and so on. Very useful, we're going to use that all the time.
Similar to sets, we have tuples. This is an ordered list of elements. And repeats are OK. And it's written with parentheses instead of curly braces. For example, the tuple (6, 1, 2, 0) is a sequence with four elements. This is not the same as (6, 1, 2, 0, 0), which is a tuple with five elements. As sets, they're the same. They have the same elements. But this one has repeats. So they're different. And likewise, neither of these is equivalent to (2, 1, 6, 0). Because the order is different, even if the elements are the same. So a tuple cares about the order. By the way, last I checked, 2.160 is identification, estimation, and learning in MechE, not the same, even though they have the same digits. It doesn't really make sense to ask for the intersection or the union or the difference of tuples. So we're not even going to try. Any questions about sets or tuples? Nice.
Let's go back to the definition I probably deleted already. A proof is a verification of a proposition by a sequence of logical deductions from a base set of axioms. I hope I got that right. We've already talked at length about propositions, one of those three terms. Let's turn to the next one, axioms. We've used both of those boards, on to this board. Nice. And axiom is a proposition we assume is true. You might have heard, when you're doing mathematical proofs, you shouldn't be assuming anything. You have to prove everything. And that's not quite true. We need somewhere to start. We need some foundation to build up from. The trick is to declare all of them in advance. These are the axioms I'm using. And if you assume these axioms, then these proofs tell you other things that also have to be true. So the axioms are the things you start with. We take them to be true. Sometimes, people say we take them to be self-evident. But I don't like that phrasing. Because they're not necessarily true in some holistic sense. We just assume them to be true for the sake of the math we're doing now. And in fact, you can often have axioms that contradict each other, as long as you're not using them at the same time.
For example, let's see. For example, we have the famous Euclid's parallel postulate. So Euclid, in 200 BC, or whenever he was alive, maybe 2000-- someone can tell me-- wrote a book, The Elements, Euclid's Elements, that chronicled all of Euclidean geometry. That's why it's called Euclidean geometry. He literally wrote the book on it. And at the beginning of the book, he had five axioms. "Postulate" is another word for "axiom," a little outdated, but still there. And parallel postulate, the fifth of the five axioms, famously for centuries, millennia, people kept trying to prove that actually, the parallel postulate doesn't have to be an axiom. You can prove it's true if you only assume the first four axioms. So it doesn't have to be an axiom. It can be a theorem. And people kept trying and kept trying and kept trying. By the way, the statement of the parallel postulate is that for every point p and line l that doesn't contain p, p not in l, there exists a unique line l prime through p parallel to l. In picture, if you have a point here and some line that doesn't go through that point, then there's a unique line parallel and going through your point. Here's p. Here's l. Intuitive, right? Makes sense. And Euclid took this as an axiom and went with it. But can we prove this, based on the other four axioms? And turns out, thousands of years later, we finally know the answer. No. No. This is not a theorem. It does not follow from the other four axioms. Because we know what happens if you change the axiom. Things do happen in a meaningful way. For example, instead of saying there is a unique line, a unique line, let's change that to no lines. There are no lines through your point parallel to your line. The concept of parallel lines doesn't exist if we use that axiom instead of Euclid's version and the other four axioms that Euclid did, you can get spherical geometry. In spherical geometry, your plane, your canvas, is a sphere instead of a plane. A line is a great circle. It's a circle whose center is the center of the sphere. And a point isn't just a point, but it's a point, and its antipode, the one directly across from it on the sphere. And if that's how we define points and lines, then there are no parallel lines. All great circles intersect each other. And we get a meaningful geometry that we can prove stuff with, that we can prove different things with than Euclid could. Since we have a different set of axioms, we're going to have a different set of conclusions. But it's still meaningful. Likewise, if we replace this-- instead of no lines, we do infinitely many lines, well, there's another version of geometry that does that. It's hyperbolic geometry, lots of ways to draw it. But sometimes, it's drawn in a circle. But now a line is a part of a circle that's perpendicular to the boundary. A point is just a point. But now if we have a line and a point not on that line, well, parallel just means they don't intersect. So, well, here is a line through p that doesn't intersect l. Well, here's another one. And here's another one. There are lots of them, infinitely many lines through p that don't touch l. And so this is a different kind of geometry that satisfies a different set of axioms. And so no, you can't prove the fifth axiom from the first four. Because you can change the fifth one and get new conclusions that make sense and aren't contradictory.
Now, I've said a couple of times, we can change it and get a new system of geometry. Well, you can imagine you can always change your axioms to some other set of assumptions and make a mathematical theory out of it. Does any set of assumptions work? Are they all as good as the others? Well, there are a couple of things that can go wrong. There are a couple of properties you might want your set of axioms to satisfy. A set of axioms is consistent when you can't prove that false is true. And we need that, right? Let me see if that's how we defined it. Yeah, if no proposition can be proved and disproved, we need true and false to be different things. Because remember, false implies anything you want. That's sometimes called the principle of explosion, by the way, great name. False implies anything. So if false is true, and false implies anything, then everything is true. So we don't want to be able to prove that false is true, because then our theory is uninteresting. Because everything is true, and everything is false. So we definitely want a set of axioms that is consistent. Ideally, we would also have a set of axioms-- a set of axioms is complete when every true-- let's see, yeah, every true proposition can be proved from the axioms. We want things to be true or false. And we want proof to be the metric by which we decide whether something is true or false. If we can find a proof for it, it's true. Ideally, if it's not true, we'd be able to find a proof for the opposite, for the not of that proposition. So the baseline things, the two things you would want in a set of axioms that is nice to work with, you would want it to be consistent. You would want it to be complete. And then Kurt Godel comes along and says, nope, can't have both. There's what's called the Godel Incompleteness Theorem. That's G-O-umlaut-D-E-L. Godel was able to prove that you can't have a system of axioms that is both consistent and complete, as long as it's complicated enough to just do arithmetic, addition and multiplication. You can't have both. We certainly want to be able to add and multiply numbers, which means we have to pick consistency or completeness. And I know which one I'm picking. I'm going to pick consistent, so that true and false have meaning. What this means-- and this kind of messes with my head a little bit. What Gödel's completeness theorem-- sorry, Incompleteness Theorem tells us is that there are true statements in math, in whatever set of axioms we're working with, there are true statements that cannot be proved. You're never going to be able to disprove it. But if you want to prove it, you have to add more axioms. But then once you add more axioms, that bigger set of axioms now has other true statements that can't be proved with those axioms. So conceivably, we might ask you to prove a problem in homework that can't be proved from the axioms, even though it's true. We're not going to do that. That's mean. Conceivably, Goldbach's Conjecture might be true, but unprovable. Maybe, I don't know. Question?
STUDENT: [INAUDIBLE].
Zachary Abel: Yeah, excellent question. If something doesn't have a proof, how do we know it's true? That is a really good question. And that's also getting back into the set theory and logic and underpinnings of math that are too in the weeds for this course. But I'm happy to discuss it afterward if you'd like.
Last thing I want to say about axioms. Every mathematician needs a set of axioms that they're working with so they know what they're allowed to assume as they're proving new things. What axioms are we going to use in this class? Roughly speaking, all of high school math. Let's say that any fact that you think is general enough and familiar enough and simple enough to be included in basically, every high school math curriculum. You're allowed to assume it, and go from there. Ideally, we ask you to identify it. Write down fact. Write the theorem you're stating, or the theorem you're assuming, like, the product of two even numbers is even. I know this from high school. And then go ahead and use it. Because ideally, at every step in a proof, we know why each thing is true. And if sometimes the reason is that's an axiom, I'm assuming it, we should say that. Are there any questions? All right, that's all I've got. Be sure to go to recitation tomorrow. You can check your time on Canvas. You can switch your time on Canvas. We look forward to seeing you then. Thank you so much.