Understanding Proofs and Mathematical Reasoning

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. Who can tell me what a proof is? Any ideas of what is a proof anyway? Any thoughts? Yeah. Statements, each logically supported by the previous ones that get you from a set of assumptions to a set of conclusions. Very good. I like that. That's very close to what we're going to do here. Yeah? Now that's a special kind of proof, though. That's a mathematical proof. And I'm going to write a definition very close to that in a few minutes. But proofs exist beyond mathematics. Can anybody? Think of a higher level notion of what a proof is. That's correct what you said, but there's a higher meta level notion of what a proof is. Beyond that, they have no logical deductions, potentially. They have no assumptions. Any thoughts about a proof? OK, well, I think generally a proof is considered across multiple fields as a method for ascertaining the truth. And you described one method. Now by ascertaining, I mean establishing truth, verifying truth. And there's lots of ways to ascertain truth in society and even within science. What are some examples of ways that we ascertain truth in society? Yeah? Seeing that a piece of chalk will fall to the ground. Observation. Experiment and observation. Excellent. That's the bedrock of physics. I mean, who really knows if there's gravity out there? Well, we observe it. And so we then conclude that's the truth. There's gravity, and we have laws about it. That's one good way. What's another way of ascertaining truth across scientific disciplines or beyond science, just in society? How is truth established? What are the ways? Yeah? Well, establishing what's false. If you know what things aren't true, then that helps you narrow down what is true. Yes, truth. Yeah, that's great. Truth is the opposite of falsehood. How do we establish falsehood? What are the ways of doing that? How do you decide something is not true? In everyday life? Yeah? Find counter examples. Find counter examples. Yeah, that's good. So in fact, even a step more general sampling, Are there counter examples of ways? If you do something, an experiment 10 times, and every time it comes out one way, that's truth, maybe. But there's fields where that becomes truth. What about other ways? How are we going to decide if Roger Clemens is guilty of perjury? For lying about steroids to Congress. He did it or he didn't. How are we going to decide that? What's the truth behind it? How is that truth going to be ascertained? Examining evidence and who makes the conclusion there? The jury. Truth is established by juries or judges. You know, Blagojevich, I can never pronounce his name, the Illinois governor, Blagojevich, he's guilty. That's the truth. Okay? Of, you know, not of conspiracy, trying to sell Obama's Senate seat, but of lying to the authorities about campaign financing. OJ is guilty, not of killing his wife, but of breaking into an apartment to steal back some of his merchandise. Okay? So judges and juries make decisions on truth. What are other truths, bigger truths even, than judges and juries in society? There's one really big one that causes a lot of issues, yeah? What is it? Religion, the word of God. Broadly construed here, or religion. Now that one's really hard to argue about, because you believe it. Especially if you're not talking to God regularly, and somebody is, well it's hard to argue about the truth. So you rely on others to interpret it for you often. A priest, or a minister, or a rabbi. It gets complicated because you can end up with conflicting truths, based on who you think you're talking to or who your translator is for you. You know, another one is the word of your boss. Whatever the boss says is right. Often in business, the customer is always right. That's the truth, whatever the customer says. All right? You know, if Donald Trump is your boss, you better agree or you're fired, right? Often in classes, the professor says it, it is true because the authority said it. That's not true here. That will not hold. And one of the nicest things about math that I like a lot is that the youngest student can stand up against the oldest, most experienced professor and win an argument on mathematics. In fact, I do get pleasure when a student comes up and proves me wrong. I loved it when that student came in and she showed me what I said really wasn't right when you looked at it carefully or in a different light. Now, sometimes if I do it on the board here and it's in class, well, you know. That's fun. I feel a little embarrassed afterwards. But it's a good thing about mathematics, is that you can have that kind of dialogue. OK, another one which is related to the word of God sometimes is inner conviction. Very popular in computer science, believe it or not. You know, with the mantra, there are no bugs in my program. Can't tell you how many times you hear that. Closely related is I don't see why not something is true. And that's a good one, because that transfers the burden of proof to anybody who disagrees with you. You don't have to prove it. You say, I don't see why it's not true. All of a sudden, the other person who's questioning you becomes their job to disprove you, which is not so good. OK, now in mathematics, there's this higher level. And someone stated it very clearly up there. Let me write it up. Here in mathematics, we have a mathematical proof is a verification of a proposition by a chain. Of logical deductions from a set of axioms. Now that's a bit of a mouthful. There's three important components here. Propositions. Logical deductions and axioms. And we're going to spend the rest of the class today talking about each of these and then give an example of a proof. We'll start with propositions. A proposition is a statement. That is either true or false. You may not know which one, but it's one or the other. Simple example, 2 plus 3 equals 5. Now that's a true proposition. Here's one that's a little more interesting. For all n in the set of natural numbers, n squared plus n plus 41 is a prime number. Now I've used some notation here. This is the upside down a is the for all symbol. How many people have not seen that symbol before? I had a bunch of you. You're going to see a bunch of symbols here first week. And that means for every possible choice of n, And this is in the natural numbers, which is the set 0, 1, 2, 3, and so forth. It's the natural numbers. It's basically the integers, but not negative. So we're saying for every natural number, i.e. for 0, for 1, for 2, and for 3, and so forth, this expression is a prime. Now a prime number is a number that is not divisible. by any other number besides itself in 1. So 2, 3, 5, 7 are prime. 9 is not, because it's 3 times 3. Now this part here is called the predicate. And a predicate is a proposition whose truth depends On the value of a variable, in this case, n. This is referred to as the universe of discourse. It's the space of all things we're talking about. We're only talking about natural numbers here. This is called a quantifier. We'll see more quantifiers later. All right, now to see if this proposition is true, we need to make sure that this predicate is true for every natural number n. So let's see if we can check that. Let's try some values. So we'll try n is 1, 2, 3, and so forth. And we'll compute n squared plus n plus 41. And then we'll check, is it prime? So for n equals 0, n squared plus n plus 41 is 41. Is 41 prime? Yeah. Nothing divides 41 but itself in 1. Let's try 1. 1 squared plus 1 plus 41 is 43. 43 prime. Yes. Let's try 2. We get 4 plus 2 is 6 plus 41 is 47. Is 47 prime? Yes. Looking good. 3, I got 9, 12, 53. 53 prime? Yeah. And I could keep on going here. I could go down to 20. I get 420, 461. In fact, that is a prime. And I could just keep on going here. Go down to 39, I get 1,601. You can check that as a prime. The first 40 values of n, the proposition is true. The predicate is true. It is prime. Now, this is a great example because in a lot of fields, physics, for example, statistics often, if it's true, you check 40 examples. That's above and beyond the call of duty. It's always true. So yeah, this must be true. Right? No. Wrong. Often you'll see this in a lot of scientific fields. It is not true. Can anybody give me an example of n for which n squared plus n plus 41 is not prime? Yeah. 40. Good. Let's see about 40. 40 squared plus 40 plus 41 is 1681. What's that equal? 41 squared. So it is not prime. Somebody give me an obvious example where it's not prime. 41. Yeah, 41 squared. Everything is divided by 41. But 40 is the first breakpoint. So the first 40 examples work, and then it fails. So this proposition is false, even though it was looking pretty good. There's a reason I'm doing this. In fact, I'm going to do it some more here. I'm going to beat you over the head with it. Here's a famous in mathematics statement. a to the fourth plus b to the fourth plus c to the fourth equals d to the fourth has no positive integer solutions. That is a proposition. Now, this proposition was conjectured to be true by Euler. In 1769, Euler's a big honcho in math. You know, we still talk about him a lot, even though he's been dead for centuries. It was unsolved for over two centuries. Methodicians worked on it. It was finally disproved by a very clever fellow named Noam Elkes. 218 years later, after it was conjectured, he works at that other school down the street. And he came up with this. A equals 95,800. B equals 217,519. C equals 414,560. You don't have to remember these numbers. We're not going to quiz you on that. 422,481. Now he claims, I've never personally checked it, but presumably people have, you plug those in here and you have an equality. So he says. So in fact, The correct true proposition is there do exist a, b, c, d in the positive natural numbers such that a to the fourth plus b to the fourth plus c to the fourth equals d to the fourth. I used a new quantifier here called there exists. Instead of an upside down a, it's a backwards e. Don't ask me why. That's what it is. The plus means you can't have 0 or negative numbers, so these are the positive natural numbers. And here's your predicate, which of course, the truth of this depends on the values of a, b, c, and d. It took a long time to figure out that actually there was a solution here. Obviously, everything they tried till that time failed. Let me give you another one. 313 x cubed plus y cubed equals z cubed has no positive integer solutions. This turns out to be false, but the shortest, smallest counterexample has over 1,000 digits. This one was easy. They only have six digits. So there's no way ever you'd use a computer to exhaustively search 1,000 digit numbers here to show it's false. Now, of course, some of you are probably thinking, why on earth would I care if 313 times x cubed plus y cubed equals z cubed has a solution? Now that probably won't be the last time that thought occurs to you during the term. And why on earth would anybody ever try to even find a solution to that? You know, mathematicians are sort of a rare breed. Now actually in this case, that's really important in practice. This equation is an example of what's called an elliptic curve. And you study these if you're really a specialist in mathematics in graduate school. Or if you work for certain three-letter agencies. Because it's central to the understanding of how to factor large integers. That means factoring, showing that 1681 is 41 times 41. I say, OK, who cares about factoring? Well, factoring is the way to break crypto systems like RSA, which are used for everything that we do electronically today. You have a PayPal account. You buy something online. You're using SSL. They're all using cryptosystems, most of which are, almost all of which, are based on number theory. And in particular, they're based on factoring. And if you can find good solutions to things like this, or solutions to things like this, all of a sudden you can get an angle and a wedge on factoring. And it's because of that that now RSA uses 1,000 digit moduluses instead of 100 digit modulus is like they used to use, because people figured out how to factor them, how to break the cryptosystem. If you can break those cryptosystems, you can't rule the world, but it's close. So you'll learn, we'll talk more about this the week after next when we do number theory and we work up to RSA and how that cryptosystem works and why factoring is so important. So yeah, you all don't have to worry about, really have to worry about this, but these things are important. And the bigger message. Is that you don't just try a few cases and if it works you think it's done. That's not how the game works in mathematics. You can get an idea of maybe it's true. But it doesn't tell you the answer. All right, let me give it another one. This is another very famous one that probably most of you have heard of. The regions in any map can be colored in four colors so that adjacent regions. Have different colors. You know, like a map of the United States, every state gets a color. If two states share a border, they have different colors. You know, so you can distinguish them. This is known as the four-color theorem, and it's very famous in the popular literature. How many people have heard of this theorem before? Yeah, OK. So you've all heard of it. It has a long history. It was conjectured by somebody named Guthrie in 1853. He's the first person to say this ought to be possible. And there were many false proofs over the ensuing century. One of the most convincing was a proof using pictures by Kempe in 1879, 26 years later. And this proof was believed for over a decade. Mathematicians thought the proof was right. Until another mathematician named Hewitt found a fatal flaw in the argument. Now this proof, by Kempe, consisted of drawing pictures of what maps have to look like. You start by saying a map has to look like one of these types. And he would draw pictures of them. And then he argued that those types that he drew pictures of, it worked for. Proofs by picture are often very convincing and very wrong. And I'm going to give you one to start lecture next time. It would be proof by PowerPoint, which is even worse than proof by picture. And it is compelling. The point will be to show you proofs by picture are generally not a good thing. Because your brain just locks in, oh, that's what it has to look like. And you don't think about other ways that it might look like. Now, the four color theorem was finally proved by Oppel and Hocken in 1977. But they had to use a computer to check thousands of cases. Now, this was a little disturbing to mathematicians because how do they know the computer did the right thing? You know, your colleague writes a proof on the board, you can check it. But how do you know the computer didn't mess up or not do some cases? Now, everybody believes it's true now, but it's unsatisfying. A few years ago, a 12-page human proof was discovered, but it's not been verified. And people are very suspicious of it. Because the proof of the main lemma says, quote, details of this lemma is left to the reader. See figure 7. That's what the main lemma of the proof is. But people think that maybe there were some good ideas there, but very suspicious proof. All right, let's do another one, another proposition, also very famous. Every even integer but 2. Actually, a positive integer but 2, is the sum of two primes. For example, 24 is the sum of 11 and 13, which are prime. Anybody know, is this true or false, this proposition? Yeah? Yeah, that's right, me too. Nobody knows if this is true or false. This is called Goldbach's Conjecture. It was conjectured by Christian Goldbach in 1742. This is a really simple proposition. And it's amazing it's not known. In fact, I spent a couple of years working on it. I thought, oh, well, this has to be easy enough to prove when I was younger. And it didn't get very far. So people still don't know if it's true. And in fact, it was listed by the Globe as one of the great unsolved mysteries. So if you get out this Globe article here, on the handout, does everybody have this handout? If you don't, we'll get it passed out. Is somebody missing that handout up over there and over here? If we get those passed out. Now it lists the three conjectures. Do you see Goldbach's conjecture there? Now, can anybody point out something that's a little disturbing about... What the globe says about Goldbach's conjecture? Yeah. It gives the example, like instead of 24 is 11 plus 13, it says 20 is the sum of 9 and 11. Now, if we're allowed to use things like 9 as primes, Goldbach's conjecture is pretty easy to prove is true. All right. This won't be the last time we get examples from the literature. In fact, we're going to do this a lot, along this theme of you cannot believe everything you read. Now, the globe is easy pickings, but we'll do some more interesting ones later. Now, this article lists two other famous conjectures which most people believe to be true. The Riemann hypothesis, after a 1859 paper written by Bernard Riemann. suggests that zeros in an infinite series of numbers known as a zeta function form along a straight line in the complex plane. The hypothesis has been proved to 1.5 billion zeros, not far enough to prove it completely. If they did 1.5 trillion zeros, it wouldn't be far enough to prove it completely, of course. And then the Poincare. No, actually, the Riemann hypothesis a couple years ago, somebody credible claimed to have proved it. Proof turned out not to be right. Then there's the Poincaré conjecture. Now this one was finished off. It was proved to be true in 2003 by a Russian named Grigor Perelman. The conjecture says, roughly speaking, that 3D objects without holes, like not a donut, are equivalent to the sphere. They can sort of be deformed into a sphere. This is known to be true in four dimensions and higher, but nobody could prove it for three dimensions until Perelman came along. Now there's a bit of a controversy around this guy. He had an 80 page proof, but didn't have all the details. So then other teams of mathematicians got together and wrote 350 pages of details. And then most people believe now that it's right and that his original proof might not have had all the details, but he had the right structure of the proof. So he won prizes for this. He won the highest prize in mathematics, the Fields Medal. And just earlier this year, He was awarded the $1 million Millennium Prize. And there's about six problems or so that if you solve one of them, the Clay Institute gives you $1 million. And he's the first one to win the $1 million. Now the guy's a little strange. He rejected the Fields Medal and refused to go to the ceremony where he was being honored. And he's recently rejected the Millennium Prize. And anyway, this area's murky. And we have an expert to explain it all for us on video, which I thought I'd show. All right, let's do a simpler one here. For all n in z, n greater than or equal to 2 implies n squared greater than or equal to 4. Now z we use for the integers. And so that would be 0, 1, minus 1, 2, minus 2. And so forth. And this symbol here is implies. In fact, one thing you can notice when you read the text is we use different notation there as the standard than I will use in lecture. And there's lots of ways of doing it. You could have a double arrow, a single arrow. You could write out implies every time as it's done in the text. And it doesn't really matter which one you want to use. As long as you use one of the conventions for implies. And let me define what implies means. An implication. p implies q is said to be true if p is false or q is true, if either one. So we can write this down in terms of a truth table as follows. We have the values of p and q. And I'll give the value of p implies q. If p is q and q is true, sorry, p is true and q is true. What about P implies Q? True, because Q is true, the definition. If P is true and Q is false? False. P is false, Q is true. What about false and false is true, even though? Well, this is false. As long as p is false, p implies q is true. So this is important to remember. False implies anything is true, which is a little strange. There's a famous expression. If pigs could fly, I would be king. Is that true? Sort of. In fact, this statement. Pigs fly implies I'm king. That's true, because pigs don't fly. Doesn't matter whether or not I'm king, which I'm not. Since pigs don't fly, even though that's false, the implication is true. Now some of you have worked on these things before. It's second nature. If you haven't, I want to start getting familiar with that. All right, let's do another example. All right, what about this proposition? For all n, for all integers, n and z, n greater than or equal to 2, this is if and only if. n squared greater than or equal to 4. Is that true? Is n bigger than 2 if and only if n squared is bigger than 4? It's false. What's an example of n for which that's false? Negative. So it's false. n equals negative 3. Negative 3 squared is bigger than or equal to 4, but negative 3 is not bigger than or equal to 2. And in fact, this if and only if means you have to have an implication both ways. So you've got to check both ways for it. So let's do the truth table. Extend this truth table out here. We'll do the truth table for P if and only if Q. All right. So here are p and q. Is q implies p true for this row? Does q imply true imply true? Yeah. False implies true. That's true. True does not imply false. That's false. And false implies false. And so now we can see where p is if and only if q. If they're both true, then it's true here. What about here? Is p true if and only if q is true in this case? No, because p implies q is false, but q implies p is true. So it's false. False here. I made a mistake there, right? That was true. Whoops. And true if and only if true. They're both true, so we're OK. So p if and only if q is true when they're both true or both false. That's it. If they're different, then it's not true. The key here is to always check both ways. So if you're asked to prove an if and only if, you've got to prove that way and that way. All right, we've just done about 15 propositions. Is every sentence a proposition? Yes, no? No, what's an example of something that's not a proposition? A what? This statement is false. This statement is false. That's true. Well, that is true. It's not a proposition. Because if it were true, it wouldn't be false. And if it was false, then it would be true and you'd have a contradiction. So it's neither true nor false. What's a more simple example of something that's not a proposition? Ooh. Boy, I would have said that's true in some world, because yeah, that's a tissue. So it's a true statement. I'm. Hello. That's good. That's neither true nor false. Yeah? A question. Who are you? Neither true nor false. So not everything is a proposition. But this course, pretty much everything we deal with will be a proposition. All right, so that's it for propositions. Any questions on propositions? All right, next we're going to talk about axioms. Now, the good news is that axioms are the same thing, really, as propositions. The only difference is that axioms are propositions that we just assume are true. An axiom is a proposition that is assumed. To be true. There's no proof that an axiom is true. You just assume it because you think it's reasonable. In fact, the word axiom comes from Greek. It doesn't mean to be true. It means to think worthy, something you think is worthy enough to be assumed to be true. Now, a lot of times you'll hear people say, sometimes we'll even say it to you, don't make assumptions when you're doing math. No, that's not true. You have to make assumptions when you do math. Otherwise, you can't do anything, because you've got to start with some axioms. The key in math is to identify what your assumptions are so people can see them. And the idea is that when you do a proof, anybody who agrees with your assumptions or your axioms can follow your proof, and they have to agree with your conclusion. Now, they might disagree with your axioms, in which case they're not going to buy your proof. Now there are lots of axioms used in math. For example, if a equals b and b equals c, then a equals c. There is no proof of that. But it seems pretty good. And so we just throw it in the bucket of axioms and use it. Now, Axioms can be contradictory in different contexts. Here's a good example. In Euclidean geometry, there's a central axiom that says, given a line, L, and a point, P, not on L, there is. exactly one line through P parallel to L. You all saw this in geometry in middle school, right? Got a point in a line, there's exactly one line, another line through the point that's parallel to the line. Now there's also a field called spherical geometry. And there you have an axiom that contradicts this. It says, given a line l and a point p not on l, there is no line through p parallel to l on the sphere. There's a field called hyperbolic geometry. And there, there's an axiom that says, given a line L and a point P0 on L, there are infinitely many lines through P parallel to L. So how can this be? Does that mean one of these fields is totally bogus, or two of them are? Because they've got contradictory axioms. That's OK. Just whatever field you're in, state your axioms. And they do make sense in their various fields. This is planar geometry. This is on the sphere. And this is on hyperbolic geometry. They make sense in those contexts. So you can have more or less whatever axioms you want. There are sort of two guiding principles to axioms. Axioms should be, it's called, consistent and complete. Now, a set of axioms is consistent if no proposition can be proved to be both true and false. And you can see why that's important. Now, if you spend three weeks proving something's true, and the next day somebody proves it's also false, I mean, the whole thing was pointless. So it only makes sense if your axioms as a group are consistent. A set of axioms is said to be complete. If it can be used to prove every proposition is either true or false. All right. Now, this is desirable because it means, well, you can solve every problem. Everything is, you can prove it's true or you can prove it's false. You can get to the end. Now, you'd think it shouldn't be too hard to get a set of axioms that satisfies these two basic properties. You're allowed to choose whatever you want, really. Just you don't want to be creating contradictions. And you want a set that's powerful enough that allows you to prove everything is true or false, one of the two. Turned out not to be so easy to do this. And in fact, many logicians spent their careers, famous logicians, trying to find a set of axioms, just one set, that was consistent and complete. In fact, Russell and Whitehead are probably the two most famous. They spent their entire careers doing this and they never got there. Then one day this guy named Kurt Gertle showed up and in the 1930s he proved it's not possible that there exists any set of axioms that are both consistent and complete. Now this discovery devastated the field. It was a huge discovery. You know imagine poor Russell and Whitehead. They spent their entire careers going after this Holy Grail Then Kurt shows up and said, hey, guys, there's no Grail. It doesn't exist. That's a little depressing. Pretty bad day when that happened. Now, it's an amazing result because it says, if you want consistency, and that's a must, there will be true facts that you will never be able to prove. We're not going to prove that here. It's proved in a logic course. For example, maybe Goldbach's conjecture is true, and it is impossible to prove. Now, we're going to try not to assign any of those problems for homework. And in fact, people, they do exist. It's complicated. You can state a problem that you can't prove is true or false. And you may be thinking that from time to time. Hey, it's one of those, you know. Remember what your parents told you? If you work hard enough, you can do anything? They were wrong. All right, that's enough for now. We'll do more of this next time.

Who can tell me what a proof is? Any ideas of what is a proof anyway? Any thoughts? Yeah. Statements, each logically supported by the previous ones that get you from a set of assumptions to a set of conclusions.

Very good. I like that. That's very close to what we're going to do here. Yeah?

Now that's a special kind of proof, though. That's a mathematical proof. And I'm going to write a definition very close to that in a few minutes. But proofs exist beyond mathematics.

Can anybody? Think of a higher level notion of what a proof is. That's correct what you said, but there's a higher meta level notion of what a proof is. Beyond that, they have no logical deductions, potentially. They have no assumptions.

Any thoughts about a proof? OK, well, I think generally a proof is considered across multiple fields as a method for ascertaining the truth. And you described one method.

Now by ascertaining, I mean establishing truth, verifying truth. And there's lots of ways to ascertain truth in society and even within science. What are some examples of ways that we ascertain truth in society? Yeah? Seeing that a piece of chalk will fall to the ground.

Observation. Experiment and observation. Excellent. That's the bedrock of physics. I mean, who really knows if there's gravity out there?

Well, we observe it. And so we then conclude that's the truth. There's gravity, and we have laws about it. That's one good way. What's another way of ascertaining truth across scientific disciplines or beyond science, just in society?

How is truth established? What are the ways? Yeah? Well, establishing what's false.

If you know what things aren't true, then that helps you narrow down what is true. Yes, truth. Yeah, that's great.

Truth is the opposite of falsehood. How do we establish falsehood? What are the ways of doing that?

How do you decide something is not true? In everyday life? Yeah? Find counter examples.

Find counter examples. Yeah, that's good. So in fact, even a step more general sampling, Are there counter examples of ways? If you do something, an experiment 10 times, and every time it comes out one way, that's truth, maybe. But there's fields where that becomes truth.

What about other ways? How are we going to decide if Roger Clemens is guilty of perjury? For lying about steroids to Congress.

He did it or he didn't. How are we going to decide that? What's the truth behind it?

How is that truth going to be ascertained? Examining evidence and who makes the conclusion there? The jury.

Truth is established by juries or judges. You know, Blagojevich, I can never pronounce his name, the Illinois governor, Blagojevich, he's guilty. That's the truth. Okay?

Of, you know, not of conspiracy, trying to sell Obama's Senate seat, but of lying to the authorities about campaign financing. OJ is guilty, not of killing his wife, but of breaking into an apartment to steal back some of his merchandise. Okay?

So judges and juries make decisions on truth. What are other truths, bigger truths even, than judges and juries in society? There's one really big one that causes a lot of issues, yeah? What is it? Religion, the word of God.

Broadly construed here, or religion. Now that one's really hard to argue about, because you believe it. Especially if you're not talking to God regularly, and somebody is, well it's hard to argue about the truth.

So you rely on others to interpret it for you often. A priest, or a minister, or a rabbi. It gets complicated because you can end up with conflicting truths, based on who you think you're talking to or who your translator is for you. You know, another one is the word of your boss.

Whatever the boss says is right. Often in business, the customer is always right. That's the truth, whatever the customer says.

All right? You know, if Donald Trump is your boss, you better agree or you're fired, right? Often in classes, the professor says it, it is true because the authority said it.

That's not true here. That will not hold. And one of the nicest things about math that I like a lot is that the youngest student can stand up against the oldest, most experienced professor and win an argument on mathematics.

In fact, I do get pleasure when a student comes up and proves me wrong. I loved it when that student came in and she showed me what I said really wasn't right when you looked at it carefully or in a different light. Now, sometimes if I do it on the board here and it's in class, well, you know.

That's fun. I feel a little embarrassed afterwards. But it's a good thing about mathematics, is that you can have that kind of dialogue.

OK, another one which is related to the word of God sometimes is inner conviction. Very popular in computer science, believe it or not. You know, with the mantra, there are no bugs in my program.

Can't tell you how many times you hear that. Closely related is I don't see why not something is true. And that's a good one, because that transfers the burden of proof to anybody who disagrees with you.

You don't have to prove it. You say, I don't see why it's not true. All of a sudden, the other person who's questioning you becomes their job to disprove you, which is not so good.

OK, now in mathematics, there's this higher level. And someone stated it very clearly up there. Let me write it up. Here in mathematics, we have a mathematical proof is a verification of a proposition by a chain.

Of logical deductions from a set of axioms. Now that's a bit of a mouthful. There's three important components here. Propositions. Logical deductions and axioms.

And we're going to spend the rest of the class today talking about each of these and then give an example of a proof. We'll start with propositions. A proposition is a statement. That is either true or false. You may not know which one, but it's one or the other.

Simple example, 2 plus 3 equals 5. Now that's a true proposition. Here's one that's a little more interesting. For all n in the set of natural numbers, n squared plus n plus 41 is a prime number. Now I've used some notation here. This is the upside down a is the for all symbol.

How many people have not seen that symbol before? I had a bunch of you. You're going to see a bunch of symbols here first week. And that means for every possible choice of n, And this is in the natural numbers, which is the set 0, 1, 2, 3, and so forth.

It's the natural numbers. It's basically the integers, but not negative. So we're saying for every natural number, i.e. for 0, for 1, for 2, and for 3, and so forth, this expression is a prime. Now a prime number is a number that is not divisible. by any other number besides itself in 1. So 2, 3, 5, 7 are prime.

9 is not, because it's 3 times 3. Now this part here is called the predicate. And a predicate is a proposition whose truth depends On the value of a variable, in this case, n. This is referred to as the universe of discourse.

It's the space of all things we're talking about. We're only talking about natural numbers here. This is called a quantifier. We'll see more quantifiers later. All right, now to see if this proposition is true, we need to make sure that this predicate is true for every natural number n.

So let's see if we can check that. Let's try some values. So we'll try n is 1, 2, 3, and so forth. And we'll compute n squared plus n plus 41. And then we'll check, is it prime?

So for n equals 0, n squared plus n plus 41 is 41. Is 41 prime? Yeah. Nothing divides 41 but itself in 1. Let's try 1. 1 squared plus 1 plus 41 is 43. 43 prime. Yes.

Let's try 2. We get 4 plus 2 is 6 plus 41 is 47. Is 47 prime? Yes. Looking good. 3, I got 9, 12, 53. 53 prime? Yeah.

And I could keep on going here. I could go down to 20. I get 420, 461. In fact, that is a prime. And I could just keep on going here. Go down to 39, I get 1,601. You can check that as a prime.

The first 40 values of n, the proposition is true. The predicate is true. It is prime. Now, this is a great example because in a lot of fields, physics, for example, statistics often, if it's true, you check 40 examples.

That's above and beyond the call of duty. It's always true. So yeah, this must be true. Right?

No. Wrong. Often you'll see this in a lot of scientific fields. It is not true. Can anybody give me an example of n for which n squared plus n plus 41 is not prime?

Yeah. 40. Good. Let's see about 40. 40 squared plus 40 plus 41 is 1681. What's that equal?

41 squared. So it is not prime. Somebody give me an obvious example where it's not prime. 41. Yeah, 41 squared.

Everything is divided by 41. But 40 is the first breakpoint. So the first 40 examples work, and then it fails. So this proposition is false, even though it was looking pretty good. There's a reason I'm doing this.

In fact, I'm going to do it some more here. I'm going to beat you over the head with it. Here's a famous in mathematics statement. a to the fourth plus b to the fourth plus c to the fourth equals d to the fourth has no positive integer solutions. That is a proposition.

Now, this proposition was conjectured to be true by Euler. In 1769, Euler's a big honcho in math. You know, we still talk about him a lot, even though he's been dead for centuries.

It was unsolved for over two centuries. Methodicians worked on it. It was finally disproved by a very clever fellow named Noam Elkes. 218 years later, after it was conjectured, he works at that other school down the street.

And he came up with this. A equals 95,800. B equals 217,519. C equals 414,560.

You don't have to remember these numbers. We're not going to quiz you on that. 422,481.

Now he claims, I've never personally checked it, but presumably people have, you plug those in here and you have an equality. So he says. So in fact, The correct true proposition is there do exist a, b, c, d in the positive natural numbers such that a to the fourth plus b to the fourth plus c to the fourth equals d to the fourth. I used a new quantifier here called there exists. Instead of an upside down a, it's a backwards e.

Don't ask me why. That's what it is. The plus means you can't have 0 or negative numbers, so these are the positive natural numbers. And here's your predicate, which of course, the truth of this depends on the values of a, b, c, and d.

It took a long time to figure out that actually there was a solution here. Obviously, everything they tried till that time failed. Let me give you another one. 313 x cubed plus y cubed equals z cubed has no positive integer solutions. This turns out to be false, but the shortest, smallest counterexample has over 1,000 digits.

This one was easy. They only have six digits. So there's no way ever you'd use a computer to exhaustively search 1,000 digit numbers here to show it's false.

Now, of course, some of you are probably thinking, why on earth would I care if 313 times x cubed plus y cubed equals z cubed has a solution? Now that probably won't be the last time that thought occurs to you during the term. And why on earth would anybody ever try to even find a solution to that?

You know, mathematicians are sort of a rare breed. Now actually in this case, that's really important in practice. This equation is an example of what's called an elliptic curve. And you study these if you're really a specialist in mathematics in graduate school.

Or if you work for certain three-letter agencies. Because it's central to the understanding of how to factor large integers. That means factoring, showing that 1681 is 41 times 41. I say, OK, who cares about factoring? Well, factoring is the way to break crypto systems like RSA, which are used for everything that we do electronically today. You have a PayPal account.

You buy something online. You're using SSL. They're all using cryptosystems, most of which are, almost all of which, are based on number theory. And in particular, they're based on factoring. And if you can find good solutions to things like this, or solutions to things like this, all of a sudden you can get an angle and a wedge on factoring.

And it's because of that that now RSA uses 1,000 digit moduluses instead of 100 digit modulus is like they used to use, because people figured out how to factor them, how to break the cryptosystem. If you can break those cryptosystems, you can't rule the world, but it's close. So you'll learn, we'll talk more about this the week after next when we do number theory and we work up to RSA and how that cryptosystem works and why factoring is so important. So yeah, you all don't have to worry about, really have to worry about this, but these things are important. And the bigger message.

Is that you don't just try a few cases and if it works you think it's done. That's not how the game works in mathematics. You can get an idea of maybe it's true. But it doesn't tell you the answer. All right, let me give it another one.

This is another very famous one that probably most of you have heard of. The regions in any map can be colored in four colors so that adjacent regions. Have different colors. You know, like a map of the United States, every state gets a color.

If two states share a border, they have different colors. You know, so you can distinguish them. This is known as the four-color theorem, and it's very famous in the popular literature. How many people have heard of this theorem before?

Yeah, OK. So you've all heard of it. It has a long history. It was conjectured by somebody named Guthrie in 1853. He's the first person to say this ought to be possible.

And there were many false proofs over the ensuing century. One of the most convincing was a proof using pictures by Kempe in 1879, 26 years later. And this proof was believed for over a decade.

Mathematicians thought the proof was right. Until another mathematician named Hewitt found a fatal flaw in the argument. Now this proof, by Kempe, consisted of drawing pictures of what maps have to look like. You start by saying a map has to look like one of these types. And he would draw pictures of them.

And then he argued that those types that he drew pictures of, it worked for. Proofs by picture are often very convincing and very wrong. And I'm going to give you one to start lecture next time.

It would be proof by PowerPoint, which is even worse than proof by picture. And it is compelling. The point will be to show you proofs by picture are generally not a good thing. Because your brain just locks in, oh, that's what it has to look like.

And you don't think about other ways that it might look like. Now, the four color theorem was finally proved by Oppel and Hocken in 1977. But they had to use a computer to check thousands of cases. Now, this was a little disturbing to mathematicians because how do they know the computer did the right thing? You know, your colleague writes a proof on the board, you can check it.

But how do you know the computer didn't mess up or not do some cases? Now, everybody believes it's true now, but it's unsatisfying. A few years ago, a 12-page human proof was discovered, but it's not been verified.

And people are very suspicious of it. Because the proof of the main lemma says, quote, details of this lemma is left to the reader. See figure 7. That's what the main lemma of the proof is. But people think that maybe there were some good ideas there, but very suspicious proof. All right, let's do another one, another proposition, also very famous.

Every even integer but 2. Actually, a positive integer but 2, is the sum of two primes. For example, 24 is the sum of 11 and 13, which are prime. Anybody know, is this true or false, this proposition? Yeah?

Yeah, that's right, me too. Nobody knows if this is true or false. This is called Goldbach's Conjecture. It was conjectured by Christian Goldbach in 1742. This is a really simple proposition.

And it's amazing it's not known. In fact, I spent a couple of years working on it. I thought, oh, well, this has to be easy enough to prove when I was younger. And it didn't get very far.

So people still don't know if it's true. And in fact, it was listed by the Globe as one of the great unsolved mysteries. So if you get out this Globe article here, on the handout, does everybody have this handout? If you don't, we'll get it passed out. Is somebody missing that handout up over there and over here?

If we get those passed out. Now it lists the three conjectures. Do you see Goldbach's conjecture there? Now, can anybody point out something that's a little disturbing about...

What the globe says about Goldbach's conjecture? Yeah. It gives the example, like instead of 24 is 11 plus 13, it says 20 is the sum of 9 and 11. Now, if we're allowed to use things like 9 as primes, Goldbach's conjecture is pretty easy to prove is true. All right. This won't be the last time we get examples from the literature.

In fact, we're going to do this a lot, along this theme of you cannot believe everything you read. Now, the globe is easy pickings, but we'll do some more interesting ones later. Now, this article lists two other famous conjectures which most people believe to be true. The Riemann hypothesis, after a 1859 paper written by Bernard Riemann.

suggests that zeros in an infinite series of numbers known as a zeta function form along a straight line in the complex plane. The hypothesis has been proved to 1.5 billion zeros, not far enough to prove it completely. If they did 1.5 trillion zeros, it wouldn't be far enough to prove it completely, of course.

And then the Poincare. No, actually, the Riemann hypothesis a couple years ago, somebody credible claimed to have proved it. Proof turned out not to be right.

Then there's the Poincaré conjecture. Now this one was finished off. It was proved to be true in 2003 by a Russian named Grigor Perelman. The conjecture says, roughly speaking, that 3D objects without holes, like not a donut, are equivalent to the sphere. They can sort of be deformed into a sphere.

This is known to be true in four dimensions and higher, but nobody could prove it for three dimensions until Perelman came along. Now there's a bit of a controversy around this guy. He had an 80 page proof, but didn't have all the details.

So then other teams of mathematicians got together and wrote 350 pages of details. And then most people believe now that it's right and that his original proof might not have had all the details, but he had the right structure of the proof. So he won prizes for this.

He won the highest prize in mathematics, the Fields Medal. And just earlier this year, He was awarded the $1 million Millennium Prize. And there's about six problems or so that if you solve one of them, the Clay Institute gives you $1 million.

And he's the first one to win the $1 million. Now the guy's a little strange. He rejected the Fields Medal and refused to go to the ceremony where he was being honored. And he's recently rejected the Millennium Prize. And anyway, this area's murky.

And we have an expert to explain it all for us on video, which I thought I'd show. All right, let's do a simpler one here. For all n in z, n greater than or equal to 2 implies n squared greater than or equal to 4. Now z we use for the integers.

And so that would be 0, 1, minus 1, 2, minus 2. And so forth. And this symbol here is implies. In fact, one thing you can notice when you read the text is we use different notation there as the standard than I will use in lecture.

And there's lots of ways of doing it. You could have a double arrow, a single arrow. You could write out implies every time as it's done in the text.

And it doesn't really matter which one you want to use. As long as you use one of the conventions for implies. And let me define what implies means.

An implication. p implies q is said to be true if p is false or q is true, if either one. So we can write this down in terms of a truth table as follows.

We have the values of p and q. And I'll give the value of p implies q. If p is q and q is true, sorry, p is true and q is true.

What about P implies Q? True, because Q is true, the definition. If P is true and Q is false? False. P is false, Q is true.

What about false and false is true, even though? Well, this is false. As long as p is false, p implies q is true.

So this is important to remember. False implies anything is true, which is a little strange. There's a famous expression. If pigs could fly, I would be king.

Is that true? Sort of. In fact, this statement. Pigs fly implies I'm king.

That's true, because pigs don't fly. Doesn't matter whether or not I'm king, which I'm not. Since pigs don't fly, even though that's false, the implication is true. Now some of you have worked on these things before. It's second nature.

If you haven't, I want to start getting familiar with that. All right, let's do another example. All right, what about this proposition? For all n, for all integers, n and z, n greater than or equal to 2, this is if and only if. n squared greater than or equal to 4. Is that true?

Is n bigger than 2 if and only if n squared is bigger than 4? It's false. What's an example of n for which that's false?

Negative. So it's false. n equals negative 3. Negative 3 squared is bigger than or equal to 4, but negative 3 is not bigger than or equal to 2. And in fact, this if and only if means you have to have an implication both ways.

So you've got to check both ways for it. So let's do the truth table. Extend this truth table out here.

We'll do the truth table for P if and only if Q. All right. So here are p and q.

Is q implies p true for this row? Does q imply true imply true? Yeah.

False implies true. That's true. True does not imply false.

That's false. And false implies false. And so now we can see where p is if and only if q. If they're both true, then it's true here.

What about here? Is p true if and only if q is true in this case? No, because p implies q is false, but q implies p is true. So it's false. False here.

I made a mistake there, right? That was true. Whoops. And true if and only if true. They're both true, so we're OK.

So p if and only if q is true when they're both true or both false. That's it. If they're different, then it's not true. The key here is to always check both ways.

So if you're asked to prove an if and only if, you've got to prove that way and that way. All right, we've just done about 15 propositions. Is every sentence a proposition?

Yes, no? No, what's an example of something that's not a proposition? A what? This statement is false.

This statement is false. That's true. Well, that is true. It's not a proposition. Because if it were true, it wouldn't be false.

And if it was false, then it would be true and you'd have a contradiction. So it's neither true nor false. What's a more simple example of something that's not a proposition? Ooh.

Boy, I would have said that's true in some world, because yeah, that's a tissue. So it's a true statement. I'm.

Hello. That's good. That's neither true nor false.

Yeah? A question. Who are you? Neither true nor false.

So not everything is a proposition. But this course, pretty much everything we deal with will be a proposition. All right, so that's it for propositions.

Any questions on propositions? All right, next we're going to talk about axioms. Now, the good news is that axioms are the same thing, really, as propositions. The only difference is that axioms are propositions that we just assume are true. An axiom is a proposition that is assumed.

To be true. There's no proof that an axiom is true. You just assume it because you think it's reasonable. In fact, the word axiom comes from Greek. It doesn't mean to be true.

It means to think worthy, something you think is worthy enough to be assumed to be true. Now, a lot of times you'll hear people say, sometimes we'll even say it to you, don't make assumptions when you're doing math. No, that's not true.

You have to make assumptions when you do math. Otherwise, you can't do anything, because you've got to start with some axioms. The key in math is to identify what your assumptions are so people can see them. And the idea is that when you do a proof, anybody who agrees with your assumptions or your axioms can follow your proof, and they have to agree with your conclusion.

Now, they might disagree with your axioms, in which case they're not going to buy your proof. Now there are lots of axioms used in math. For example, if a equals b and b equals c, then a equals c. There is no proof of that.

But it seems pretty good. And so we just throw it in the bucket of axioms and use it. Now, Axioms can be contradictory in different contexts.

Here's a good example. In Euclidean geometry, there's a central axiom that says, given a line, L, and a point, P, not on L, there is. exactly one line through P parallel to L. You all saw this in geometry in middle school, right? Got a point in a line, there's exactly one line, another line through the point that's parallel to the line. Now there's also a field called spherical geometry.

And there you have an axiom that contradicts this. It says, given a line l and a point p not on l, there is no line through p parallel to l on the sphere. There's a field called hyperbolic geometry.

And there, there's an axiom that says, given a line L and a point P0 on L, there are infinitely many lines through P parallel to L. So how can this be? Does that mean one of these fields is totally bogus, or two of them are?

Because they've got contradictory axioms. That's OK. Just whatever field you're in, state your axioms. And they do make sense in their various fields. This is planar geometry.

This is on the sphere. And this is on hyperbolic geometry. They make sense in those contexts. So you can have more or less whatever axioms you want.

There are sort of two guiding principles to axioms. Axioms should be, it's called, consistent and complete. Now, a set of axioms is consistent if no proposition can be proved to be both true and false.

And you can see why that's important. Now, if you spend three weeks proving something's true, and the next day somebody proves it's also false, I mean, the whole thing was pointless. So it only makes sense if your axioms as a group are consistent.

A set of axioms is said to be complete. If it can be used to prove every proposition is either true or false. All right.

Now, this is desirable because it means, well, you can solve every problem. Everything is, you can prove it's true or you can prove it's false. You can get to the end. Now, you'd think it shouldn't be too hard to get a set of axioms that satisfies these two basic properties. You're allowed to choose whatever you want, really.

Just you don't want to be creating contradictions. And you want a set that's powerful enough that allows you to prove everything is true or false, one of the two. Turned out not to be so easy to do this. And in fact, many logicians spent their careers, famous logicians, trying to find a set of axioms, just one set, that was consistent and complete. In fact, Russell and Whitehead are probably the two most famous.

They spent their entire careers doing this and they never got there. Then one day this guy named Kurt Gertle showed up and in the 1930s he proved it's not possible that there exists any set of axioms that are both consistent and complete. Now this discovery devastated the field. It was a huge discovery. You know imagine poor Russell and Whitehead.

They spent their entire careers going after this Holy Grail Then Kurt shows up and said, hey, guys, there's no Grail. It doesn't exist. That's a little depressing.

Pretty bad day when that happened. Now, it's an amazing result because it says, if you want consistency, and that's a must, there will be true facts that you will never be able to prove. We're not going to prove that here.

It's proved in a logic course. For example, maybe Goldbach's conjecture is true, and it is impossible to prove. Now, we're going to try not to assign any of those problems for homework.

And in fact, people, they do exist. It's complicated. You can state a problem that you can't prove is true or false. And you may be thinking that from time to time. Hey, it's one of those, you know.

Remember what your parents told you? If you work hard enough, you can do anything? They were wrong. All right, that's enough for now.

We'll do more of this next time.

Transcript for:Understanding Proofs and Mathematical Reasoning

Transcript for:
Understanding Proofs and Mathematical Reasoning