Uniqueness. To prove uniqueness, what do we do?
So we have two options to prove uniqueness:
we assume that there are two elements x and y inside some set S
such that these statements P(x) and P(y) are true,
and then show that x equals y, that's the one thing we can do,
and the second thing we can do is we can argue by assuming that
there are two elements x and y inside S
that are distinct such that P(x) and P(y) are true,
and then derive a contradiction somehow.
So start with two distinct things, and break math in some way, shape, or form.
So to prove uniqueness and existence, don't forget that
you actually have to show that there is one such [x],
so there are two elements to uniqueness and existence.
Uniqueness is just showing that
if an element exists it must be the only element,
and existence means finding such an element.
Remember that we said that we used another symbol here,
“there exists” with an exclamation [mark].
That means that “there exists a unique…”, okay?
I don't have that on the slide but it's okay.
How about an example of uniqueness?
So here's our question: “Suppose that x is inside the set of
real numbers set differenced with the set of integers,
and that m is an integer such that x is less than m is less than x plus 1.
Show that m is unique.” Okay?
So again, this is tough to do unless you actually
read and understand what the sentence is.
“Suppose x is a real number that's not an integer.”
so it’s what we call a non integral real number, that’s one way to word it,
and m is an integer such that
x is less than m is less than x plus 1.
Show that m is unique. What does this really mean?
Let's take an example say x equals 3.3.
So if x is 3.3, then x plus 1 is 4.3 and
m is an integer between 3.3 and 4.3.
Okay, well it's probably the integer 4
since I don't think there's any other ones… oh we're showing that m is unique,
okay, so that's kind of the idea here. You're showing that there was only
one integer between some decimal number and the decimal number plus 1.
It's important that you don't include
the integers for your x because if you included
let's say 0, then 0 is less than m is less than 1
well there is no integer between 0 and 1.
So we need x to be a non-integral real number.
So how does the proof of this go? Well what are we going to do?
We're going to assume that there are two integers m and n
such that x is less than m is less than x plus 1,
and x is less than n is less than x plus 1.
And now what are we going to do? Well let's look…
so now comes the sort of the clever part of this proof,
and when you look at m and n, well the bounds are very…
well the bounds are identical.
So because the bounds are identical, it seems to suggest that if
we look at the difference then we're gonna learn some information here.
So let's look at the difference m minus n.
The value is largest when m is largest and n is smallest,
so when is m largest? Well
when it's as close as possible to x plus 1,
and when is n the smallest? Well it's the smallest
when it's as close as possible to x. Well what's that difference?
That difference is bounded above by 1, right?
If m is x plus 1 and n is x,
well that difference, that length, is 1.
So m minus n has to be less than 1.
For this to be minimal, you flip the roles of m and n, so take
n largest and m smallest.
Well we're going to see that m minus n is bounded below by negative 1,
and these are strict inequalities.
So combining these two facts what do we get? Negative 1 is less than
m minus n is less than [1].
And m minus n is an integer.
There's not too many integers between minus 1 and 1.
In fact we know all of them, it's 0.
But m and n is an integer in this range, so m minus n must be 0,
and that is m equal n. That completes the proof.
So it's just another way to…
again, uniqueness so how do we do this? Again,
start with two values, and either
assume they're distinct and reach a contradiction
or take the two values and show that they must be equal.
In this case, we took two values and showed that they were equal.
Uniqueness, we saw a couple of examples, so a couple of
areas where we could use uniqueness.
One of them was with injections and surjections.
So I'm going to talk a little bit about function notation here. So
let S and T be sets, a function f from S to T
and we use this notation. So what does this notation mean?
A lot of things have sort of changed from here and
from your previous, let's say calculus courses or high school courses.
Functions have a domain and a co-domain given to you.
Here we call S the domain,
and here we call T the co-domain.
Some of you have heard the word “range”. What is range?
Well range is the set of all values
that the function takes.
So, for example, I could define a function from the real numbers
to the real numbers defined by x goes to x squared.
Well the range of this function is only all non-negative numbers.
It's only…x squared is always non-negative.
So x squared is always non-negative,
but what am I trying to say? So
the range is all non-negative numbers, but the co-domain is all real numbers, okay?
So a function has a domain and a co-domain given to it.
It's not… so the question: “find the domain of the function,”
it should just be ,"oh it’s S, right here obviously."
That question really should be very obvious, okay?
Now you could ask, “Can I extend the domain of f
to make sense in other places?” That makes sense too, but a function should
have a domain given to you, and a co-domain given to you.
This notation, what does it mean? Well it means that I'm going to take x
map it to something, so that value we call f(x).
So in the past, you used to see,
“define a function f(x) equals x squared,” something like that, right? Here,
I'm going to define it using the more general notation
and this is used in many upper-year courses, so I wanted to introduce it now
because I feel like it's a really good time to get your head around functions.
So a function f from S to T defined by x maps to f(x)
is said to be injective (sometimes
we use the words, 1 to 1 or 1:1)
if and only if for all x and y inside S,
f(x) equals f(y) implies that x equals y.
What does this really mean? Again, so a bunch of symbols.
I know how to prove this, right, I start with this and show that this is true.
What is this actually telling you?
If I take an element from T
that is mapped to from something from S,
so something that is actually mapped to,
it must only be mapped to in one way, okay?
So the way to think about this is like S is a group of boys and T is a group of girls,
okay? So if a girl has a dance partner,
they only have one dance partner.
That's kind of what this is saying, right?
Now let’s look at it the other way surjective,
or onto, if and only if for all y inside the set T,
so inside the co-domain,
there exists an x inside the domain
such that f(x) equals y.
So let's go back to that party example.
So S is the set of boys, T is the set of girls.
What is this saying? This is saying that every girl has a dance partner.
It mentions nothing…so maybe a girl has two dance partners, you know lucky girl,
that's fine,
but it means that every girl has a partner,
that's what it means to be onto, and 1 to 1 means that
if a girl does have a partner, it must be a unique partner.
That's the idea behind injections and surjections.
Again, there's lots of examples in the notes. I'm not going to
do them here. I'll say, go to the notes. Go to
the Math 135 Resources Page.
Check out some typed examples.
Check out some of the examples from my notes.
One more example of uniqueness was the division algorithm.
What is the division algorithm? It’s basically grade school division.
You do your long division, okay? So if I wanted to divide 7 by 51,
I would write my 7
goes into 51 how many times?
Well 7 goes into 5 0 times, 7 goes into 51 7 times,
what's my remainder? 2.
So 51 is 7 times 7 plus 2.
And another example: so 35 is equal to…
well how many times does 6 go into 35? It
goes in 5 times. 6 times 5 is 30, the remainder is 5.
And if you wanted to do it with a negative value for a, what would we do?
So negative value on the left, well we would write negative 35…
so I do it with the positive version first, take the negation of everything.
So negative 35 is equal to 6 times negative 5,
right, only one of these terms need to be negative if
I multiply everything by negative 1,
and I'm going to subtract 5. But now
I'm going to insist that my remainder be positive,
so [how] do I get my remainder to be positive? I’m going to add an extra value 6,
and that's going to give me 6 times minus 6 plus 1.
So it's the way to do it, this is the way I think about it when I
have negative values for a in the division algorithm, okay?
I go through this two-step process.
The division algorithm, so what does the division algorithm say?
Let a be an integer and b be a natural number,
then here…oh I actually got to use it…
then there exists unique
values q and r inside Z such that a equals b q plus r,
and this doesn't mean that q and r are unique yet.
We also require the condition that 0 is less than or equal to r is strictly less than b.
So keep in mind somebody asked me, “Well why can't r be b?”
And I said, “Well if r is b, then just take off another copy of b,
put it into q and make your remainder 0.”
It's like basically like writing, well 6 is equal to 0 plus 6.
No you should have written it as 6 is equal to 6 times 1 plus 0.
That's the difference there.
The proof, I didn't do it in my class. Some classes probably did do it.
I recommend reading the proof, I really do.
It's a good example of uniqueness.
Existence is tricky, and actually uses
this thing called the “Well Ordering Principle”.
It's a clever argument, you can check that out on Wikipedia,
but for now the proof in the notes…
it's there and you should read it.
It's a good example of uniqueness, and one more example, okay?