Hi. I'm Vladimir Podolski.

And today, we are going to discuss reductio ad absurdum or proof by contradiction.

So, how can they prove that something is true?

One way to do it is to show that the opposite is impossible.

Indeed, if you have a statement and the opposite of a statement is impossible,

then your statement must be true.

And this method is called "reductio ad absurdum" or proof by contradiction.

This is one of the base methods of reasoning.

It is used everywhere.

And it is often combined with other methods.

And we will use it a lot for our courses.

So, we will discuss these methods in this lesson extensively.

So, reductio ad absurdum is a classical method.

It is as old as logic.

And one early example is "Socratic Method," in books by Plato.

Socrates did the following.

He talked to his students and he revealed contradictions

in the beliefs of his students just asking them questions, question by question.

And in this way, he showed that the beliefs of his students are inconsistent.

So, let's consider the following example.

Let's consider the following problem.

There's a class, and there are boys and girls in this class.

And they are divided into two groups for the foreign language.

There are students who study French,

and there are students who study German.

And each student picks one of the two languages.

Now, in this situation,

we need to show that there is a boy and a girl who study different languages.

And this might seem impossible at first.

We know basically nothing,

so we have a completely generic situation.

It is very typical, nothing specific is known,

so we do not know any restrictions,

any useful information, basically.

So, we just have a class there are boys and girls.

There are two languages. And somehow,

we would like to state something nontrivial.

We would like to state that there is a boy and a girl who study different languages.

So, let's proceed to a solution.

We will solve this problem using proof by contradiction.

Suppose that our statement is wrong,

so there are no boy and a girl studying different languages.

So, we have now this assumption.

And we have to get to a contradiction.

So, we have to see, to show that something is wrong now.

And for this, let's consider some girl.

And also, generally, so let's assume that this girl studies French.

It could be German.

It doesn't matter. And so, let's assume it's French.

Now, let's consider some boy.

Even though that there is no pair of boy and the girl studying different languages.

So, if you consider some boy and we consider this girl,

they should study the same language.

So, each boy, you can pick any boy,

and each boy should study French.

So, all boys are studying French.

So, this is already suspicious.

Somehow we have made our assumption.

And somehow it turned out that all boys are learning French now.

But this is not a contradiction yet.

It might be the case.

It might be that all boys decided to learn French. But let's proceed now.

Let's consider some boy now. Let's consider the first boy.

And let's consider some girl.

Since we know, again, by our assumption that there

is no boy and a girl studying different languages,

and the boy studies French,

then this arbitrary girl they're considering is also studying French.

So, this means that all girls are studying French as well.

So, it means that everyone studies French.

So, we've made our assumption,

and now everyone is studying French.

And we know that this is impossible,

because we know that students are divided into groups.

We know there are students that was studying German.

And now we have obtained that everyone studies French.

This is a contradiction.

So, we have made our assumption,

and we arrive at the contradiction.

We have arrived at- We have deduced that no one is studying German.

This is forbidden by the formulation of the problem.

So, our assumption was wrong,

so very general statement was true.

And that's how the proof by contradiction works.

Reductio ad Absurdum

What is a Proof?

与讲师见面