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.

PROFESSOR: Now generally speaking,

a proof is going to have seven characteristics

that you want to keep in mind.

Good proofs are correct-- that's obviously important--

complete-- you've got to have all the details there.

All of the key steps have to be there.

They should be clear so we can understand what's going on.

Brief is good.

You don't want to crush somebody with all the details.

You want to get to the key points, and be crisp.

It's really nice if they're elegant.

Now, that means clever.

It's the mathematician's notion of beauty.

Like you go to the art museum, and the artists will say,

wow, that's a beautiful painting.

In mathematics, you say, wow, that's an elegant proof.

It's crisp, clever, short, to the point.

And it's really the highest compliment

you can get from a mathematician, anyway.

And there's a lot of judgment that goes into that.

Just like in art-- there's judgment

over what is great art.

The proof should be well organized.

For example, use lemmas the same way

you would use subroutines in writing

code-- helps to make it clear.

And the proof should be in order.

Sometimes you'll see proofs where things are

done in a haphazard fashion.

All the pieces are there, but they're in the wrong order.

Sometimes-- and they teach this in some high schools--

they teach you to do proofs backwards.

And the classic thing there is, say you're

trying to prove a equals b.

Well, the proof sometimes will start with what

you're trying to prove.

And then they'll do a bunch of steps.

And then you'll end up with 1 equals 1,

and you'll write a check, because you went

from a equals b to 1 equals 1.

And that's, of course, true.

Now, that's not a good thing to do.

It can be correct if the implications go this way.

Because really, you're starting with a fact-- 1 equals 1--

and deriving a equals b.

So if, in fact, the implications work this way,

then your proof is right.

But most people, especially as you get farther along,

think about it going from top to bottom.

So don't use this technique, because it'll confuse people.

You're liable to make a mistake.

Just start with 1 equals 1 and work your way from there--

top down for being in order.

Now, good proofs are very much like good code.

In fact, one of the reasons we care so much about teaching you

how to write a good proof in computer science

is so that later on, you'll be able to prove

that your programs are doing what you expect-- what they're

supposed to do.

Now, there are many famous examples where programs did not

do what they were supposed to do,

with disastrous consequences.

The Airbus A300 was one of the first commercial jets totally

operated by software.

It could take off, fly, and land totally by software.

It was a major advance in the airline industry.

The only problem was, that on one

of the first flights of the A300,

the software accidentally opened the rear door just

before landing.

And the plane crashed as a result.

It was the first plane crash in commercial history because

of a software bug.

There's a famous radiation device for cancer patients

called the Therac-25.

It's famous because it got into a race condition

occasionally, which caused the device

to just slam the patient with radiation-- so much so,

it killed the patient.

And they had multiple examples of this, and of course,

a lot of lawsuits afterwards.

How many of you all remember the 2000 election?

A few of you do.

OK, this will probably be the last class that remembers that.

But that's where Al Gore was going up against George Bush--

very close election-- all came down to recounting

the votes in Florida.

But in fact, Al Gore got negative 16,000 votes

in one county because of a software bug

in the electronic voting booths, which

I think they got rid of a lot of them in the election

after that.

Because the software was buggy.

So poor Al had enough problem which chads

and funny business in Florida.

But getting negative 16,000 votes certainly

didn't help his chances.

Several years ago, a single faulty command

in a computer system used by United and American Airlines

grounded the entire fleets to both airlines for close

to a day.

Because they couldn't do anything.

They're all run by computer, and the whole thing was screwed up.

So there's lots more examples.

We run into this issue all the time at Akamai.

Akamai is a company started by MIT folks-- by myself,

and Danny Lewin, and a dozen undergrads in the late 1990s.

And we deliver a lot of the content

you get on the web-- Facebook, all the search engines.

A lot of the stuff you go to comes from our servers.

So we've got to be very careful that we

don't have software bugs.

Now, in fact we do.

And we catch them every once in awhile.

But if we got a bad one, it would bring down

all the sites you go to you.

You wouldn't be able to go to those sites anymore.

And everybody would notice.

It would be sort of embarrassing.

Now, this really does matter.

And this is going to sound a little scary, but someday--

probably 30, 20 years from now, somewhere

in there-- it's possible that all of us, our lives

may depend on the software that some of you write.

In fact, to bring this home how scary it is,

look at the person sitting next to you.

And imagine that in 25 years, your life depends on

whether their code does what it's

supposed to do-- little scary.

That's why we are very motivated to help

you learn how to make rock-solid arguments,

so you don't have code that fries one of your classmates

someday, or puts him in a bad plane situation.

Now unfortunately, writing rock-solid proofs

is a very hard thing to do.

Even the world's best mathematicians

mess them up on a regular basis.

In fact, it's estimated that one third of all published proofs

have bugs, have flaws, that render the proof incorrect.

The trouble often arises because we get lazy.

We don't write down all the details or all the steps.

Because, wow, it's clear.

Let's just move on.

Now, this can be OK.

Not such a good practice, but it dramatically

increases the chances of making a mistake.

And there's some very famous examples

in the math literature from the world's

most famous mathematicians.

Gauss-- and we'll talk about Gauss

later during the term-- he's one of the most

famous mathematicians ever.

He wrote his PhD thesis in 1799.

And it's usually referred to as the first rigorous proof

of the fundamental theorem of algebra.

And that says that every polynomial

has a 0 over the complex numbers-- something

probably a lot of you learned in high school.

You get a polynomial.

You can find roots of the polynomial

over the complex numbers.

But his thesis contains the following quote,

"If a branch of an algebraic curve enters a bounded region,

it must necessarily leave again.

Nobody, to my knowledge, has ever doubted this fact."

Warning signs-- buzzers-- should be going off in your brain.

"But if anybody desires it, then on another occasion,

I intend to give a demonstration which will leave no doubt."

So he's using something that he believes to be true.

He sort of thinks it's clear, that everybody knows it.

But he writes this down.

And when you're writing that down,

you know there's a problem.

And in fact, there's another Fields medalist--

we talked about Fields medals last week-- Stephen Smale

writes that this was an immense gap in the proof that was not

filled until 1920-- more than 100 years later.

So Gauss never could give the proof,

and nobody did for over a century more.

Remember the Poincare conjecture from last week?

We had Colbert talking about that.

In 1900, Poincare claimed it was a simple fact.

Four years later, he decided it wasn't so simple,

and he demoted his claim to the status of a conjecture.

And of course, this became the famous Poincare conjecture,

which took another century to solve.

So when you think you see yourself doing this,

famous mathematicians do it too, and it catches them.

So you want to not try to do that.

Now, in fact, just to really bring home the point,

we've made a top 10 list of proof techniques

you should not use in 6.042.

So everybody go to the handout here.

In fact, there's lot of them on the back, too,

but on the front page, there's the top 10.

So we're going to go through these.

These are the ones we've most observed

in 6.042 over the years.

Number 10-- proof by throwing in the kitchen sink.

The author writes down every theorem known to mankind,

and then adds a few more for good measure.

Now, this is good, because when you're questioned later--

you're trying to get a better score on your exam--

you say, look, the proof contains all the key facts.

They're all here.

And so that does help.

You get extra credit if all the facts are there.

We are literally seen students copy over their crib sheet,

if they got enough time, for a problem they're not

knowing how to solve, just to get all of the facts in there.

Number nine-- proof by example-- the author gives the case n

equals 2 and suggests it contains

most of the ideas of the general proof.

In fact, a student before a class

was telling me on one of the homework problems,

he talked about it to his non-math friends,

and they gave examples, not the proof.

Number eight-- proof by vigorous hand-waving-- one

of my favorites-- I get up here and wave my hands.

And it must be true.

Number seven-- proof by cumbersome notation--

here the reader gets hopelessly confused,

gives up, and says OK.

In fact, I once had a grad student,

and we called him the encryptor, because he

could take the simplest proof and so encrypt it in notation

and God knows what, you could never understand the proof

and figure out if it was really right or wrong.

That goes well with number six-- proof by exhaustion--

so does throwing in the kitchen sink.

Number five-- proof by omission--

you will see that a lot, also by faculty-- "The reader

may easily supply the details.

The other cases are analogous-- trivial."

Experts use that all the time.

You can find a lot of my papers online.

"The proof is trivial"-- very bad.

Every once in a while, it turned out not to be so trivial.