Types of implications. So we've seen these
sort of implicitly throughout the course,
but we're gonna make a point right now to just go over the
ways we can use ‘and’s and ‘or’s and hypothesis and the conclusion
and how we prove these things.
So statement one was: “A and B implies C.”
This we saw in…we've already seen this.
We've seen this Divisibility of Integer Combinations, we've seen this
in Bounds By Divisibility.
Remember DIC was, “a implies c and b implies c implies that…”
or a divides, sorry… “a divides b and a divides c,
implies that a divides an integer linear combination of b and c.” Okay?
So when we proved it, we assumed that a
divided b and a divided c,
and when we use it, we prove that a divides b and a divides c.
So second one: “ A implies B and C.” So what does this mean?
Well when we're trying to prove this, we're starting with A,
we're assuming A and we're trying to show that both B and C are true,
and when we're using it we're proving A, and we get both B and C as being true for free.
So as an example, let S, T, and U be sets.
If S union T is inside U, then S is inside U and T is inside U.
So again, this is sort of a “follow your nose” type of proof.
You start with the hypothesis,
well and what are we trying to show? Let's start by showing S is inside U.
Take an arbitrary element of S, it must be in the union,
the union’s inside U, therefore every element of S is in U,
and we argue similarly for T inside U.
It’s the first time we saw the word “similarly” in class.
Round three: "A 'or' B implies C."
This is actually a little bit subtle, okay,
which we'll see in a minute. So using this, you either start with
A being true, or B being true, and then you get C for granted.
Proving this... what do we need to do to prove this?
Well let's take a look at this example.
The example will kind of help us out here:
“x equals 1 or y equals 2 implies that
this polynomial equation [with] x and y is equal to 2.”
How do we prove this?
We start by assuming the hypothesis is true,
and the hypothesis is x equals 1 or y equals 2.
Well what does it mean for an ‘or’ statement to be true?
Well it means that at least one of these two things is true,
but the question is which one?
And the answer to that is you don't know. You don't know which
which one of these two facts is true, so you have to start with the one fact,
so start with x equals 1,
and prove that that alone implies this equation is true.
And then start with y equals 2,
use that alone to prove that this equation is true, okay?
So you have to do…
it's not just one thing. You have to do both things here, okay?
You have to start with x equals 1, and prove the conclusion is true,
then start with y equals 2 and prove the conclusion is true, okay?
The last thing
that I want to talk about is part four, which is elimination.
This one's an important one as well.
“A implies B or C”, so
the way we can do this is we can eliminate one of the possibilities.
Why can we do that? Well A implies B 'or' C. Well...
so we're gonna take A for granted, and if B were true, then we'd be done, right,
because then the conclusion is true and so the implication is true.
So instead of
trying to prove B 'or' C, what we're going to do is
we're going to take ‘not’ B as part of our hypothesis as well.
And again why can we do that? If B is true, we’re done the question.
So we might as well assume that B is false.
If B is false, then the negation of B is true.
So start with A and ‘not’ B.
If you want you can prove this by, again,
logical equivalences things, like that,
but I like that sort of case analysis in your head.
You should be able to do that in your head by now.
So let's see an example: “if x squared minus 7x plus 12 is greater than or equal to 0,
then x is less than or equal to 3 or x is greater than or equal to 4.”
Let me also note:
you don't have to use elimination to solve this problem.
It just makes life a little bit easier and cleaner if you do.
What does elimination say? Well I'm going to take one of these two facts,
I'm gonna start with the first one just because, and take the negation of that as being true.
So suppose that my hypothesis is true and that x is greater than 3;
the negation of one of my two statements in the conclusion.
Then 0 is bounded below by this polynomial
and that polynomial factors as x minus 3 and x minus 4.
Since x minus 3 is greater than 0, we know that
x minus 4 must also be greater than or equal to 0,
since the product is greater than or equal to 0,
and hence x is greater than or equal to 4.
So that's the idea behind an elimination. You take one of the terms…
you take the negation of one of the terms of the conclusion as true.
Contradiction, so proof by contradiction.
This generalizes a proof by contrapositive.
So if you never use contrapositive, you're not going to lose anything
in terms of sanity. You should know what the word contrapositive means.
There's lots of “C” words: contrapositive, contradiction, converse.
Make sure that you have them all organized,
but in terms of like actually leaving this course, if you
always use contradiction instead of contrapositive,
you're not losing any strength. You're not like missing a proof technique sort of thing.
So something to keep in mind, but for the purposes of this course,
you should know what both of these words mean.
That being said, what is a proof by contradiction?
Well let S be a statement then S and ‘not’ S is false, okay?
That sounds really obvious that one of S
or the negation of S is true and the other one is false. It seems really clear, but
it's something to keep in mind.
How do we use this? How does this actually help us?
A really obvious statement but it does help us a lot.
What do we do? Well we're going to assume the hypothesis is true,
and we're going to assume towards a contradiction that
the negation of the conclusion is also true,
so we get the hypothesis and the negation of the conclusion.
Now what are we gonna do? Well we're going to break math. What does that mean?
So to break math involves...
basically involves this: it involves finding a
statement such that S and its negation is true.
What that statement is, it's not necessarily obvious
when you start, but as you go through the proof you
usually know when you’ve broken math in some way, shape, or form.
Once you do that, you conclude the conclusion must be true, right?
Only one of the negation or
itself is true, and so if the negation was false...
the negation being true led to a contradiction, then the original conclusion must be true.
Example of a contradiction so you use it in the same
situations that you would consider using contrapositive.
Here's an example: “Prove that the square root of 2 is irrational.”
So contrapositive you need to use for implications, contradiction well…
it's a little bit more general.
It helps you out in situations like this where you don't have
a visible implication.
So here we go. So prove that root 2 is irrational.
So proof: “Assume towards a contradiction that the square root of 2 is rational,”
right? Being irrational is a difficult condition to deal with.
Being rational is an easy condition to start manipulating.
So we're going to assume towards a contradiction that square root of 2
is equal to a over b, which is rational,
and here though we're gonna get a little bit more. We are going to also
assume that a and b are natural numbers instead of just integers.
Why can we do that?
Stop and think about this and say, “Okay well root 2 is positive.
So if it's positive, then I know that a over b
is a positive number, so I might as well assume that both a and b are positive.
If they were both negative… that's a possibility but
then you can just cancel the negatives, and get something
where both terms are positive,
and we already know that b is not 0
and we know that a is not 0 because root 2 is bigger than 0.
Okay, we have all of those facts we are allowed to assume,
in this case, that a and b are natural numbers.
You should write this down in your proof. I'm not going to
because I want to fit on this slide.
“Assume further that a and b share no common factor,” right?
If they did share a common factor, then you could simplify the fraction
before declaring what a and b were, okay?
So we're also going to do that.
“Then cross multiplying and squaring gives us that 2b squared equals a squared,”
and what does that mean? Well it means that
a squared must be even, and hence a is even, okay?
So if a squared is even, then we know that a is even,
we saw that in class this week as well.
You can check that out in lecture 10.
So write a equals 2k for some integer k,
then substitute that into a squared is equal to 2b squared. What do we get?
So we get 2b squared is equal to… plugging it in… 4k squared.
Canceling a 2 shows that b squared is equal to k squared and then, once again,
b squared is even, hence b is even.
Well a is even and b is even, so that means that
share a common factor, namely 2, and that's a contradiction.
Okay?
So what did we contradict? Well we said that a and b
had no common factor,
but here we've shown that a and b have a common factor.
So my statement is: “a and b share no common factor.”
Well I've shown that S and ‘not’ S were both true.
So S and ‘not’ S is true, well that's a contradiction. That doesn't make sense.
So because I broke math, because I've reached a contradiction,
I conclude that the thing that I assumed was false.
I assumed that root 2 was rational so therefore square root of 2 is irrational.
Should you include a concluding sentence, “therefore the square root of 2 is irrational”?
It's good form, I didn't here. you should probably do it.
Do what I say not what I do.