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: Last week we talked about the key components

of a proof, propositions, axioms, and logical deductions,

and as you probably talked about during recitation,

we're not going to worry too much

about what axioms or logical deductions that you use.

Anything that is reasonable, is fine by us.

We're not going to ask you to know what modus ponens is,

or to label some law when you make a logical deduction.

Just, you know, be reasonable.

Any facts you knew coming into this course about mathematics,

probably close enough to use as an axiom.

Want to make sure your axioms are consistent, but that's OK.

Now the exception to this would be, is say we're on an exam,

and we ask you to prove some proposition, p.

Well you can't say, I already knew p, it's an axiom, check.

That's not so good.

We're asking you to prove it from some more

elementary facts.

OK it's also don't want me making wild leaps of faith,

or saying it's obvious that, unless it really is obvious.

That kind of stuff can get you in trouble.

Much better to sort of explain the reasoning in the proof.

Now the proofs that we covered last week in recitation,

the problems set, were all examples

of what are called direct proofs.

You start with some axioms, you have some theorems

you knew before or you proved along the way,

and you make logical deductions until you

get to where you want to go, the theorem.

We're going to start today with an indirect proof.

For example, a proof by contradiction.

And this is a little bit different.

In a proof by contradiction, you assume the opposite

of what you're trying to prove.

Then you just take steps for logical deductions

forward until you arrive at a contradiction,

something where you prove false equals true.

Now if you can ever get to the point

we approve something is false and true,

that means what you assumed at the start had to be wrong.

Namely, what you're trying to prove has to be true.

So let's write that down, because it

can be a little confusing the first time.

So to prove a proposition p is true,

you will assume that it's false.

In other words, that not p is true.

And then you use that hypothesis, namely the p

is false, to derive a falsehood.

In other words, you prove a falsehood is true.

And this is called deriving a contradiction.

And so it must be that, in fact, p is not false,

namely that it's true.

Now this works because if you can prove,

if not p implies false is true, well from last time,

the only way this is a true statement is if this is false,

namely p is true.

All right?

So we can conclude that p is true,

if we can show that not P implies a falsehood.

Any questions about that?

It's sort of a lot of sort of notation,

and until you've seen, it can be confusing.

So maybe we should do an example.

Let's prove that square root of 2 is irrational.

Is irrational.

OK, everybody knows what an irrational number is?

That's something that can't be expressed

as the ratio of integers.

OK, and probably most people already

know that-- how many people have not

seen a proof that square root of 2 is a rational before?

So most of you have seen a proof of that, good.

You know, if you try to do a direct proof for this,

it's pretty hard.

How do you show there's no way to represent

the square root of 2 is as integers a over b?

But it's very easy, if we do a proof by contradiction.

Now when you're doing a proof by contradiction,

always start off by saying, by contradiction.

Write that down.

And then what you do next is you say,

I'm going to assume, for the purpose of contradiction,

that p is false and when not p is true.

In this case, that would be square root of 2 is rational.

So in this case, here's what we're trying to prove.

That's p.

I'm going to assume not p, namely that square root of 2

is irrational number.

Then I'm going to get a contradiction or falsehood,

and then I'm going to know that p was true after all.

All right, so let's see where this leads us.

Well, if square root of 2 is rational

then we can express it as a over b, where a over b

is a fraction in lowest terms.

That means a and b have no common divisors.

And then I can square both sides,

and I get two is a squared over b squared.

Then I multiply by b squared, and I get

2b squared equals a squared.

And what does that imply about a?

What can you tell me about a if it equals--

if a squared is 2b squared?

Anything special about a?

Could a be anything?

A squared is even, all right?

Because 2b squared is an even number, so a squared is even,

and what does that mean about a?

A is even.

B squared is even, then a is even.

So a is even.

So we could write that as two divides a.

That's the divide symbol.

You'll see a lot of that next week.

All right if a is even, what do I know about a squared?

I know more than just, it's even.

What is it?

It's multiple of 4, yeah.

So that means that four divides a squared.

A squared is 2b squared, so that means

that four divides 2b squared.

Divide each side by 2 means 2 divides b squared.

What does that imply about b?

B is even.

All right, b is even, good.

Well, I've got a is even and b is even.

I got a contradiction here, somewhere?

Yeah a over b was not a fraction in lowest terms,

because both and b are even.

All right, so that implies a over b is not in lowest terms.

And that is a contradiction.

Now you'll see that written lots of ways.

One is, you can say a contradiction,

sometimes you'll see just this sharp symbol written,

and that means you've got to a contradiction.

Because here, we had it being in lowest terms,

and here we have it not in lowest terms.

You can't have both at the same time,

so you got a contradiction.

And that means we've now proved that this assumption was wrong.

Square root of 2 is not rational,

so it must be irrational.

and then we put a little box here at the end,

or sometimes you'll see a check, sometimes you'll

see QED, that says the proof's done now.

It's over.

Any questions about that proof?

We're going to do a lot of proofs by contradiction.

Actually, there's an interesting story behind this proof.

As far as we know, it was first discovered by the Pythagoreans,

way back when in ancient Greece.

And the Pythagoreans were a religious society

started by Pythagoras, of Pythagoras theorem frame.

Now it sounds weird today, but back then, in ancient Greece,

math was a religion, all right?

Every once in while you'll see somebody around MIT,

and you'll think he must think math is a religion,

but back then it really was, and it was ruled by God,

because this is ancient Greece.

And there were two key gods in this religion, Apeiron

and Peros.

Now Apeiron was the bad god, and he was the god of infinity,

because infinity was considered all that was bad.

And I don't think we'll do a lot with infinity this term,

but if we do you'll appreciate why that's the case.

And Peros was a good god.

He was the god of the finite world,

and represented everything that was good to the ancient Greeks.

Now one of their main axioms, or beliefs,

was that there were no irrational numbers.

They just didn't exist.

Now the reason is, they didn't like irrational numbers.

They were bad.

Because, well they're infinite.

You can't write them as a decimal

without repeating forever, and you know, just an infinite sort

of decimal representation.

They liked rational numbers, you know, like one seventh?

That's a good number, because you can write it

as 0.142857 repeating.

So rational numbers are finite, in that

you can always find a repeating pattern of finite length.

Irrational numbers are not.

They're infinite in that sense of the ancient Greeks.

So they said there were no irrational numbers.

That was an early axiom.

Now they also had an axiom that said

that every length of a line was finite, therefore rational.

All right, you know the ancient Greeks

were good with a compass, and drawing lines

with straight edges and stuff.

So they said any line that you can construct

has a finite length to it, so therefore it

has a rational length.

That was axiom number two.

Now they were good geometers, so they knew, of course,

they developed the Pythagorean theorem.

But if you took a triangle, and you have side lengths one,

the length of the hypotenuse was square root 2.

Therefore they had a theorem that said

square root 2 was rational.

Because you've got the 2 axioms there, right?

Now eventually, they discovered a proof like that,

that it wasn't rational.

It was irrational.

This caused quite a stir.

First it meant that their axioms were inconsistent.

Every theorem they proved was now suspect,

once you have inconsistent axioms.

Even worse, the devil is in their midst.

Square root 2 is infinite is the bad god,

and this is the most basic length they had, besides one.

So that's a very bad thing.

Sort of like, you know, today we were

to wake up and discover that there were only nine

commandments, and the 10th was planted there by the devil.

And you're not sure which one, maybe.

That would be a big mess, sacrilege.

Well, so what were they to do?

This is a disaster of major proportions.

So they covered it up, and they denied the result.

So they didn't want to publish that proof.

So they kept on saying square root 2 was rational.

But then, according to legend there was a Deep Throat.

Somebody who let out the word and the proof the square root 2

is irrational, because that would be very destabilizing

for the society, and so they killed them.

This is the legend.

Now, hard to imagine getting killed

over the irrationality of 2.

All right, we're going to do a lot more

of these kind of proofs in homework

and throughout the term.

The next proof I want to show you

is one of my favorite proof techniques.

One of my favorite proofs.

And that is a false proof.

And we're going to see a lot of these during the term, too.

And if we could bring the screens down.

Somebody back there to-- yeah.