Subsection Relations Generally
A graph is a way to represent some ways that different objects are related. We have seen how to use graphs to represent which people are friends, or which classes have time conflicts, or which radio stations are too close to have the same frequency. Not all ways in which things can be related can be represented by a graph, however. In this section, we will consider the more general concept of a relation and see how those might be related to graphs.
Consider the example of the relation between students and classes that holds when a student is in that class (in a particular semester). This is a relation between two different sets (the students and the classes). If we used a graph to illustrate this relation, the graph would be
bipartite, since two students are never related to each other, and two classes are never related to each other.
A graph is really a set of vertices and a set of edges: each element of the set is a two-element subset of If we want to draw attention to the bipartiteness of the graph, we can split up into its two sets and write In this notation, for the graph to be bipartite, we want each edge to be a pair where is an element of and is an element of In other words, each edge is an element of the Cartesian product of and written,
(Another way to say this is that is βthe set of all ordered pairs of elements from and β)
This example exactly illustrates what a general binary relation is. Here is the careful definition.
Definition 2.6.2.
A
binary relation is a set of ordered pairs. We say the binary relation is a
relation on sets and provided the ordered pairs are a subset of
We say a binary relation is a
relation on a set provided the ordered pairs are a subset of
Note that
is just the set of all ordered pairs where both coordinates are elements from
Example 2.6.3.
Consider a set
of students and a set
of classes. Say
and
Everyone except Dirk is in Calculus, Bob and Eva are in Discrete, and Al, Cat, and Dirk are in Statistics.
We can define a relation
of βis takingβ
and
that holds of a student and class precisely if that student is taking that class. Write this relation as a subset of
and draw its bipartite graph.
Solution.
To write the relation precisely, we just give the set of ordered pairs:
We can draw this relation as a bipartite graph:
Example 2.6.4.
Consider the relation
for βis a multiple ofβ on the set
Write this as a set of ordered pairs. Does this relation create a graph?
Solution.
First, letβs think about which elements should be related and which should not. We know that
is a multiple of
so the relation is true of the pair
but
is not a multiple of
so the pair
does not satisfy the relation. More precisely, we say that
but
Letβs list all the elements of
This relation is not a graph for two reasons: first, elements are related to themselves, and second, the order of elements in the relation is not symmetric ( is related to but is not related to for example).
We can, however, still draw something like a graph to illustrate this relation: Since the direction of the relation matters, we will have
directed edges. This alone would create a
directed graph. Since vertices can have edges going to themselves, we would call the structure a
multigraph, so the relation can be thought of as a
directed multigraph.
A binary relation
on sets
and
can always be βturned aroundβ to give a relation on sets
and
That is,
says how things in
are related to things in
those things in
are related to things in
just in an
inverse (backward) way. We will call this new relation the
inverse of
Definition 2.6.5.
Given a binary relation define to be the inverse of as the set
The relation
from
Example 2.6.3 said that a given student was in a particular class. The inverse relation
says that a given class has a particular student in it. For example,
is an element of
Graphically, there wonβt be any difference in the picture, although we could put the set of classes on top and students on bottom.
The relation
from
Example 2.6.4 gave us that, for example,
is a multiple of
since
For the inverse, we have
which means that
is a factor of
For this example, we have represented a relation as a directed multigraph. The graph of the inverse will look exactly the same, but all the arrows will point in the opposite direction.
Another way to create a new relation is to combine two relations. Suppose in addition to the βis takingβ relation from
Example 2.6.3, we define a relation βis taught byβ that matches up each course with its instructor. Perhaps Professor X teaches Calculus. In that case, since Al is taking Calculus, and Calculus is taught by Professor X, we can conclude that Al is taking a class with Professor X.
Definition 2.6.6.
Let be a relation from set to and be a relation from to The composition of and is
Note the order in which we wrote the two relations: itβs
not
The reason we do this (which might seem backward) is that it agrees with the usual notation for composition of
functions. In fact, functions are nothing but a specific type of relation!
Example 2.6.7.
Write out the relation
composing the relations of
Example 2.6.3 and
Note that here we are saying the statistic course is co-taught by professors X and S.
Solution.
The relation we are looking for is a relation between students and professors. We can start with each element of
and
extend it by following the course to the professor(s) via
So for example, start with Cat, and notice that
Now look at what Calculus is related to via
Thus we can push these together to conclude that
An alternative approach would be to simply consider which pairs of students and professors are linked by a common class. Should the pair
be an element of the composition? No, because there is no class that is both taken by Al and taught by Professor L. On the other hand, we can conclude the
since there is a common course. In fact, the common course could be Calculus or Statistics (it doesnβt matter how many common middle steps there are, as long as there is at least one).
Here is the complete relation:
Something interesting often happens when you compose a relation with its inverse. You might have seen something like this for
functions in calculus or algebra:
has an inverse function
and we know that
But functions are relations in which every βinputβ has exactly one βoutputβ, so perhaps it is not surprising that composing with an inverse just gives you the identity function. When inputs can have multiple outputs, and outputs can have multiple inputs, then we get something more.
Example 2.6.8.
Describe the relation
(using our familiar relation
from
Example 2.6.3). What does this tell us about students and classes?
Solution.
By following the relation, we could start by saying Al is in Calculus, and Calculus is taken by Al, so Al is related to Al. But also , Calculus is taken by Bob, so now Al is also related to Bob. Is Bob related to Al as well? Yes, since Bob is taking Calculus and Calculus is taken by Al.
The composition is telling us which pairs of students have at least one class in common. Thatβs almost all pairs of students, except that Dirk is not related to Bob or Eva, since they donβt take Statistics, and that is the only class he takes.
Instead of writing out the relation (which will almost be all of
), here is the graph representation.
While we drew a directed multigraph here, the arrows going both ways mean that we really could have drawn just a multigraph.
Subsection Properties of Relations
From this point on, we will just consider relations on a single set (so from a set to itself). To help understand these relations, letβs consider some basic properties a relation might or might not have.
Definition 2.6.9. Reflexive, Symmetric, and Transitive.
Ler be a relation on the set We say,
-
is
reflexive provided
for all
-
is
symmetric provided, for all
if
then
-
is
transitive provided, for all
if
and
then
Letβs examine each of these properties carefully.
It will be helpful to consider a few standard examples of relations on sets as we go. Most relations we consider here will be written using
infix notation, just meaning that we put the relation symbol between the two things it is relating. For example, the
less than relation is almost always written as
rather than writing
Example 2.6.10. Reflexive and non-reflexive relations.
A relation is reflexive when every element is related to itself. The following are reflexive relations:
-
The βless-than-or-equal-toβ relation on any set of numbers. Is it the case that
More importantly, is every number no greater than itself? Since the answer is yes, this relation is reflexive.
-
The βwithin 3β relation, that holds of two numbers
and
provided
To prove that this is reflexive, we simply note that
-
The βis a multiple ofβ relation from
Example 2.6.4. Note that the directed multigraph for this relation had loops at every vertex.
However, these relations are not reflexive:
-
The βsums to zeroβ relation, that holds on numbers
and
if
Note that while
so
is an element of the relation, every other number is not related to itself.
-
Any relation that is described by a graph. Remember, graphs cannot have edges looping back to a single vertex, so the edge relation on a graph is not reflexive. (A multigraph could be reflexive or not).
If no element is related to itself (such as in the edge relation for a graph), then we call the relation
irreflexive. Of course, some relations are neither reflexive nor irreflexive.
Checking that a relation is reflexive is relatively easy. The other two properties are phrased as implications, which makes them a little more complex.
Example 2.6.11. Symmetric and non-symmetric relations.
Essentially, symmetric relations are the ones that work βboth ways.β More precisely, if
is related to
then
is also related to
The following relations are symmetric.
-
The βwithin 3β relation: if
then
-
The βsums to zeroβ relation: if
then certainly
-
For any graph, the edge relation is symmetric. Of course, for
directed graphs this is usually not true.
On the other hand, these relations are not symmetric.
-
is not symmetric. All we need to do to prove that a relation is not symmetric is to find some
and
such that
but
Well,
but
QED.
-
The βis a multiple ofβ relation is not symmetric.
is a multiple of
but
is not a multiple of
Relations that are not symmetric could in fact be
antisymmetric, meaning the
only elements for which both
and
are in the relation is when
Note that there are relations that are neither symmetric nor antisymmetric.
Using the language of inverse relations, a relation is symmetric if and only if the relation is equal to its inverse.
Example 2.6.12. Transitive and non-transitive relations.
If
is related to
and
is related to
does that mean
is related to
If this is true no matter what
and
are, then we say the relation is transitive.
Here are some transitive relations.
-
-
The βis a multiple ofβ relation. This is a good one to write a proof for: Suppose
is a multiple of
and that
is a multiple of
Then
for some integer
and
for some integer
By substitution,
so
is a multiple of
However, the following relations are not transitive.
-
The βwithin 3β relation is not transitive. All we need to do is find three numbers that fail to meet the condition. How about
and
Here
is within 3 of
and
is within 3 of
but
so the relation does not hold of
-
The βsums to zeroβ relation is not transitive. Notice that we never claimed that
and
need to be different numbers. Let
and
Then
and
so the relation holds of
and
But
so the relation does not hold of
The edge relation for a graph might or might not be transitive. What would a graph look like if its edge relation was transitive?
Subsection Equivalence Relations
Now we will do something very typical for mathematics: We will look at our most common types of relations, consider what properties these have, and then classify other relations that also have these properties as a specific class of relations.
The relation we are all most familiar with is
equality. Which properties of relations does the equality relation possess? Certainly everything is equal to itself, so equality is
reflexive. If
then
so equality is
symmetric. If
and
then
so equality is
transitive.
What other relations are
reflexive,
symmetric, and
transitive? Exactly those relations that behave like equality. We call such relations
equivalence relations.
Definition 2.6.13. Equivalence Relation.
A relation that is reflexive, symmetric, and transitive is called an
equivalence relation.
None of the examples we have considered so far in this section have been equivalence relations, but they are ubiquitous in mathematics. They are so common that it is easy to overlook them as anything worth saying something about at all. Letβs see some examples.
Example 2.6.15.
Prove that the relation
which holds of two integers if their difference is even, is an equivalence relation. That is,
if and only if
for some integer
Solution.
We simply check the three required properties.
-
is reflexive: for any integer
we have
and
for
so
-
is symmetric: Fix arbitrary integers
and
and assume
That means that
for some integer
What about
Well, we will have
and
is an integer, so we have
-
is transitive: Fix arbitrary integers and and assume and This means that and for some integers and What about Well,
Since is an integer, we see that as required.
Example 2.6.16.
Letβs call two graphs βdegree-sequence-equivalentβ if they have the same degree sequence. Is this an equivalence relation?
Solution.
Yes it is. Clearly every graph has the same degree sequence as itself, so the relation is reflexive. If
has the same degree sequence as
then
has the same degree sequence as
so the relation is transitive. Finally, if
has the same degree sequence as
which has the same degree sequence as
then they all have the same degree sequence, so
has the same degree sequence as
(i.e., the relation is transitive).
This example is almost too obvious. Thatβs because we said that two things are related if a well-defined property of those things was
equal, and equality satisfies the properties of an equivalence relation. Our next goal is to try to make better sense of this and see that it is exactly what gives us an equivalence relation.
Subsection Equivalence Classes and Partitions
Given
any relation
we can look at the
set of elements that are related to a particular element. For the βis takingβ relation, we can ask what classes Al is taking (i.e., the classes related to Al). For the βis a multiple ofβ, we can ask which numbers 6 a multiple of. One way to study the relation is to study the sets of things related to each element.
Definition 2.6.17.
Let be a relation on the set and let be an element of The relation class of written is the set of all elements such that (the set of that are related to by ). That is,
When
is an equivalence relation, we call relation classes
equivalence classes.
Example 2.6.18.
Find the relation classes for the βis a multiple ofβ relation on the set
Solution.
There will be six relation classes since each element has a relation class. They are:
For example, we found by considering all pairs that satisfied the relation: 4 is a multiple of 1, 2, and 4, so those are the possible values of that we find.
Look back at the directed multigraph for this relation shown in the solution to
Example 2.6.4. What are the relation classes? They are nothing but the neighbors of each vertex (where neighbor means you follow the arrows in the correct direction).
Example 2.6.19.
Find the equivalence classes for the
relation on the integers.
Solution.
On no! Our set is infinite, so we will have infinitely many relation classes? Well, we better get started...
What numbers are related to 1? Remember, we want integers whose difference with 1 is a multiple of 2. So 3 for sure. Also 5, and 7, and -1, and -3, and... all the odds? Yes, because the difference of any two odd numbers is even. We can also say that the difference between any two even numbers is even, so the equivalence class of 2 will contain all the even numbers. So far we have:
Actually, I think we are done. While
and so on are all completely valid equivalence classes, the elements that are related to
will be exactly the elements related to
since
This is because the relation is transitive! If
then we know
So we have exactly two equivalence classes. Every integer is in exactly one of these two equivalence classes, and the equivalence class of any integer is exactly the class it belongs to.
Examine the two examples above carefully. For the βis a multiple ofβ relation, which is NOT an equivalence relation, some elements belong to more than one (different) relation class. But for
which is an equivalence relation, every element is in exactly one equivalence class. This is no accident. To make sense of this, we will define a new term.
Definition 2.6.20.
Given a non-empty set
a
partition of
is a set
of non-empty subsets of
such that every element of
is in exactly one element of
That definition has a lot of symbols and sets involved. Itβs really not complicated though: A partition is a way to break up a set into
disjoint subsets that
cover the whole set. That the subsets are disjoint means no element is in
more than one subset. That the subsets cover the set means every element is in
at least one subset.
Example 2.6.21.
Give a few different partitions of the set
Solution.
There are so many choices here! One choice is:
Thatβs a partition of into two subsets. Another partition:
Another:
which happens to be a partition into even and odd numbers. We also have the trivial partition:
Note: that is a single set inside the set
It is sometimes a little confusing to think of the elements of a partition as subsets since the partition is a set, and a set of sets can be difficult to talk about. We sometimes call the partition a
collection and each of the elements of the partition
parts or
blocks.
Now the big idea: For any equivalence relation, the equivalence classes form a partition, and for any partition, we can define a relation βare in the same subsetβ which will be an equivalence relation. We have already seen that the equivalence classes of
form a partition. Letβs go the other direction.
Example 2.6.22.
Define an equivalence relation
on the set
from the partition
Solution.
Say two elements of
are equivalent provided they belong to the same element of
That is,
and
and
and
Wait. We also have
and so on, since every number is in the same subset as itself.
It is clear from looking that this relation is reflexive, symmetric, and transitive, so is an equivalence relation.
Theorem 2.6.23.
Given any equivalence relation
on a set
the equivalence classes form a partition of
Given any partition
of a set
the relation
defined by
if and only if
and
belong to the same block of
is an equivalence relation.
Further, the equivalence classes for the equivalence relation formed by a partition are exactly the original partition, and the equivalence relation built by the partition of its equivalence classes is exactly the original equivalence relation.