The contrapositive.

We look at the technique of proof by contrapositive and give several examples.

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

[goodplacetostop]

2:27 Homework
18:56 Good place to stop

I say it again: I really enjoy this logic playlist. It reminds me the good old days of computer science at university.

[funkygawy]

"If you are not part of the solution, you are part of the problem." So the contrapositive follows: "If you are not part of the problem, then you are part of the solution"

[tusharchetal]

"We suppose n is odd"
n: "hey screw you Michael, I may be a little goofy, but that's totally normal!"

[michaelgian]

Good to see English proper usage describing maths expressions.
As an Engineer needing to get contract wording set-in-stone, your maths proof course has impact well beyond its specific intent.

[marcustulliuscicero]

You seem like a wonderful teacher Michael!

[inGuy]

Michael: A minor nit but when you compare which approach is easier, the comparison should be between P and (not Q), rather than P and Q. ie if P is simpler than not Q, do the direct proof. If not Q is simpler than P, prove by contrapositive. This would be because not Q may be either much simpler or harder than Q when Q is a complex expression.

[julimate]

Loved the video, wish it existed two years ago when I was learning this, love you videos, there's never a good place to stop watching them.

[thecustomer]

This video came at the perfect time for me. I'm taking a course in Discrete Mathematics and this'll be great help to me!

[orenfivel]

@Michael Penn, nice video.
BTW, what's the difference between proof by contrapositive and proof by contradiction?

[MrRyanroberson]

Actually you can still do modulo by negative numbers, you just get identical results. The only constraint is n is not 0 since 0 divides nothing

[noahtaul]

Direct proofs and contrapositive proofs both have a bit of a deficiency. If you're trying to prove sqrt(2) is irrational, for example, you can let P="x^2=2" and Q="x =/= p/q for all p, q". Both P->Q and ~Q->~P are hard to prove because they both end with "something =/= something else", but you're only starting with "something = something else". A third way, proof by contradiction, is of the form P & ~Q -> contradiction, and is much easier to work with in this case and many others. Here, proof by contradiction starts with "x^2=2 and x=p/q" and ends with "Contradiction".

The difference between the three is what information you're starting with and able to immediately use. With direct and contrapositive proofs, you have only one piece of information among P and ~Q that you're allowed to start with, but with contradiction proofs, you're allowing yourself to use both. Sometimes you can work your way from P to Q or from ~Q to ~P without having to use the other piece, as Michael did in these videos, but it feels like a very artificial handicap to place on yourself and only allow yourself one thing you're allowed to use as opposed to both.

And direct and contrapositive proofs can be formulated as contradiction proofs anyway, where the contradiction is "We ended at Q (or ~P), but we also assumed ~Q (or P), so contradiction", so every proof can be thought of as a proof by contradiction. Direct and contrapositive proofs are just the proofs that have the special property that they didn't need to use ~Q or P throughout the course of the proof until the last step.

That said, there's something clean about reading a direct proof or a contrapositive proof that isn't phrased as a proof by contradiction, since you're taking one step at a time, always moving forward, instead of pulling information back from the beginning, and you end with a true statement, not a contradiction.

[prithujsarkar]

Thanks! this video was much needed, i often make mistakes (which i think is quite common) when converting a statement into its contrapositive form, like if P \implies Q then sometimes i make mistake by writing In P does not happen then Q happens neither which is totally wrong, now i get it fully :D

[nathanisbored]

i dont understand how the truth table works at 2:45... why is it true that if both P and Q are true, then P must imply Q? what if they are two unrelated statements, like "there are infinitely many primes" and "2 + 2 = 4"? then P is true and Q is true, but P implies Q is false, no?

[animeniacthephysicist]

Where can I find the earlier vides of this proof writing course?

[dickson]

Please Help, i don't know how to prove this but i have no counterexample
Prove that every rational number could be written as sum of three rational cube

[elgourmetdotcom]

Then proof by Contrapositive is basically the same as proof by Contradiction, right?

[peterklenner]

The truth of a false statement implying another false statement trips me all the time.

[canalMatUem]

A tabela verdade mostra a equivalência. Fiz um vídeo de lógica da vava voadora, veja lá. Paradóxo. Brasil.

[mikecaetano]

If the flower is not yellow and the grass is not green, then the flower is not made of grass and the grass is not made of flower. The flower is made of grass and the grass is made of flower. Therefore the flower is yellow and the grass is green. If the flower is yellow and the grass is green, then the flower is made of grass and the grass is made of flower. The flower is yellow and the grass is green. Therefore the flower is made of grass and the grass is made of flower.