1
00:00:00,000 --> 00:00:03,600
We can talk about negating quantifiers. 
These ones that I used in class,

2
00:00:03,600 --> 00:00:06,300
everyone in this room 
is born before 2010.

3
00:00:06,300 --> 00:00:09,966
Somebody in this room was not 
born before 2010, that's the negation,

4
00:00:09,966 --> 00:00:12,166
someone in this room 
is born before 1990,

5
00:00:12,166 --> 00:00:15,266
the negation is: everyone in this 
room was born after 1990.

6
00:00:15,266 --> 00:00:17,733
So what am I trying
to emphasize here?

7
00:00:17,733 --> 00:00:21,400
I'm trying to emphasize 
the “everybody” to “somebody”.

8
00:00:21,400 --> 00:00:23,800
Everybody should, in your 
mind, mean “for all”.

9
00:00:23,800 --> 00:00:26,900
Somebody means “there 
exists”, there's somebody.

10
00:00:26,900 --> 00:00:29,966
I started with somebody, or
someone, in this room

11
00:00:29,966 --> 00:00:33,400
that's a “there exist” statement. What’s 
the negation of a “there exists” statement?

12
00:00:33,400 --> 00:00:36,333
It's an “everybody” statement, 
it’s a “for all” statement, okay?

13
00:00:36,333 --> 00:00:38,633


14
00:00:38,633 --> 00:00:40,133
Here's two 
more examples,

15
00:00:40,133 --> 00:00:41,933
so now let's do this mathematically. 
If I have for all x

16
00:00:41,933 --> 00:00:44,900
inside the real numbers, the absolute
value of x is less than 5.

17
00:00:44,900 --> 00:00:46,666
What's the negation 
of that? 

18
00:00:46,666 --> 00:00:49,200
Well the negation is 
there exists a real number,

19
00:00:49,200 --> 00:00:52,566
such that the absolute value of 
x is greater than or equal to 5.

20
00:00:52,566 --> 00:00:56,000
Remember that equality has to come 
here because it wasn't in the original.

21
00:00:56,000 --> 00:00:59,366
The negation of a “less than” 
is a “greater than or equal to”.

22
00:00:59,366 --> 00:01:02,066
Number four: there exists 
a real number x such

23
00:01:02,066 --> 00:01:04,933
that the absolute value of 
x is less than or equal to 5.

24
00:01:04,933 --> 00:01:06,466
What's the 
negation of that?

25
00:01:06,466 --> 00:01:08,100
For all real
numbers x, the

26
00:01:08,100 --> 00:01:10,500
absolute value of x is
greater than 5.

27
00:01:10,500 --> 00:01:12,466
Here the equality was in 
here, so the negation of

28
00:01:12,466 --> 00:01:16,000
“a less than or equal to” 
is strictly “greater than”.

29
00:01:16,000 --> 00:01:18,100
That's negating quantifiers, 
that's basically it.

30
00:01:18,100 --> 00:01:20,000
So notice that the domains 
stay the same, something

31
00:01:20,000 --> 00:01:23,100
to keep in mind, you don't negate the 
domain or do something crazy with that.

32
00:01:23,100 --> 00:01:26,433
Leave that alone, just 
negate the quantifier.

33
00:01:26,433 --> 00:01:28,333


34
00:01:28,333 --> 00:01:34,033
Nesting quantifiers, I believe this is the 
last thing I want to talk about… it is. 

35
00:01:34,033 --> 00:01:35,733
What's the point of nesting 
quantifiers? Well the

36
00:01:35,733 --> 00:01:38,166
order of quantifiers 
matters, okay?

37
00:01:38,166 --> 00:01:40,866
The order in which 
you do things

38
00:01:40,866 --> 00:01:43,433
influences whether or not
the statement’s true or false.

39
00:01:43,433 --> 00:01:45,500
So let's look at these four examples 
and these are basically the

40
00:01:45,500 --> 00:01:48,266
four examples that you can 
have for this problem:

41
00:01:48,266 --> 00:01:51,400
so, “For all real numbers x 
and for all real numbers of y,

42
00:01:51,400 --> 00:01:53,433
x cubed minus y 
cubed equals 1.”

43
00:01:53,433 --> 00:01:56,633
So hopefully that immediately just 
sounds ridiculous, right? I mean

44
00:01:56,633 --> 00:01:58,966
for every single real 
number x and y,

45
00:01:58,966 --> 00:02:01,466
the difference of cubes 
is 1? That can't be true.

46
00:02:01,466 --> 00:02:04,500
A simple counter example 
is x equals y equals 0.

47
00:02:04,500 --> 00:02:08,400
The second one: “There 
exists a real number x

48
00:02:08,400 --> 00:02:12,300
and there exists real number y such 
that x cubed minus y cubed equals 1,”

49
00:02:12,300 --> 00:02:15,833
and that's true, right? You get to 
actually pick your x and y here.

50
00:02:15,833 --> 00:02:17,900
So I'm gonna pick x 
equals 1 and y equals 0,

51
00:02:17,900 --> 00:02:19,800
that's definitely a 
good enough proof. 

52
00:02:19,800 --> 00:02:24,200
You can pick many other ones, but that'll 
work and that's the easiest one I think.

53
00:02:24,200 --> 00:02:25,800
What about the 
third one:

54
00:02:25,800 --> 00:02:29,466
“For all real numbers x, there exists
a real number y such that

55
00:02:29,466 --> 00:02:32,233
x cubed minus
y cubed equals 1.” 

56
00:02:32,233 --> 00:02:33,666


57
00:02:33,666 --> 00:02:37,200
For all real numbers x… so 
I give you a real number x,

58
00:02:37,200 --> 00:02:40,200
can you find a real 
number y that

59
00:02:40,200 --> 00:02:42,100


60
00:02:42,100 --> 00:02:44,000
works for the 
given x,

61
00:02:44,000 --> 00:02:46,200
such that x cubed minus 
y cubed equals 1.

62
00:02:46,200 --> 00:02:48,166
So this is where 
the order is important.

63
00:02:48,166 --> 00:02:51,733
You're given the x first, and you 
can choose the y depending

64
00:02:51,733 --> 00:02:54,733
on the x that you
were given, okay?

65
00:02:54,733 --> 00:02:56,966
So in this case, it's
going to be true. Why?

66
00:02:56,966 --> 00:03:00,000
So start with 
an arbitrary x 

67
00:03:00,000 --> 00:03:03,366
and pick y to 
depend on x, okay?

68
00:03:03,366 --> 00:03:06,033
So y is gonna be the cube 
root of x cubed minus 1

69
00:03:06,033 --> 00:03:09,333
y is allowed to depend on x because 
it appears later in the statement.

70
00:03:09,333 --> 00:03:11,200
Then if I plug that in…by the way, 
where does this come from?

71
00:03:11,200 --> 00:03:13,600
This y equals the cube 
root of x cubed minus 1?

72
00:03:13,600 --> 00:03:15,800
Just solve for y in
the expression.

73
00:03:15,800 --> 00:03:20,000
And if you plug it in then you 
see that equality is satisfied.

74
00:03:20,000 --> 00:03:21,733
So three is 
[true] too.

75
00:03:21,733 --> 00:03:23,600
Now what about 
four though? So

76
00:03:23,600 --> 00:03:27,433
if I flip the quantifiers, 
“There exists an x,

77
00:03:27,433 --> 00:03:31,033
a real number x, such that
for all real numbers y, x cubed

78
00:03:31,033 --> 00:03:33,200
minus y cubed 
equals 1.”

79
00:03:33,200 --> 00:03:36,366
So there's some x 
such that for every

80
00:03:36,366 --> 00:03:39,500
single y I pick, x cubed 
minus y cubed equals 1.

81
00:03:39,500 --> 00:03:42,466
Hopefully that to you sounds 
ridiculous, right, I mean,

82
00:03:42,466 --> 00:03:45,166
so there's some
magical x

83
00:03:45,166 --> 00:03:49,500
that every single y value makes x 
cubed minus y cubed equals 1? 

84
00:03:49,500 --> 00:03:50,966
That doesn't 
sound right.

85
00:03:50,966 --> 00:03:55,600
It sounds like you have a 
way too much freedom… 

86
00:03:55,600 --> 00:03:57,800
there's no way 
that…I mean

87
00:03:57,800 --> 00:04:00,666
1 is fixed and somehow 
x cubed is fixed,

88
00:04:00,666 --> 00:04:04,533
so y cubed should probably be
fixed, that's sort of the intuition here.

89
00:04:04,533 --> 00:04:08,433
But how do you disprove this? How do 
you write a formal disproof of this fact?

90
00:04:08,433 --> 00:04:10,866
So you're disproving a 
“there exists” statement,

91
00:04:10,866 --> 00:04:13,166
negate it, and 
prove the negation.

92
00:04:13,166 --> 00:04:15,800
So the negation of this is…
well how do we do it?

93
00:04:15,800 --> 00:04:19,266
Bring the negation in, so negated “there
exists” that becomes a “for all”,

94
00:04:19,266 --> 00:04:21,200
negate a “for all” that 
becomes a “there exists”,

95
00:04:21,200 --> 00:04:24,966
leave the domains the same, and 
instead of an equality here, you put

96
00:04:24,966 --> 00:04:28,666
an inequality here. So 
not equals to, okay?

97
00:04:28,666 --> 00:04:31,800
So proof, what's 
the proof?

98
00:04:31,800 --> 00:04:34,000
I should say…yeah so
what's the proof?

99
00:04:34,000 --> 00:04:36,000
Let x, an element 
of R, be arbitrary,

100
00:04:36,000 --> 00:04:39,000
so I pick some 
x inside R,

101
00:04:39,000 --> 00:04:41,366
now I need to find 
some y such that

102
00:04:41,366 --> 00:04:44,000
they're not equal to 1. Well
just take y equals x, right?

103
00:04:44,000 --> 00:04:47,000
I can pick y now because 
once I've negated it and I

104
00:04:47,000 --> 00:04:48,400
I start with 
my x,

105
00:04:48,400 --> 00:04:51,600
I get to choose y depending 
on x in this setting.

106
00:04:51,600 --> 00:04:56,000
Then x cubed minus y cubed is equal to x cubed 
minus x cubed, which is 0 which is not 1.

107
00:04:56,000 --> 00:05:00,233
That’s the idea. So the negation 
is true, so the original is false.

108
00:05:00,233 --> 00:05:03,166
Notice the difference here, so three 
and four look very similar, right,

109
00:05:03,166 --> 00:05:05,966
I've just changed the order of 
the “for all” and the “there exists”,

110
00:05:05,966 --> 00:05:08,533
but it matters 
because

111
00:05:08,533 --> 00:05:09,700


112
00:05:09,700 --> 00:05:11,533
the x cannot 
depend on the y.

113
00:05:11,533 --> 00:05:14,366
The y can depend on the x, but 
the x cannot depend on the y.

114
00:05:14,366 --> 00:05:17,033
In this case, really, y can't depend 
on anything because it's for all y,

115
00:05:17,033 --> 00:05:20,366
so I mean you have to show this 
is true for every single value of y. 

116
00:05:20,366 --> 00:05:22,233


117
00:05:22,233 --> 00:05:24,366
And that is
nesting quantifiers.

118
00:05:24,366 --> 00:05:26,866
Okay, so order matters. Get a 
little bit of practice, again,

119
00:05:26,866 --> 00:05:28,433
doing assignments is
probably the best way,

120
00:05:28,433 --> 00:05:31,033
doing practice problems, all 
those sorts of things.

121
00:05:31,033 --> 00:05:34,633
Ask questions, post on Piazza. If you 
have any questions, let me know.

122
00:05:34,633 --> 00:05:37,300
Hopefully this was helpful. Hopefully 
this gave you some insight into

123
00:05:37,300 --> 00:05:39,633
week 2’s concepts,

124
00:05:39,633 --> 00:05:43,666
and hopefully you join me for week 
3. Thank you and good luck.