---
Video Title: Binary Relations
Description: Theory of Computation
https://uvatoc.github.io

4.2: Binary Relations
- Domain and Codomain
- Function, Total
- Injection, Surjective
- Definition of a One to One Function

David Evans and Nathan Brunelle
University of Virginia
---

Let's talk about binary relations.

We used them last class, but we didn't
define them.

And I hope this is something
most of you are familiar with

that you should have seen
in some way in discrete math.

The terminology that's used, like
injective-surjective, I think is kind of

counterintuitive, and I always get those
confused.

The actual concepts, I think,
are fairly straightforward,

but the map to the terminology
is kind of complicated.

So this is the definition
of a binary relation from

the book that is sometimes
used for discrete math.

There's no definition in the book that
we're using for this class of a binary

relation that starts out assuming we
understand what functions are.

The binary relation is just we've got two
sets.

We've got one that's
called the domain and one

that's called the codomain,
and we're using codomain.

Range is kind of an informal term that's
sometimes used to mean something sort of

like codomain, and in functions we talk
about ranges.

Because range has a
slightly different meaning

and we are going to
try to avoid using range.

Some subset of the product of those two
sets is the graph of the relation.

The product of A and B
is every pair that you can

make from taking an element
of A and an element of B.

If it was complete, there would be an edge
between every A and every B.

That would be the full product graph.

What a relation is, is some subset of
that.

Could be the complete
set that would be connecting

every element of A
to every element of B.

The more interesting relations are some
subset.

So we can define special types of
relations, yeah.

So there's no requirement
or non-requirement

about anything about
the elements of the sets.

All we're saying is A is some set of
elements, B is some set of elements.

There are edges between those.

These could be the same.

In A we could have an element 3 and we
could have an element 3 in B.

But they could also be totally different
objects.

There's nothing about the relation that
says they can't be totally different things.

So it could be that all of the things in B
are apples and oranges.

Or they could be sets.

There's no requirement that there's
anything similar about the two sets.

There's nothing necessarily in common or
non-common.

All we're doing is defining a graph.

We have the set A, and we have the set B.

The product A cross B,
it's the set of everything

we can get, taking one
from A and one from B.

That would be those six elements.

We haven't said anything about what the
elements of the sets are.

They could be anything.

Everything we're talking about sets today,
we rarely care what the elements are.

The only thing that matters about the set
is how many things are in it.

But of course, most uses of sets we
actually care what the elements are.

But there's nothing about this that
distinguishes the elements other than B1,

B2, and B3 are different, and it's
different.

If there's an edge between A1 and B1,
that's a different relation than one that

has an edge between B2 and no edge between
A1 and B1.

So they are distinct, but there's nothing
particular about those elements.

The properties that are commonly used to
describe relations.

A function means for every element of the
first set, which is the A set here,

the number of edges out of it is either
zero or one.

If we have one element of A that has edges
to two elements of B, it's not a function.

Is that consistent with the way we think
about functions in computing?

Yeah.

Sure, right.

Lots of functions we write in code can, for
the same input, return different outputs.

But they're not really functions.

At least they're not mathematical
functions if they do that.

To be a mathematical
function, every time we call it

on the same input, it
should give the same output.

To be a function, it's
not allowed to be the case

that it maps the same
element to different things.

And this is good.

For reasoning about relations,
this is a good property to have.

Because if we think of applying the
relation as a function, in our common use

of a function, well, we can apply the
function, the relation to some element of.

A, and that's always going to give us some
element of B.

And it's always going to give us the same.

If we had two edges out of A in our
relation, we couldn't just get an output.

We'd need to get a set of things as an
output, And we don't want to do that.

So a function is useful.

A total relation is every element of A has
at least one out.

So to be a total function means it's
defined on every element of A,

and there's exactly one B that is the
output for every element of A.

Yeah.

Don't mathematical functions have to map
every element in the domain?

So some people define function to mean a
total function, and then would say partial

function when they mean one that's not
defined on every element of the domain.

So this is another case of terminology not
always being used consistently.

If you assume that definition
of function, then the less

than or equal to one out just
means it's a partial function.

The terminology I
prefer would be you have

to explicitly say when
it's a total function.

Function by itself doesn't necessarily
mean it's defined on every input.

The sort of analogy, if you're thinking
about code, and this is a computer science

class, so I think it's useful to relate
things to code.

It's also dangerous, too.

And we've hopefully set that up with the
differences between code.

Many functions that are functional in
programs, meaning they always produce the

same output for the same input,
have exceptions.

They might fail on some inputs.

Like divide by zero is not defined for
zero.

So that would be still a function if we
use this terminology, but it's not a total

function because there
are inputs in the domain,

which is all the natural
numbers that it fails on.

And then the other two terms, which are
the ones that have been used talking about

cardinalities of sets,
are how many edges are

going into each element
in the codomain set.

To be injective means there's less than or
equal to one edge in.

So if there is an injective
total function between two sets.

A and B, what does that tell
us about their cardinalities?

Are they the same?

So it's less than or equal to one here.

Yeah.

B is at least the cardinality of A.

B has cardinality greater than or equal to
A if there is a total injective function.

This gets back to the question of,
when I say function, if we didn't specify

a total function, if there was a function
that was injective between A and B,

do we know anything about the
cardinalities?

No, we don't.

I'll try to be careful, but sometimes,
and I think this is probably true of some

of the definitions we've seen,
we've used function with the assumption

that we're actually talking about a total
function.

Because otherwise it doesn't help us with
the cardinalities.

And surjective, there's at least one in,
that tells us that A is at least the size

of B, if it's a total function between A
and B.

Bijective combines all these to end up
with one out and one in.

So this is a total function that is
injective and surjective.

If we have all of those properties,
we have a bijection, that there's exactly

one out edge from each element in B and
exactly one in edge to each element in A.

And that should intuitively tell you
they're the same cardinality.

So let's make sure we understand those
definitions.

Which of these properties do we need?

So we've got a relation between A and B.

And we want to know
that the cardinality of A is

greater than or equal
to the cardinality of B.

Which of those properties do we need?

Yeah.

Total.

Total, okay.

So it definitely needs to be total.

If it's not total, what could go wrong?

Right.

It could be we have all those
edges, but we have some

elements of A not involved
in any edge if it's not total.

So it's going to need to be total.

What else?

Injective.

Okay.

Good.

It needs to be injective.

Our goal is to show A is bigger than B.

Actually, let's go back to the total
question.

Maybe I'm not so sure about that,
right?

So the relations between A and B.

Our goal is to show A is bigger than B.

So if we have some elements of A with no
edges out of them, that's actually okay.

Do we need injective?

Yeah.

Yeah, we need surjective.

We need at least one edge going into every
element of B.

But we could have some with more.

And do we need anything else?

Is surjective enough?

Yeah, we need a function.

If we didn't have a
function, we could have just

one element of A with
all of those edges out.

Well, it can't actually
have two edges out to the

same one, but it could
have edges out to everyone.

So we need a function.

That's the two things that we would need.

So this was the definition from the book.

And this was actually the very first
definition.

And it was there partly to illustrate what
definitions are.

Does this make sense?

So this is defining a term we didn't use
yet, at least not on the previous slide.

It's defining a one-to-one function.

It's using S and T as the two sets.

For every two elements, X
and X prime of S, if those are

different and we know F of
X, those two are also different.

What does this definition assume about
function?

Yeah, is this assuming it has to be a
total function?

The one-to-one as the name kind of only
makes sense if it's a total function.

It's not what we would
informally think of as the

one-to-one mapping if it
was not a total function.

But this doesn't actually explicitly say
that.