1 00:00:00,000 --> 00:00:03,566 So quantified statements. So this week, 
we talked about two quantified statements. 2 00:00:03,566 --> 00:00:06,200 We saw them a bit last 
week and a bit in the past, 3 00:00:06,200 --> 00:00:08,466 but now we're going to formally 
do them. So we saw 4 00:00:08,466 --> 00:00:11,666 the upside down A 
and the inverted E. 5 00:00:11,666 --> 00:00:14,900 Upside down A means “for all”, the inverted E means “there exists”. 6 00:00:14,900 --> 00:00:16,933 So two examples in 
class that we did. 7 00:00:16,933 --> 00:00:20,000 “Prove that for all 
natural numbers n, 8 00:00:20,000 --> 00:00:22,000 2n squared plus 11n 
plus 15 is composite.” 9 00:00:22,000 --> 00:00:24,233 So how do we do that? 
Well we start our proof… 10 00:00:24,233 --> 00:00:26,100 well so we're proving 
a “for all” statement, 11 00:00:26,100 --> 00:00:30,033 so start with an arbitrary element of the “for all” statement, 12 00:00:30,033 --> 00:00:32,600 and then show 
the second half. 13 00:00:32,600 --> 00:00:35,466 Show that 2n squared plus 
11n plus 15 is composite, 14 00:00:35,466 --> 00:00:37,200 with an 
arbitrary n. 15 00:00:37,200 --> 00:00:38,966 How did we do that? Well it's 
similar to our assignment 16 00:00:38,966 --> 00:00:41,233 problem that we had in Assignment 1, we factor. 17 00:00:41,233 --> 00:00:44,000 So we factor, we show 
that both of the factors 18 00:00:44,000 --> 00:00:46,400 are bigger than 1 because 
n is a natural number, 19 00:00:46,400 --> 00:00:49,666 and thus that 2n squared plus 
11n plus 15 is composite. 20 00:00:49,666 --> 00:00:52,233 Here's an example of a “there exists” 
statement that we're gonna prove. 21 00:00:52,233 --> 00:00:55,733 “Prove there exists an integer k such that 6 equals 3k.” 22 00:00:55,733 --> 00:00:58,533 How do we do this? Well we're 
proving a "there exists" statement, 23 00:00:58,533 --> 00:01:01,100 so all we need to 
do is find such a k. 24 00:01:01,100 --> 00:01:05,366 Now, it is possible to prove existence 
statements without actually finding one. 25 00:01:05,366 --> 00:01:08,800 Hopefully we won't see that in this 
course. [We] might but I doubt it. 26 00:01:08,800 --> 00:01:12,633 Here though, we can just specifically find the k that makes this work, 27 00:01:12,633 --> 00:01:15,633 and the k that's gonna work is 
actually 2. Since 3 times 2 is 6, 28 00:01:15,633 --> 00:01:18,133 we see that k equals 2 satisfies the given statement. 29 00:01:18,133 --> 00:01:19,600 And that's it. 30 00:01:19,600 --> 00:01:21,400 So for proving “there 
exists” statements, 31 00:01:21,400 --> 00:01:23,700 it's enough to actually physically find an example. 32 00:01:23,700 --> 00:01:26,633 Proving a “for all” statement, you 
have to actually go through 33 00:01:26,633 --> 00:01:28,700 an arbitrary proof, 
like this. 34 00:01:28,700 --> 00:01:29,800 35 00:01:29,800 --> 00:01:31,533 We'll see this 
in a couple slides. 36 00:01:31,533 --> 00:01:32,433 We'll see this 
in a couple slides. 37 00:01:32,433 --> 00:01:34,566 This is something that 
trips students up 38 00:01:34,566 --> 00:01:36,133 a lot, so I'd like to 
talk about it here. 39 00:01:36,133 --> 00:01:39,633 Assuming a “for all” statement, okay? 
So let's look at this statement: 40 00:01:39,633 --> 00:01:42,366 “Let a, b, c be integers, if 
for all x in the integers 41 00:01:42,366 --> 00:01:45,433 a divides b x plus c, 
then a divides b plus c.” 42 00:01:45,433 --> 00:01:46,600 43 00:01:46,600 --> 00:01:50,833 Now setting up this proof is… the first line’s very sort of… 44 00:01:50,833 --> 00:01:52,800 dry. It's obvious. 45 00:01:52,800 --> 00:01:56,766 If hypothesis, then conclusion. So assume the hypothesis. 46 00:01:56,766 --> 00:01:58,766 Now what you have to tell yourself is, 47 00:01:58,766 --> 00:02:01,033 "What does this mean that 
I'm assuming the hypothesis?" 48 00:02:01,033 --> 00:02:02,833 So I'm assuming 
that the statement, 49 00:02:02,833 --> 00:02:08,000 “for all integers x, a divides 
b x plus c” is true. 50 00:02:08,000 --> 00:02:09,833 I'm assuming 
this is true, 51 00:02:09,833 --> 00:02:12,366 that means if I plug in 
any value for x, 52 00:02:12,366 --> 00:02:14,666 this is going to be 
a true statement. 53 00:02:14,666 --> 00:02:17,666 What values can I plug in? If I 
plug in let's say x equals 0, 54 00:02:17,666 --> 00:02:20,100 then what do I learn? I 
learn that a divides c. 55 00:02:20,100 --> 00:02:23,033 If I plug in x equals 
10, what do I learn? 56 00:02:23,033 --> 00:02:25,666 Well I learn that a 
divides 10b plus c. 57 00:02:25,666 --> 00:02:28,000 And for all values of 
x that you plug in, 58 00:02:28,000 --> 00:02:31,633 you're gonna get a statement - a divisibility criteria - from that. 59 00:02:31,633 --> 00:02:32,833 60 00:02:32,833 --> 00:02:35,000 In particular, how do we show 
that a divides b plus c? 61 00:02:35,000 --> 00:02:36,766 Well let's pick a 
good value of x, 62 00:02:36,766 --> 00:02:38,966 and it turns out that a good value of x to pick is 1. 63 00:02:38,966 --> 00:02:42,300 So I can plug in 1 because I know 
that this “for all” statement is true. 64 00:02:42,300 --> 00:02:44,433 I'm given the 
“for all” statement. 65 00:02:44,433 --> 00:02:46,900 So I know that's true for x equals 1, and when I plug that in 66 00:02:46,900 --> 00:02:49,233 I should get that 
a divides b plus c. 67 00:02:49,233 --> 00:02:50,800 68 00:02:50,800 --> 00:02:53,366 This is important. This 
is a little bit subtle. 69 00:02:53,366 --> 00:02:56,133 Assuming a “for all” statement. You're assuming that a “for all” statement is true 70 00:02:56,133 --> 00:03:00,000 so you can plug in values and you can take that for granted. 71 00:03:00,000 --> 00:03:02,333 72 00:03:02,333 --> 00:03:05,666 Domain is important. So 
let's look at the example: 73 00:03:05,666 --> 00:03:08,766 P(x) being the statement, “x squared equals 2” 74 00:03:08,766 --> 00:03:11,800 and we're gonna let S be the 
set “plus or minus root 2”. 75 00:03:11,800 --> 00:03:14,433 Which of the following 
are true: 76 00:03:14,433 --> 00:03:17,500 there exists an integer 
such that P(x) is true, 77 00:03:17,500 --> 00:03:20,000 for all integers 
x, P(x) is true, 78 00:03:20,000 --> 00:03:22,500 there exists a real number 
such that P(x) is true, 79 00:03:22,500 --> 00:03:25,333 for all real numbers 
P(x) is true, 80 00:03:25,333 --> 00:03:28,633 there exists an x inside 
S such that P(x) is true, 81 00:03:28,633 --> 00:03:31,500 and for all x inside 
S, P(x) is true. 82 00:03:31,500 --> 00:03:34,466 How do we 
prove this? 83 00:03:34,466 --> 00:03:35,300 84 00:03:35,300 --> 00:03:37,166 Which of the 
following are true? 85 00:03:37,166 --> 00:03:41,466 So we know that over 
the reals, the only values 86 00:03:41,466 --> 00:03:45,400 that make this true are plus or minus root 2. 87 00:03:45,400 --> 00:03:49,133 So are there integers where 
P(x) is true? Well no. 88 00:03:49,133 --> 00:03:52,000 The only ones are the irrational 
numbers plus or minus root 2. 89 00:03:52,000 --> 00:03:53,633 90 00:03:53,633 --> 00:03:56,000 Well for all integers 
is P(x) true, 91 00:03:56,000 --> 00:04:00,700 Right? I mean 0, for example, 0 squared [doesn't] equal 2. 92 00:04:00,700 --> 00:04:02,566 93 00:04:02,566 --> 00:04:05,566 Let's look at the real numbers now. Is 
here a real number that makes this true? 94 00:04:05,566 --> 00:04:08,000 The answer is yes. Well square root of 2 makes it true. 95 00:04:08,000 --> 00:04:10,000 Now let's look at number 
4, well is it true for 96 00:04:10,000 --> 00:04:12,433 all real numbers x 
that P(x) is true? 97 00:04:12,433 --> 00:04:15,133 That's false, right? I mean 0, again, is a counterexample. 98 00:04:15,133 --> 00:04:16,600 0 is a real 
number 99 00:04:16,600 --> 00:04:20,666 and 0 squared equals 2 is a false statement. 100 00:04:20,666 --> 00:04:24,000 But what about for S? Well there 
exists an x in S such that 101 00:04:24,000 --> 00:04:28,766 P(x) is true, that's true. 
There's root 2, for example. 102 00:04:28,766 --> 00:04:31,266 Part 6, for all x 
inside S, P(x). 103 00:04:31,266 --> 00:04:34,500 Well that's also true, S 
only has two elements: 104 00:04:34,500 --> 00:04:36,733 plus or minus root 2, and they're both roots 105 00:04:36,733 --> 00:04:40,000 of x squared minus 
2 equals 0. 106 00:04:40,000 --> 00:04:41,900 6 is going 
to be true. 107 00:04:41,900 --> 00:04:43,100 108 00:04:43,100 --> 00:04:45,566 So here's an example - this actually gives you all the combinations. 109 00:04:45,566 --> 00:04:47,533 So something to 
think about, 110 00:04:47,533 --> 00:04:50,733 just a little bit, can I find one where 
there exists a set T such that 111 00:04:50,733 --> 00:04:52,566 P(x)… that's true 112 00:04:52,566 --> 00:04:55,733 and for all x inside 
T, P(x) that’s… 113 00:04:55,733 --> 00:04:58,900 so can I find one where the first one 
is false and the second one is true? 114 00:04:58,900 --> 00:05:02,600 So if there exists an x inside 
T such that P(x), that's false, 115 00:05:02,600 --> 00:05:05,000 and for all x inside 
T, P(x) is true. 116 00:05:05,000 --> 00:05:08,000 Think about why that can't 
happen. It can't happen, 117 00:05:08,000 --> 00:05:10,533 and if you think about it you'll see why. 118 00:05:10,533 --> 00:05:13,400 So this basically gives 
all the possibilities. 119 00:05:13,400 --> 00:05:15,300 120 00:05:15,300 --> 00:05:17,666 A couple of final things 
to end off with so 121 00:05:17,666 --> 00:05:20,700 approaching quantified statement problems. 122 00:05:20,700 --> 00:05:23,466 So what do we 
want to say here? 123 00:05:23,466 --> 00:05:26,166 We're gonna go through the four 
possibilities. So a single counter example 124 00:05:26,166 --> 00:05:28,833 shows that for all x inside 
S, P(x) is false. 125 00:05:28,833 --> 00:05:31,233 So if I want to disprove a “for all” statement, 126 00:05:31,233 --> 00:05:32,833 all I need to do is find a counter example. 127 00:05:32,833 --> 00:05:36,300 So here's an example: “Every even 
positive integer is composite”, that's false. 128 00:05:36,300 --> 00:05:40,000 2 is even, but 2 is not 
composite, 2 is prime. 129 00:05:40,000 --> 00:05:41,533 Part 2, 130 00:05:41,533 --> 00:05:43,366 a single example 
does not prove that 131 00:05:43,366 --> 00:05:45,300 for all x inside 
S, P(x) is true. 132 00:05:45,300 --> 00:05:47,300 If you want to prove this just like 
we did a couple slides ago, 133 00:05:47,300 --> 00:05:50,966 you have to prove it 
for all elements of S. 134 00:05:50,966 --> 00:05:54,900 So here's an example: “Every even 
integer at least four is composite.” 135 00:05:54,900 --> 00:05:57,766 This is true but we cannot 
prove it by saying, 136 00:05:57,766 --> 00:06:00,466 "Well 6 is an even integer and it's composite, so I'm done." 137 00:06:00,466 --> 00:06:02,833 You can't do 
that, okay? 138 00:06:02,833 --> 00:06:05,266 That's not 
enough, right, 139 00:06:05,266 --> 00:06:08,666 because there are lots of 
even integers that aren't 6, 140 00:06:08,666 --> 00:06:10,933 and that are 
at least 4. 141 00:06:10,933 --> 00:06:13,666 To prove that this is true, you must show that this is true 142 00:06:13,666 --> 00:06:17,700 for an arbitrary even integer x 
greater than or equal to 4. 143 00:06:17,700 --> 00:06:19,166 So what's the 
idea? Well 144 00:06:19,166 --> 00:06:21,833 2 divides x so there exists 
a natural number k 145 00:06:21,833 --> 00:06:25,833 such that 2k equals x and k is not 1. 146 00:06:25,833 --> 00:06:29,033 You can do this to show that the number 
must be composite, it's divisible by 2. 147 00:06:29,033 --> 00:06:31,633 148 00:06:31,633 --> 00:06:36,466 The two factors… and the two factors are greater than 1. 149 00:06:36,466 --> 00:06:37,966 150 00:06:37,966 --> 00:06:40,866 Let's look at another one. So a 
single example does show that 151 00:06:40,866 --> 00:06:44,000 there exists an x inside 
S, P(x) is true. 152 00:06:44,000 --> 00:06:46,966 Claim: “some even 
integer’s prime”, right? 153 00:06:46,966 --> 00:06:50,733 There exists an even integer such that it is prime. 154 00:06:50,733 --> 00:06:53,200 That claim’s true because 
2 is even and 2 is prime. 155 00:06:53,200 --> 00:06:57,366 So there's an example of a “there exists” statement being true. 156 00:06:57,366 --> 00:06:59,733 And then, the last one is 
sort of the trickiest one. 157 00:06:59,733 --> 00:07:02,800 What about showing there exists an x inside S such that P(x) 158 00:07:02,800 --> 00:07:04,733 is false? How 
do we do that? 159 00:07:04,733 --> 00:07:07,300 It turns out the easiest way I 
like to think about this, is you 160 00:07:07,300 --> 00:07:10,933 actually negate this and we'll talk about 
negating quantifiers in the next slide, 161 00:07:10,933 --> 00:07:12,733 but if you negate this, 162 00:07:12,733 --> 00:07:15,033 what has to happen? Well the negation of this must be true. 163 00:07:15,033 --> 00:07:18,500 What's the negation of a “there exists” statement? It's a “for all” statement. 164 00:07:18,500 --> 00:07:21,466 For all x inside S, 
not P(x) is true, 165 00:07:21,466 --> 00:07:25,433 is equivalent to saying there exists an x inside S such that P(x) is false. 166 00:07:25,433 --> 00:07:26,633 167 00:07:26,633 --> 00:07:29,400 So this sort of logical 
equivalence here is actually a 168 00:07:29,400 --> 00:07:32,000 big big hint for solving 
this type of problem. 169 00:07:32,000 --> 00:07:34,900 We'll see this is central in the 
idea of proof by contradiction, 170 00:07:34,900 --> 00:07:37,400 which we'll see 
next week, 171 00:07:37,400 --> 00:07:40,300 but I thought I'd mention it here and it 
seems like a really natural point to do so.