We can talk about negating quantifiers. These ones that I used in class,
everyone in this room is born before 2010.
Somebody in this room was not born before 2010, that's the negation,
someone in this room is born before 1990,
the negation is: everyone in this room was born after 1990.
So what am I trying to emphasize here?
I'm trying to emphasize the “everybody” to “somebody”.
Everybody should, in your mind, mean “for all”.
Somebody means “there exists”, there's somebody.
I started with somebody, or someone, in this room
that's a “there exist” statement. What’s the negation of a “there exists” statement?
It's an “everybody” statement, it’s a “for all” statement, okay?
Here's two more examples,
so now let's do this mathematically. If I have for all x
inside the real numbers, the absolute value of x is less than 5.
What's the negation of that?
Well the negation is there exists a real number,
such that the absolute value of x is greater than or equal to 5.
Remember that equality has to come here because it wasn't in the original.
The negation of a “less than” is a “greater than or equal to”.
Number four: there exists a real number x such
that the absolute value of x is less than or equal to 5.
What's the negation of that?
For all real numbers x, the
absolute value of x is greater than 5.
Here the equality was in here, so the negation of
“a less than or equal to” is strictly “greater than”.
That's negating quantifiers, that's basically it.
So notice that the domains stay the same, something
to keep in mind, you don't negate the domain or do something crazy with that.
Leave that alone, just negate the quantifier.
Nesting quantifiers, I believe this is the last thing I want to talk about… it is.
What's the point of nesting quantifiers? Well the
order of quantifiers matters, okay?
The order in which you do things
influences whether or not the statement’s true or false.
So let's look at these four examples and these are basically the
four examples that you can have for this problem:
so, “For all real numbers x and for all real numbers of y,
x cubed minus y cubed equals 1.”
So hopefully that immediately just sounds ridiculous, right? I mean
for every single real number x and y,
the difference of cubes is 1? That can't be true.
A simple counter example is x equals y equals 0.
The second one: “There exists a real number x
and there exists real number y such that x cubed minus y cubed equals 1,”
and that's true, right? You get to actually pick your x and y here.
So I'm gonna pick x equals 1 and y equals 0,
that's definitely a good enough proof.
You can pick many other ones, but that'll work and that's the easiest one I think.
What about the third one:
“For all real numbers x, there exists a real number y such that
x cubed minus y cubed equals 1.”
For all real numbers x… so I give you a real number x,
can you find a real number y that
works for the given x,
such that x cubed minus y cubed equals 1.
So this is where the order is important.
You're given the x first, and you can choose the y depending
on the x that you were given, okay?
So in this case, it's going to be true. Why?
So start with an arbitrary x
and pick y to depend on x, okay?
So y is gonna be the cube root of x cubed minus 1
y is allowed to depend on x because it appears later in the statement.
Then if I plug that in…by the way, where does this come from?
This y equals the cube root of x cubed minus 1?
Just solve for y in the expression.
And if you plug it in then you see that equality is satisfied.
So three is [true] too.
Now what about four though? So
if I flip the quantifiers, “There exists an x,
a real number x, such that for all real numbers y, x cubed
minus y cubed equals 1.”
So there's some x such that for every
single y I pick, x cubed minus y cubed equals 1.
Hopefully that to you sounds ridiculous, right, I mean,
so there's some magical x
that every single y value makes x cubed minus y cubed equals 1?
That doesn't sound right.
It sounds like you have a way too much freedom…
there's no way that…I mean
1 is fixed and somehow x cubed is fixed,
so y cubed should probably be fixed, that's sort of the intuition here.
But how do you disprove this? How do you write a formal disproof of this fact?
So you're disproving a “there exists” statement,
negate it, and prove the negation.
So the negation of this is… well how do we do it?
Bring the negation in, so negated “there exists” that becomes a “for all”,
negate a “for all” that becomes a “there exists”,
leave the domains the same, and instead of an equality here, you put
an inequality here. So not equals to, okay?
So proof, what's the proof?
I should say…yeah so what's the proof?
Let x, an element of R, be arbitrary,
so I pick some x inside R,
now I need to find some y such that
they're not equal to 1. Well just take y equals x, right?
I can pick y now because once I've negated it and I
I start with my x,
I get to choose y depending on x in this setting.
Then x cubed minus y cubed is equal to x cubed minus x cubed, which is 0 which is not 1.
That’s the idea. So the negation is true, so the original is false.
Notice the difference here, so three and four look very similar, right,
I've just changed the order of the “for all” and the “there exists”,
but it matters because
the x cannot depend on the y.
The y can depend on the x, but the x cannot depend on the y.
In this case, really, y can't depend on anything because it's for all y,
so I mean you have to show this is true for every single value of y.
And that is nesting quantifiers.
Okay, so order matters. Get a little bit of practice, again,
doing assignments is probably the best way,
doing practice problems, all those sorts of things.
Ask questions, post on Piazza. If you have any questions, let me know.
Hopefully this was helpful. Hopefully this gave you some insight into
week 2’s concepts,
and hopefully you join me for week 3. Thank you and good luck.