Original subtitles

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 and what is a proof anyway and

thoughts yeah very good I like that

that's 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

may have no logical deductions

potentially they have no assumptions any

thoughts better 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 and even within science what

are some examples of ways that we

ascertain truth in society yeah

observation experiment and observation

excellent that's 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

sir taining truth across scientific

disciplines or inside beyond science

just in society how is truth established

one of the ways yeah yes truth yeah

that's great truth is the opposite of

falsehood how do we establish falsehood

what are the ways in doing that how do

you decide something is not true and

every day ya find counter examples yeah

that's good so in fact even a step more

general sampling counter examples are

ways you know if you do something an

experiment 10 times and every time it

comes out one way huh 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 how is that true

it's going to be ascertained yeah

examining evidence and who makes the

conclusion there the jury truth is

established by juries or judges you know

like oh 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 sent a seat but of lying to

the authorities about campaign financing

Oh Jay 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 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 you 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 what

Donald Trump is your boss you better

agree or you're fired

right yeah

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 Beck 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 wheelie 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 but

it's a good thing about mathematics is

that you can have that kind of dialogue

okay 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 know 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 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 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 of the other

simple example two plus three equals

five 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

all 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 I had a bunch of

you yo 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 so forth it's the natural

numbers it's basically the integers but

not negative so we're saying for every

natural number ie 4 0 4 1 4 2 of the 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 and 1 so 2 3 5 7 or 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 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 quantifier will 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 and 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 it's 41 prime yeah nothing

divides 41 but itself and 1 alright

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 47 he's 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 1601 you can show

that is 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 for T

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 40

1 is 16 81 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 with that 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 if 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

Matheson's worked on it

it was finally disproved by very clever

fellow named no Mel Kees 218 years later

after was conjectured he works at that

other school down the street and he came

up with this a equals ninety five

thousand eight hundred b equals two

hundred seventeen thousand five hundred

nineteen c equals four hundred fourteen

thousand five hundred sixty you don't

have to remember these numbers we're not

going to quiz you on that four hundred

twenty two thousand four hundred eighty

one 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 to the fourth plus B to the

fourth plus C to the fourth equals D to

the four

all right 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 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 alright take 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 a thousand digits this one was easy

they only have 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 times s

Q 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 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

in your 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 what was it 16 81 is 41

times 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 do 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 which are based on

number theory and in particular that

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 a thousand digit

modulus instead of hundred digit modulus

is 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 I can't rule the

world but it's close

all right so you'll learn would talk

more about this 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 we all 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 because 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 you

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 I have 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

kemppi 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

he would found a fatal flaw in the

argument now this proof I can't be

consistent of drawing pictures of what

maps have to look like your summer

saying a map has to look like one of

these types and would draw pictures of

them and then he argued that those types

that you 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 be proof by PowerPoint which is

even worse than proof by picture and it

is compelling you know 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 Appel and Haken in 1977 but

they had to use the 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 of 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

lamb of the proof is but people think

that maybe we're 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 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 was

conjectured by Kristian Goldbach in 1742

this is a really simple proposition and

it you know as it's amazing it's not

known in fact I spend you know a couple

years working on I thought oh well this

has to be easy enough to prove when I

was a younger and 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 everybody have this

handout you don't we'll get it passed

out somebody missing the handout up 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 set up 24 is 11 plus 13 it

says 20 is the sum of nine and 11 now if

we're allowed to use things like nine as

primes Goldbach conjecture is pretty

easy to prove is true all right

this won't be the last time we get

examples from the literature if I queer

gonna 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 now this article lists to other

famous conjectures which most people

believe to be true the Riemann

hypothesis after a 1859 paper written by

bernhard riemann suggests that zeroes in

an infinite series of numbers known as a

zeta function form along a straight line

the complex plane the hypothesis has

been proved

to 1.5 billion zeros not far enough to

prove it completely now if they did 1.5

trillion zeros it wouldn't be far enough

to prove it completely of course and

then the pranker now actually the Rhema

thesis a couple years ago somebody

credible claim to approved it

proof turned out not to be right then

there's the plonker a conjecture now

this one was finished off it was proved

to be true in 2003 by a Russian named

Gregor Perelman the conjecture says

roughly speaking that 3d objects without

holes like not a doughnut 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 and 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 you know he

won the highest prize in mathematics the

Fields Medal and just earlier this year

he was awarded that $1,000,000

millennium prize and there's about six

problems or so that if you solve one of

them the clay is 2 gives you a million

dollars 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

in any way 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 simpler one here

for all n MZ and greater than equal to

two implies N squared greater than equal

to four 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 alright 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

is 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 and I'll give

the value of P implies Q if P is Q and Q

is true so I 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 P is false Q is

true what about false and false is true

even though this is false as long as P

is false P implies Q is true alright 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

second

if you haven't want to start getting

familiar with that alright let's do

another example all right what about

this proposition for all n for all

integers and in Z N greater than equal

to two this is if and only if n squared

greater than equal to four is that true

is n bigger than true if bigger than two

if and only if M Squared is bigger than

four false what's an example of n for

which that's false negative all right so

it's false n equals negative three all

right

negative three squared is bigger than

equal to four but negative three 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 to 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 it'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 just 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'm in a mistake there right that

was true

oops yep and true if and only if 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 I we've just done about 15

propositions is every sentence of

proposition yes no no what's an example

something is not a proposition

oh wow this statement is false that's

true well that is true it says he's not

a composition because if it were true it

wouldn't be false and if it was false

and it'd be true you have a

contradiction so it's neither true nor

false what's a more simple example of if

something that's not a proposition hmm

boy I would have said that's true in

some some world you know cuz that yeah

that's a tissue so it's a true statement

um 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're

Hill 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 a to

you 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 proofs 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 action 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 be 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 planar

geometry this is on the sphere and this

is on you know hyperbolic geometry they

make sense in those contexts so you can

have more less whatever-whatever axioms

you want there are sort of two guiding

principles two axioms

axiom 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 all right everything is you can

prove it's true or you can prove it's

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 to 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 like 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 discovery

devastated the field 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 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 you can its complicated 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 it's remember what your parents

told you if you work hard enough you can

do anything

they were wrong alright that's enough

for now we'll do more of this next time