So quantified statements. So this week, we talked about two quantified statements.
We saw them a bit last week and a bit in the past,
but now we're going to formally do them. So we saw
the upside down A and the inverted E.
Upside down A means “for all”, the inverted E means “there exists”.
So two examples in class that we did.
“Prove that for all natural numbers n,
2n squared plus 11n plus 15 is composite.”
So how do we do that? Well we start our proof…
well so we're proving a “for all” statement,
so start with an arbitrary element of the “for all” statement,
and then show the second half.
Show that 2n squared plus 11n plus 15 is composite,
with an arbitrary n.
How did we do that? Well it's similar to our assignment
problem that we had in Assignment 1, we factor.
So we factor, we show that both of the factors
are bigger than 1 because n is a natural number,
and thus that 2n squared plus 11n plus 15 is composite.
Here's an example of a “there exists” statement that we're gonna prove.
“Prove there exists an integer k such that 6 equals 3k.”
How do we do this? Well we're proving a "there exists" statement,
so all we need to do is find such a k.
Now, it is possible to prove existence statements without actually finding one.
Hopefully we won't see that in this course. [We] might but I doubt it.
Here though, we can just specifically find the k that makes this work,
and the k that's gonna work is actually 2. Since 3 times 2 is 6,
we see that k equals 2 satisfies the given statement.
And that's it.
So for proving “there exists” statements,
it's enough to actually physically find an example.
Proving a “for all” statement, you have to actually go through
an arbitrary proof, like this.
We'll see this in a couple slides.
This is something that trips students up
a lot, so I'd like to talk about it here.
Assuming a “for all” statement, okay? So let's look at this statement:
“Let a, b, c be integers, if for all x in the integers
a divides b x plus c, then a divides b plus c.”
Now setting up this proof is… the first line’s very sort of…
dry. It's obvious.
If hypothesis, then conclusion. So assume the hypothesis.
Now what you have to tell yourself is,
"What does this mean that I'm assuming the hypothesis?"
So I'm assuming that the statement,
“for all integers x, a divides b x plus c” is true.
I'm assuming this is true,
that means if I plug in any value for x,
this is going to be a true statement.
What values can I plug in? If I plug in let's say x equals 0,
then what do I learn? I learn that a divides c.
If I plug in x equals 10, what do I learn?
Well I learn that a divides 10b plus c.
And for all values of x that you plug in,
you're gonna get a statement - a divisibility criteria - from that.
In particular, how do we show that a divides b plus c?
Well let's pick a good value of x,
and it turns out that a good value of x to pick is 1.
So I can plug in 1 because I know that this “for all” statement is true.
I'm given the “for all” statement.
So I know that's true for x equals 1, and when I plug that in
I should get that a divides b plus c.
This is important. This is a little bit subtle.
Assuming a “for all” statement. You're assuming that a “for all” statement is true
so you can plug in values and you can take that for granted.
Domain is important. So let's look at the example:
P(x) being the statement, “x squared equals 2”
and we're gonna let S be the set “plus or minus root 2”.
Which of the following are true:
there exists an integer such that P(x) is true,
for all integers x, P(x) is true,
there exists a real number such that P(x) is true,
for all real numbers P(x) is true,
there exists an x inside S such that P(x) is true,
and for all x inside S, P(x) is true.
How do we prove this?
Which of the following are true?
So we know that over the reals, the only values
that make this true are plus or minus root 2.
So are there integers where P(x) is true? Well no.
The only ones are the irrational numbers plus or minus root 2.
Well for all integers is P(x) true,
Right? I mean 0, for example, 0 squared [doesn't] equal 2.
Let's look at the real numbers now. Is here a real number that makes this true?
The answer is yes. Well square root of 2 makes it true.
Now let's look at number 4, well is it true for
all real numbers x that P(x) is true?
That's false, right? I mean 0, again, is a counterexample.
0 is a real number
and 0 squared equals 2 is a false statement.
But what about for S? Well there exists an x in S such that
P(x) is true, that's true. There's root 2, for example.
Part 6, for all x inside S, P(x).
Well that's also true, S only has two elements:
plus or minus root 2, and they're both roots
of x squared minus 2 equals 0.
6 is going to be true.
So here's an example - this actually gives you all the combinations.
So something to think about,
just a little bit, can I find one where there exists a set T such that
P(x)… that's true
and for all x inside T, P(x) that’s…
so can I find one where the first one is false and the second one is true?
So if there exists an x inside T such that P(x), that's false,
and for all x inside T, P(x) is true.
Think about why that can't happen. It can't happen,
and if you think about it you'll see why.
So this basically gives all the possibilities.
A couple of final things to end off with so
approaching quantified statement problems.
So what do we want to say here?
We're gonna go through the four possibilities. So a single counter example
shows that for all x inside S, P(x) is false.
So if I want to disprove a “for all” statement,
all I need to do is find a counter example.
So here's an example: “Every even positive integer is composite”, that's false.
2 is even, but 2 is not composite, 2 is prime.
Part 2,
a single example does not prove that
for all x inside S, P(x) is true.
If you want to prove this just like we did a couple slides ago,
you have to prove it for all elements of S.
So here's an example: “Every even integer at least four is composite.”
This is true but we cannot prove it by saying,
"Well 6 is an even integer and it's composite, so I'm done."
You can't do that, okay?
That's not enough, right,
because there are lots of even integers that aren't 6,
and that are at least 4.
To prove that this is true, you must show that this is true
for an arbitrary even integer x greater than or equal to 4.
So what's the idea? Well
2 divides x so there exists a natural number k
such that 2k equals x and k is not 1.
You can do this to show that the number must be composite, it's divisible by 2.
The two factors… and the two factors are greater than 1.
Let's look at another one. So a single example does show that
there exists an x inside S, P(x) is true.
Claim: “some even integer’s prime”, right?
There exists an even integer such that it is prime.
That claim’s true because 2 is even and 2 is prime.
So there's an example of a “there exists” statement being true.
And then, the last one is sort of the trickiest one.
What about showing there exists an x inside S such that P(x)
is false? How do we do that?
It turns out the easiest way I like to think about this, is you
actually negate this and we'll talk about negating quantifiers in the next slide,
but if you negate this,
what has to happen? Well the negation of this must be true.
What's the negation of a “there exists” statement? It's a “for all” statement.
For all x inside S, not P(x) is true,
is equivalent to saying there exists an x inside S such that P(x) is false.
So this sort of logical equivalence here is actually a
big big hint for solving this type of problem.
We'll see this is central in the idea of proof by contradiction,
which we'll see next week,
but I thought I'd mention it here and it seems like a really natural point to do so.