PROFESSOR: So in this short segment,
we'll talk about some relational properties
that I call mapping properties.
They can also be referred to as archery [? on ?] relations.
This segment is mostly vocabulary.
There are a half a dozen concepts
and words that are standard in the field
and that one needs to know to be able to do discrete math and so
on.
The applications will come in the next short segment
where we start applying these properties to counting.
Although, there'll be a punchline
about counting at the end of this segment.
So let's go back or proceed.
And remember that a binary relation
is a thing with three parts.
It's got a domain illustrated as A here,
a codomain illustrated as B here,
and relationship's an association
between domain elements and codomain elements indicated
by the arrows, the arrows being called
the graph of the relation.
And we already observed one aspect of archery and arrows
that the concept of a function could
be captured by saying that there was less than
or equal to 1 arrow out of every element in the domain.
That implied that there was a unique other end
of an arrow out of a domain point
called the value of that point under the relation
which is in fact a function F.
So F of green equals magenta where
there is an arrow out of a green element.
But in this picture-- as is typical--
not every domain element-- not every green dot--
has an arrow out if it.
So this would be an illustration of a partial function
where F of a green element isn't always defined
if there's no arrow out.
Well, the general idea of archery relations
pursues this function idea that basically we're
going to classify relations according to-- first,
how many arrows come out of domain elements?
Really, in three categories.
The relations where there's at most
one arrow out of every domain element,
there's exactly one arrow out of every domain element,
or there's at least one arrow out of every domain element.
And symmetrically, we're going to classify codomain relations
with respect to codomain in the same way-- relations
where every codomain element has greater than or equal to 1.
Arrow in has exactly one arrow in,
or at most, one arrow in is the other part
of the classification.
And various combinations of these things
have standard name, which it turns out
that you'll need to know.
So we'll lead you through them.
OK.
So let's begin with the idea of a total relation.
Total relation means there's at least one arrow out
every domain element.
So if you look at this picture, it's not quite total
yet because there are two green domain elements
with no arrows out of them.
So I've just highlighted them in red,
and we can fix this by making them disappear.
Now I'm left with a total relation.
Every domain elements has at least one arrow coming out
of it.
So that's what makes it total.
Another way to say total is to say
that if you look at the inverse image of the codomain,
it is equal to the domain.
That means if you take all the arrows that are coming out
of the domain and you turn them around
and you look at all the things that have arrowheads into them,
it's the entire domain.
So that's what R inverse of B-- a nice, slick way
to say it using relational operators and sets related
to applying relations.
So total and function means that there's exactly one arrow out,
and that's probably the most familiar case of functions.
And lots of fields just assume that functions are total,
but the truth is that there often is not total.
And people aren't careful about.
So let's look at a calculus-like example.
Here's a function g that takes a pair of reals
and returns a real.
It maps the real plane into the real line.
And the definition of it is g of x, y is 1 over x minus y.
Now, the domain of this function g
is in fact all the pairs of reals.
That's what it means to say that it goes from R cross R--
shorthand R squared-- to the codomain R.
The codomain is the set of all reals.
But this g is obviously not total because 1 over 0
is not defined, which means that on the 45 degree line,
g is not defined.
g of r, r is not defined.
So g in fact, is not a total function
even though it's familiar.
And you'd not worry about partial functions normally.
You wouldn't notice that this was partial
because you're not used to paying attention to that.
OK.
Let's look at a slight variation.
This is function g 0 that goes from some unspecified domain.
I'll specify it in a minute to the reals.
It has exactly the same formula g of x, y is 1 over x minus y.
But now, I'm going to tell you that the domain-- instead
of being all the reals-- is the reals except for that 45 degree
line.
I just want to get rid of the bad points
and not worry about them.
The minute I do that, I have these two functions
relations that have the same graph but different domains.
And the result is that I've removed from the domain of g
all the bad points.
I'm left with a total function g 0.
OK.
Let's keep going.
The next concept is of a surjection,
and that's a relation where there
is at least one arrow into every point in the codomain.
There's at least one arrow into every point in B.
Well, again this is a picture where that doesn't quite
work because there's at least one bad point there-- there it
is in red-- that doesn't have an arrow in.
So let's fix things again by making it disappear.
Now I'm left with a surjective relation, or a surjection,
because in fact, everything in the codomain in B
has at least one arrow coming.
Everything's the endpoint of an arrow.
So likewise, we can say in terms of set operations
that R is a surjection if and only if the image of the domain
is the codomain.
Or still another way to say it is-- if
and only if the range of the function
is its entire codomain.
Remember, the range of the points
that are hit-- that's R of A-- it's
not always equal to the codomain.
But when it is, that is what makes it a surjection.
All right.
Injections-- another variation on the theme-- an injection
is a relation where there is at most one
arrow into every element in the codomain.
So looking at this picture now, this is not quite an injection
because there are at least two points here
that have more than one arrow coming into them.
That's what keeps it from being an injection.
So let's fix that by deleting a couple of those edges
that are crowding up points, and now I'm
left with a situation where, in fact, everything in B
has at most one an arrow coming in.
And so I'm showing you a picture of an injection.
And the final concept is when you
have all the good properties.
A bijection is when you have exactly one arrow out
and exactly one arrow in.
It's a total function that is an injection and a surjection
because it's got greater than or equal to 1
and less than or equal to 1 and equal to 1
for all of the domains and codomains.
Now, there's an obvious thing though about bijections,
which we'll wrap up with, which is
why they're useful in counting theory
because it's clear that since there's exactly one arrow out
of every element in A-- the number of arrows
is the same as the size of A-- and since there's exactly one
arrow coming into every element of B, the number of arrows
is the same as the size of B.
And guess what.
That means that where there's a bijection,
the sets are of equal size.
If there's a bijection between two finite sets A and B,
that means that they're the same size.