1 00:00:00,000 --> 00:00:03,266 Uniqueness. To prove 
uniqueness, what do we do? 2 00:00:03,266 --> 00:00:05,633 So we have two options 
to prove uniqueness: 3 00:00:05,633 --> 00:00:09,266 we assume that there are two 
elements x and y inside some set S 4 00:00:09,266 --> 00:00:13,933 such that these statements 
P(x) and P(y) are true, 5 00:00:13,933 --> 00:00:16,766 and then show that x equals y, 
that's the one thing we can do, 6 00:00:16,766 --> 00:00:18,833 and the second thing we can do 
is we can argue by assuming that 7 00:00:18,833 --> 00:00:21,166 there are two elements 
x and y inside S 8 00:00:21,166 --> 00:00:24,000 that are distinct such that 
P(x) and P(y) are true, 9 00:00:24,000 --> 00:00:26,000 and then derive a 
contradiction somehow. 10 00:00:26,000 --> 00:00:29,300 So start with two distinct things, and 
break math in some way, shape, or form. 11 00:00:29,300 --> 00:00:30,366 12 00:00:30,366 --> 00:00:32,400 So to prove uniqueness and existence, don't forget that 13 00:00:32,400 --> 00:00:34,700 you actually have to show 
that there is one such [x], 14 00:00:34,700 --> 00:00:37,800 so there are two elements to 
uniqueness and existence. 15 00:00:37,800 --> 00:00:41,133 Uniqueness is just showing that 16 00:00:41,133 --> 00:00:43,833 if an element exists it must 
be the only element, 17 00:00:43,833 --> 00:00:47,500 and existence means 
finding such an element. 18 00:00:47,500 --> 00:00:50,233 Remember that we said that 
we used another symbol here, 19 00:00:50,233 --> 00:00:52,000 “there exists” with an exclamation [mark]. 20 00:00:52,000 --> 00:00:55,233 That means that “there exists a unique…”, okay? 21 00:00:55,233 --> 00:00:58,600 I don't have that on 
the slide but it's okay. 22 00:00:58,600 --> 00:01:01,300 How about an example of uniqueness? 23 00:01:01,300 --> 00:01:03,700 So here's our question: “Suppose 
that x is inside the set of 24 00:01:03,700 --> 00:01:06,100 real numbers set differenced
with the set of integers, 25 00:01:06,100 --> 00:01:09,400 and that m is an integer such that x 
is less than m is less than x plus 1. 26 00:01:09,400 --> 00:01:12,000 Show that m is 
unique.” Okay? 27 00:01:12,000 --> 00:01:14,700 So again, this is tough to 
do unless you actually 28 00:01:14,700 --> 00:01:16,366 read and understand 
what the sentence is. 29 00:01:16,366 --> 00:01:20,600 “Suppose x is a real number that's not an integer.” 30 00:01:20,600 --> 00:01:24,633 so it’s what we call a non integral real 
number, that’s one way to word it, 31 00:01:24,633 --> 00:01:26,366 and m is an integer 
such that 32 00:01:26,366 --> 00:01:29,966 x is less than m is 
less than x plus 1. 33 00:01:29,966 --> 00:01:32,366 Show that m is unique. What does this really mean? 34 00:01:32,366 --> 00:01:35,500 Let's take an example 
say x equals 3.3. 35 00:01:35,500 --> 00:01:38,500 So if x is 3.3, then 
x plus 1 is 4.3 and 36 00:01:38,500 --> 00:01:42,100 m is an integer 
between 3.3 and 4.3. 37 00:01:42,100 --> 00:01:44,200 Okay, well it's 
probably the integer 4 38 00:01:44,200 --> 00:01:46,900 since I don't think there's any other ones… 
oh we're showing that m is unique, 39 00:01:46,900 --> 00:01:49,600 okay, so that's kind of the idea here. 
You're showing that there was only 40 00:01:49,600 --> 00:01:54,333 one integer between some decimal 
number and the decimal number plus 1. 41 00:01:54,333 --> 00:01:56,166 It's important that 
you don't include 42 00:01:56,166 --> 00:01:58,066 the integers for your x 
because if you included 43 00:01:58,066 --> 00:02:00,933 let's say 0, then 0 is less 
than m is less than 1 44 00:02:00,933 --> 00:02:03,166 well there is no integer between 0 and 1. 45 00:02:03,166 --> 00:02:07,533 So we need x to be a 
non-integral real number. 46 00:02:07,533 --> 00:02:09,533 So how does the proof of this go? 
Well what are we going to do? 47 00:02:09,533 --> 00:02:12,833 We're going to assume that there are two integers m and n 48 00:02:12,833 --> 00:02:15,100 such that x is less than 
m is less than x plus 1, 49 00:02:15,100 --> 00:02:17,633 and x is less than n 
is less than x plus 1. 50 00:02:17,633 --> 00:02:19,933 And now what are we 
going to do? Well let's look… 51 00:02:19,933 --> 00:02:23,366 so now comes the sort of 
the clever part of this proof, 52 00:02:23,366 --> 00:02:26,100 and when you look at m and 
n, well the bounds are very… 53 00:02:26,100 --> 00:02:27,733 well the bounds 
are identical. 54 00:02:27,733 --> 00:02:30,066 So because the bounds are identical, it seems to suggest that if 55 00:02:30,066 --> 00:02:32,866 we look at the difference then we're 
gonna learn some information here. 56 00:02:32,866 --> 00:02:35,566 So let's look at the 
difference m minus n. 57 00:02:35,566 --> 00:02:38,500 The value is largest when m 
is largest and n is smallest, 58 00:02:38,500 --> 00:02:40,000 so when is m 
largest? Well 59 00:02:40,000 --> 00:02:43,333 when it's as close as 
possible to x plus 1, 60 00:02:43,333 --> 00:02:45,866 and when is n the smallest? 
Well it's the smallest 61 00:02:45,866 --> 00:02:48,000 when it's as close as possible to 
x. Well what's that difference? 62 00:02:48,000 --> 00:02:51,200 That difference is bounded above by 1, right? 63 00:02:51,200 --> 00:02:54,000 If m is x plus 1 and n is x, 64 00:02:54,000 --> 00:02:56,333 well that difference, 
that length, is 1. 65 00:02:56,333 --> 00:02:58,866 So m minus n has 
to be less than 1. 66 00:02:58,866 --> 00:03:02,066 For this to be minimal, you flip 
the roles of m and n, so take 67 00:03:02,066 --> 00:03:04,000 n largest and 
m smallest. 68 00:03:04,000 --> 00:03:07,600 Well we're going to see that m minus 
n is bounded below by negative 1, 69 00:03:07,600 --> 00:03:09,666 and these are 
strict inequalities. 70 00:03:09,666 --> 00:03:12,000 So combining these two facts what 
do we get? Negative 1 is less than 71 00:03:12,000 --> 00:03:14,066 m minus n is less than [1]. 72 00:03:14,066 --> 00:03:15,766 And m minus 
n is an integer. 73 00:03:15,766 --> 00:03:18,300 There's not too many integers 
between minus 1 and 1. 74 00:03:18,300 --> 00:03:21,033 In fact we know 
all of them, it's 0. 75 00:03:21,033 --> 00:03:25,033 But m and n is an integer in this 
range, so m minus n must be 0, 76 00:03:25,033 --> 00:03:28,300 and that is m equal n. That completes the proof. 77 00:03:28,300 --> 00:03:31,366 So it's just another way to… 78 00:03:31,366 --> 00:03:34,000 again, uniqueness so how do we do this? Again, 79 00:03:34,000 --> 00:03:36,800 start with two values, and either 80 00:03:36,800 --> 00:03:39,633 assume they're distinct 
and reach a contradiction 81 00:03:39,633 --> 00:03:42,433 or take the two values and 
show that they must be equal. 82 00:03:42,433 --> 00:03:45,200 In this case, we took two values 
and showed that they were equal. 83 00:03:45,200 --> 00:03:47,866 84 00:03:47,866 --> 00:03:50,933 Uniqueness, we saw a couple 
of examples, so a couple of 85 00:03:50,933 --> 00:03:52,266 areas where we 
could use uniqueness. 86 00:03:52,266 --> 00:03:54,833 One of them was with injections and surjections. 87 00:03:54,833 --> 00:03:57,433 So I'm going to talk a little bit 
about function notation here. So 88 00:03:57,433 --> 00:04:01,100 let S and T be sets, a function f from S to T 89 00:04:01,100 --> 00:04:04,000 and we use this notation. So 
what does this notation mean? 90 00:04:04,000 --> 00:04:06,066 A lot of things have sort 
of changed from here and 91 00:04:06,066 --> 00:04:09,766 from your previous, let's say calculus 
courses or high school courses. 92 00:04:09,766 --> 00:04:13,900 Functions have a domain and a co-domain given to you. 93 00:04:13,900 --> 00:04:15,766 Here we call 
S the domain, 94 00:04:15,766 --> 00:04:19,233 and here we call 
T the co-domain. 95 00:04:19,233 --> 00:04:21,666 Some of you have heard the 
word “range”. What is range? 96 00:04:21,666 --> 00:04:23,900 Well range is the 
set of all values 97 00:04:23,900 --> 00:04:25,933 that the function takes. 98 00:04:25,933 --> 00:04:29,000 So, for example, I could define a 
function from the real numbers 99 00:04:29,000 --> 00:04:32,633 to the real numbers defined 
by x goes to x squared. 100 00:04:32,633 --> 00:04:35,433 Well the range of this function 
is only all non-negative numbers. 101 00:04:35,433 --> 00:04:38,900 It's only…x squared is 
always non-negative. 102 00:04:38,900 --> 00:04:40,533 103 00:04:40,533 --> 00:04:43,533 So x squared is always non-negative, 104 00:04:43,533 --> 00:04:46,533 but what am I 
trying to say? So 105 00:04:46,533 --> 00:04:50,400 the range is all non-negative numbers, but 
the co-domain is all real numbers, okay? 106 00:04:50,400 --> 00:04:53,733 So a function has a domain 
and a co-domain given to it. 107 00:04:53,733 --> 00:04:56,566 It's not… so the question: “find the domain of the function,” 108 00:04:56,566 --> 00:05:00,000 it should just be ,"oh it’s 
S, right here obviously." 109 00:05:00,000 --> 00:05:03,833 That question really should 
be very obvious, okay? 110 00:05:03,833 --> 00:05:06,800 Now you could ask, “Can 
I extend the domain of f 111 00:05:06,800 --> 00:05:10,266 to make sense in other places?” That 
makes sense too, but a function should 112 00:05:10,266 --> 00:05:13,033 have a domain given to you, 
and a co-domain given to you. 113 00:05:13,033 --> 00:05:16,066 This notation, what does it mean? Well it means that I'm going to take x 114 00:05:16,066 --> 00:05:19,533 map it to something, so 
that value we call f(x). 115 00:05:19,533 --> 00:05:21,633 So in the past, 
you used to see, 116 00:05:21,633 --> 00:05:25,600 “define a function f(x) equals x squared,” 
something like that, right? Here, 117 00:05:25,600 --> 00:05:27,800 I'm going to define it using 
the more general notation 118 00:05:27,800 --> 00:05:31,166 and this is used in many upper-year 
courses, so I wanted to introduce it now 119 00:05:31,166 --> 00:05:35,366 because I feel like it's a really good 
time to get your head around functions. 120 00:05:35,366 --> 00:05:38,633 So a function f from S to 
T defined by x maps to f(x) 121 00:05:38,633 --> 00:05:40,500 is said to be 
injective (sometimes 122 00:05:40,500 --> 00:05:43,433 we use the words, 
1 to 1 or 1:1) 123 00:05:43,433 --> 00:05:46,733 if and only if for all 
x and y inside S, 124 00:05:46,733 --> 00:05:50,433 f(x) equals f(y) implies that x equals y. 125 00:05:50,433 --> 00:05:53,666 What does this really mean? 
Again, so a bunch of symbols. 126 00:05:53,666 --> 00:05:57,200 I know how to prove this, right, I start 
with this and show that this is true. 127 00:05:57,200 --> 00:05:58,866 What is this actually telling you? 128 00:05:58,866 --> 00:06:01,866 If I take an 
element from T 129 00:06:01,866 --> 00:06:04,000 that is mapped to from 
something from S, 130 00:06:04,000 --> 00:06:06,433 so something that is 
actually mapped to, 131 00:06:06,433 --> 00:06:09,966 it must only be mapped 
to in one way, okay? 132 00:06:09,966 --> 00:06:14,466 So the way to think about this is like S is 
a group of boys and T is a group of girls, 133 00:06:14,466 --> 00:06:17,166 okay? So if a girl has a dance partner, 134 00:06:17,166 --> 00:06:19,866 they only have 
one dance partner. 135 00:06:19,866 --> 00:06:22,300 That's kind of what 
this is saying, right? 136 00:06:22,300 --> 00:06:24,000 Now let’s look at it 
the other way surjective, 137 00:06:24,000 --> 00:06:27,533 or onto, if and only if for all y inside the set T, 138 00:06:27,533 --> 00:06:29,100 so inside the 
co-domain, 139 00:06:29,100 --> 00:06:31,533 there exists an x 
inside the domain 140 00:06:31,533 --> 00:06:33,566 such that 
f(x) equals y. 141 00:06:33,566 --> 00:06:35,700 So let's go back to 
that party example. 142 00:06:35,700 --> 00:06:38,400 So S is the set of boys, 
T is the set of girls. 143 00:06:38,400 --> 00:06:42,733 What is this saying? This is saying 
that every girl has a dance partner. 144 00:06:42,733 --> 00:06:46,833 It mentions nothing…so maybe a girl has 
two dance partners, you know lucky girl, 145 00:06:46,833 --> 00:06:48,433 that's fine, 146 00:06:48,433 --> 00:06:51,200 but it means that 
every girl has a partner, 147 00:06:51,200 --> 00:06:53,933 that's what it means to be 
onto, and 1 to 1 means that 148 00:06:53,933 --> 00:06:57,566 if a girl does have a partner, 
it must be a unique partner. 149 00:06:57,566 --> 00:06:58,700 150 00:06:58,700 --> 00:07:01,933 That's the idea behind injections and surjections. 151 00:07:01,933 --> 00:07:04,666 Again, there's lots of examples 
in the notes. I'm not going to 152 00:07:04,666 --> 00:07:08,000 do them here. I'll say, 
go to the notes. Go to 153 00:07:08,000 --> 00:07:10,666 the Math 135 Resources Page. 154 00:07:10,666 --> 00:07:13,333 Check out some 
typed examples. 155 00:07:13,333 --> 00:07:16,000 Check out some of the 
examples from my notes. 156 00:07:16,000 --> 00:07:20,000 One more example of uniqueness 
was the division algorithm. 157 00:07:20,000 --> 00:07:22,566 What is the division algorithm? It’s basically grade school division. 158 00:07:22,566 --> 00:07:26,333 You do your long division, okay? 
So if I wanted to divide 7 by 51, 159 00:07:26,333 --> 00:07:28,500 I would write my 7 160 00:07:28,500 --> 00:07:30,833 goes into 51 
how many times? 161 00:07:30,833 --> 00:07:34,366 Well 7 goes into 5 0 times, 
7 goes into 51 7 times, 162 00:07:34,366 --> 00:07:36,000 what's my remainder? 2. 163 00:07:36,000 --> 00:07:40,000 So 51 is 7 
times 7 plus 2. 164 00:07:40,000 --> 00:07:42,166 And another example: 
so 35 is equal to… 165 00:07:42,166 --> 00:07:44,166 well how many times 
does 6 go into 35? It 166 00:07:44,166 --> 00:07:48,466 goes in 5 times. 6 times 5 
is 30, the remainder is 5. 167 00:07:48,466 --> 00:07:51,733 And if you wanted to do it with a negative 
value for a, what would we do? 168 00:07:51,733 --> 00:07:55,333 So negative value on the left, well we would write negative 35… 169 00:07:55,333 --> 00:07:58,800 so I do it with the positive version 
first, take the negation of everything. 170 00:07:58,800 --> 00:08:01,400 So negative 35 is equal 
to 6 times negative 5, 171 00:08:01,400 --> 00:08:03,366 right, only one of these 
terms need to be negative if 172 00:08:03,366 --> 00:08:05,366 I multiply everything 
by negative 1, 173 00:08:05,366 --> 00:08:08,233 and I'm going to 
subtract 5. But now 174 00:08:08,233 --> 00:08:10,366 I'm going to insist that 
my remainder be positive, 175 00:08:10,366 --> 00:08:13,433 so [how] do I get my remainder to be 
positive? I’m going to add an extra value 6, 176 00:08:13,433 --> 00:08:16,000 and that's going to give me 
6 times minus 6 plus 1. 177 00:08:16,000 --> 00:08:18,166 So it's the way to do it, this is 
the way I think about it when I 178 00:08:18,166 --> 00:08:21,200 have negative values for a in 
the division algorithm, okay? 179 00:08:21,200 --> 00:08:24,000 I go through this two-step process. 180 00:08:24,000 --> 00:08:26,466 The division algorithm, so what 
does the division algorithm say? 181 00:08:26,466 --> 00:08:28,933 Let a be an integer and 
b be a natural number, 182 00:08:28,933 --> 00:08:30,733 then here…oh I 
actually got to use it… 183 00:08:30,733 --> 00:08:32,833 then there 
exists unique 184 00:08:32,833 --> 00:08:38,033 values q and r inside Z such 
that a equals b q plus r, 185 00:08:38,033 --> 00:08:40,866 and this doesn't mean that 
q and r are unique yet. 186 00:08:40,866 --> 00:08:45,433 We also require the condition that 0 is 
less than or equal to r is strictly less than b. 187 00:08:45,433 --> 00:08:47,900 So keep in mind somebody asked 
me, “Well why can't r be b?” 188 00:08:47,900 --> 00:08:50,400 And I said, “Well if r is b, then 
just take off another copy of b, 189 00:08:50,400 --> 00:08:53,800 put it into q and make 
your remainder 0.” 190 00:08:53,800 --> 00:08:57,033 It's like basically like writing, 
well 6 is equal to 0 plus 6. 191 00:08:57,033 --> 00:09:01,800 No you should have written it 
as 6 is equal to 6 times 1 plus 0. 192 00:09:01,800 --> 00:09:04,400 That's the 
difference there. 193 00:09:04,400 --> 00:09:08,366 The proof, I didn't do it in my class. 
Some classes probably did do it. 194 00:09:08,366 --> 00:09:10,566 I recommend reading 
the proof, I really do. 195 00:09:10,566 --> 00:09:12,500 It's a good example 
of uniqueness. 196 00:09:12,500 --> 00:09:14,233 Existence is tricky, 
and actually uses 197 00:09:14,233 --> 00:09:17,233 this thing called the 
“Well Ordering Principle”. 198 00:09:17,233 --> 00:09:19,800 It's a clever argument, you can 
check that out on Wikipedia, 199 00:09:19,800 --> 00:09:24,533 but for now the 
proof in the notes… 200 00:09:24,533 --> 00:09:25,966 it's there and you should read it. 201 00:09:25,966 --> 00:09:28,766 It's a good example of uniqueness, 
and one more example, okay?