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.