the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality 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 any thoughts yeah it's a chain of 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 that's very close to what we're going to do here yeah um now that's a special kind of proof though that's a mathematical proof and I'll 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 metal level notion of what a proof is beyond that they have no logical deductions potentially they have no assumptions any thoughts better a proof okay 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 even within science what are some examples of ways that we ascertain truth in society yeah like seeing that a piece of chalk will fall to the ground observation experiment and observation excellent that's that's the uh 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 or in or in sci Beyond science just in society how is truth established what are the ways yeah well establishing what's false if 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 yeah counter find counter examples yeah that's good so in fact even a step more General sampling counter examples our ways you know if you do something an experiment 10 times and every time it comes out one way that's truth maybe but there's fields that becomes truth what about other ways uh 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 how is that truth going to be ascertained yeah examining evidence and who makes the conclusion there the jury truth is established by juries or judges you know black go I can never pronounce his name the Illinois governor black oich 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 Finance 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 ReliOn what is it religion religion the word of God broadly construed here or religion you know now that one's really hard to argue about you know because you believe it you know and it's especially if you're not talking to God regularly and somebody is well it's hard to argue about you know the truth so you rely on others to interpret it for you often you know a priest or minister or Rabbi okay now it gets complicated because you can end up with conflicting truths based on you know who you think you're talking to or who your represent 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 with Donald Trump is your boss you better agree or you're fired right you know um often in classes the professor says it it is true because the authority said it that's not true here all right that will not hold and one of the nicest thing about math that I like a lot is that the youngest student can stand up against the most oldest most experienced professor and win an argument on mathematics in fact I am you know I really 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 you know 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 uh but it's a good thing about mathematics is that you can have that kind of dialogue okay um 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 the Mantra there are no bugs in my program can't tell you how many times you know you he that closely related is I don't see why not something is true now that's a good one because that transfers the burden of proof to anybody who disagrees with you right 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 not so good okay now in mathematics there's this higher level and someone uh 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 uh 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 + 3 = 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^2 + n + 41 is a prime number right 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 all right a bunch of you you're you're going to see a bunch of symbols here first 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 zero for one for two and for three and so forth this expression is a prime now a prime number is is a number that is not divisible by any other number besides itself and one so 2 3 5 seven or prime nine is not because it's three * three 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 all right 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 quantum 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 one two three and so forth and we'll compute n 2 + n + 41 and then we'll check is it Prime so for Nal 0 n^2 + n + 41 is 41 is 41 prime yeah nothing divides 41 but itself and one all right let's try one one 2 + 1+ 41 is 43 it's 43 prime yes let's try two we get 4 + 2 is 6 + 41 47 is 47 prime yes yes looking good three I got 9 12 uh 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 16001 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 you know if it's true you checked 40 examples that's above and beyond the Call of Duty it's 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^2 plus n plus 41 is not prime yeah 40 40 good let's see about 40 402 plus 40 + 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 Square everything is divided by 41 but 40 is the first break point 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 the 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 uh here's a famous in mathematics statement a to 4th plus b to 4th plus C to 4th equal D 4th has no positive integer solution that is a proposition now this proposition was conjectured to be true by Oiler in 1769 Oiler is 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 mathematicians worked on it it was finally disproved by very clever fellow named gnome Elis um 218 years later after it was conjectured he works at that other school uh down the street and uh he came up with this a equal 95,00 b equal 27,5 19 Cal 41456 you don't have to remember these numbers we're not going to quiz you on that 42248 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 correct true proposition is there do exist a b c d in the positive natural numbers such that a 4th plus b 4th plus C 4th = D 4th all right I used a new quantifier here called there exists instead of an up 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 zero or negative numbers so the 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 all right 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 Cub + y Cub = z cubed has no positive integer Solutions this turns out to be false but the shortest smallest counter example has over a thousand digits this one was easy they only has six digits so there's no way ever you'd use a computer to exhaustively search thousand 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 * XB + y Cub equal 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 I mean mathematicians are sort of a rare breed now actually in this case that's really important in practice okay this equation is an example of what's called an elliptic curve elliptic curve and you study these and if you're really a specialist in mathematics and 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 you know factoring showing that uh what was it 1681 is 41 * 41 I say okay 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 you have a PayPal account you buy something on online you're using SSL they're all using crypto systems 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 a an angle and a wedge on factoring and it's because of that that now RSA uses thousand digigit modulus instead of 100 digigit modulus like they used to use because people figured out how to factor them how to break the crypto system if you can break those crypto systems well you can't rule the world but it's close all right so you'll learn we talk more about this uh the week after next when we do number Theory and we work up to RSA and how that crypto system works and why factoring is so important all right so yeah you all don't have to worry about really have to worry about this but these things are important and 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 that's not how the game works in mathematics you can get an idea of maybe it's true but doesn't doesn't tell you the answer all right let me give it another one this is another very famous one that probably most 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 it's very famous in the popular literature how many people have heard of this theorem before yeah okay so you've all heard of it as a long history 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 Kempy in 1879 you know 26 years later and this proof was believed for over a decade mathematicians thought the proof was right until another mathematician named hewwood found a fatal flaw in the argument now this proof by kmy consisted of drawing pictures of what maps have to look like he start by saying a map has to look like one of these types he would draw pictures of them and then he argued that those types that he drew pictures of it worked for um proofs by picture are often very convincing Ing and very wrong and I'm going to give you one to start lecture next time be proof by PowerPoint which is even worse than proof by picture uh and it is compelling you know uh and 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 Opel and hackin 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 you can 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 um now everybody believes it's true now but it's unsatisfying a few years ago a 12-page human proof was discovered uh 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 seven that's what the main Lemma the proof is but people think there maybe 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 two actually positive integer but two is the sum of two primes for example 24 is the sum of 11 and 13 which our Prime anybody know is this true or false this proposition yeah yeah that's right me too uh nobody knows if this is true or false this is called goldbach's conjecture uh was conjectured by Christian goldbach in 1742 this is a really simple proposition and it you know is it's amazing it's not known in fact I spent you know couple years working on I thought oh well this has to be easy enough to prove when I was a younger and uh didn't get very far so people still don't know if it's true and in fact it was listed by the globe uh as one of the great Unsolved Mysteries so if you get out this Globe article here one the handout does everybody have this handout you don't we'll get it past out somebody missing that handout up up over there and over here all right if we get those passed out um now at list of three conjectures do you see goldbox conjecture there now can anybody point out something that's a little disturbing about what the globe says about goldbox conjecture yeah it gives the example like instead of 24 is 11 + 13 it says 20 is the sum of 9 and 11 now if we're allowed to use things like nine as primes gold bash can is pretty easy to prove is true all right this won't be the last time we we get examples from the literature fact we're going to do this a lot along this theme of you cannot believe everything you read and now the globe is easy pickings but we'll do some more interesting ones later uh now this article lists two other famous conjectures which most people believe to be true um the reman hypothesis um after a 1859 paper written by Bernard reman 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 now if if they did 1.5 trillion zeros it wouldn't be far enough to prove it completely of course um and then uh the Panka no actually the REM hypothesis a couple years ago somebody credible claimed who have proved it pro turned out not to be right then there's the panare conjecture now this one was finished off it was proved to be true in 2003 by a Russian named Gregor perilman the conjecture says roughly speaking that 3D objects without holes like not a donut uh 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 perilman came along along now there's a bit of a controversy around this guy uh 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 uh 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 you know he won the highest prize in mathematics the fields medal and uh 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 a million dollar and he's the first one to win the million dollars 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 um and anyway this area is 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 a simpler one here for all n in z n greater than equal to 2 implies n 2 greater than equal to four now Z we use for the integers and so that would be 0 1 - one 2 minus 2 and so forth and this symbol here is implies all right in fact one thing you're going to notice when you read the text is we use different notation there as the standard that 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 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 then 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 it's true because Q is true the definition if p is true and Q is false false uh p is false Q is true true what about false and false is true even though this is false as long as p is false P implies Q is true all right so this is important to remember false implies anything is true which is a little strange there's a famous expression uh 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 you worked on these things before second nature if you haven't want to start getting familiar with that uh 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 equal to to this is if and only if n^2 greater than equal to 4 is that true is n bigger than true if bigger than two if and only if n squ is bigger than four it's false what's an example of n for which that's false negative all right so it's false n equals -3 all right -32 is bigger than equal to 4 but3 is not bigger than equal to two and in fact this if and only if means you have to have an implication both ways so you got to check both ways for it so let's do the truth table extend this truth table out here do the truth table for p uh if and only if Q all right so here are p and Q um 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 does 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 uh I made a mistake there right that was true oops y uh and true if only have true okay they're both true so we're okay 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 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 something that's not a proposition a what this statement is false this statement is false that's true well that is true it a 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 have a contradiction so it's neither true nor false what's a more simple example of something that's not a proposition boy I would have said that's true in some some world you know because that yeah that's a tissue so it's a true statement um 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 axium is true you just assume it because you think it's reasonable in fact the word axium 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 he'll people say sometimes we'll even say it to you you know 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 got to start with some axioms the key in math is to I to identify what your ass are so people can see them and the idea is that when you do a proof anybody who agrees with your assumptions or your aums can follow your proof then 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 uh 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 ukian Geometry there's a central axium 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 axum that says given a line L and a point P not on L there are infinitely many lines through P parallel to L so how can this does that mean one of these fields is totally bogus or two of them are because they've got contradictory axioms that's okay just whatever field you're in state your axioms and they do make sense in their various Fields you know this is pler geometry this is on the sphere and this is on you know H hyperbolic geometry they make sense in those contexts so you can have more or less whatever whatever axioms you want there are sort of two guiding principles to axioms axium 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 you know if you spend 3 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 all right everything is you can prove it's true or you can prove it's false false you can get to the 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 they never got there then one day this guy named Kurt girdle 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 discover 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 doesn't exist that's a little 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 um and in fact people they do exist you can it's complicated you can State a problem that you can't prove is true or false uh and you may be thinking that from time to time hey it's one of those you know um it's remember 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 we'll do more of this next time