Associated Topics || Dr. Math Home || Search Dr. Math

### Relations on a Set, as Mappings

```
Date: 7/19/96 at 16:41:33
From: Scott Turner
Subject: Proof: Relations on a Set

I have a 3 parter here and I'm pulling blanks.  The book I have has
very little on relations and I'm not sure where to go with this.

1. If R, S, and T are relations on a set A, show that
(R o S) o T = R o (S o T) where "o" stands for composite.
Basically I'm lost here because the only thing I have
to go on is the definition of composite.

2. Using (1), prove by induction on n that R o R^n = R^(n+1)

3. Suppose R is symmetric. show that R^n is symmetric for all pos
integers n.

On this one I got lost from the start. With my base case = 1,
how can I say that R is symmetric? Then I assume R^n.  Well I've
jumped ahead at this point and assumed that R is symmetric (can I
assume twice?). Well then (a,b) and (b,a) belong to R and (a, b)
and (b,a) belong to R^n. Then applying the the fact that R o R^n =
R^(n+1), I get that (a, a) and (b,b) belong to R^(n+1) but this
doesn't prove anything.

Help.  - ST
```

```
Date: 7/20/96 at 21:12:1
From: Doctor Sydney
Subject: Re: Proof: Relations on a Set

Doing proofs with relations can be hard at first, but once you
begin to get a feel for what a relation is, your intuition will

Let's first go over what a relation is. A relation R on a set A is
a subset of the set A x A. The set A x A is the set of ordered
pairs (x,y) such that x and y are both in A.

That seems simple, right?  Let's look at some examples. Suppose
our set A is the following: {1, 2, 3, 4, 5}. An example of a
relation R is the following:  R = {(1,1), (1,2), (5,4)}. [About
notation: people often write xRy to mean that the ordered pair
(x,y) is in R, so we might write 1R2 to indicate that (1,2) is in
R above.]

Let's elaborate on what a relation is by comparing it to a
function. If you already feel comfortable with what a relation is,

Let's examine relations in more detail. Relations and functions
are intricately related (no pun intended!). Understanding the set
theoretic definition of a function will help us understand better
what a relation is.

Functions are relations with two special properties. A function
F on A (defined set theoretically) is a relation such that:

1. For all x in A, there exists a y such that (x,y) is in F.

2. If (x,y) and (x,z) are in F, then y = z.

That sounds complicated, but it is just a new way of thinking
about functions, which are probably familiar to you. How is this
definition of function similar to the one you know? Well, let's
look at the definition you know. It says that f is a function if
it takes values from its domain and assigns them to unique values
in its range. The function will assign to an element of its
domain, say x, a value we denote as f(x) in its range, right? So,
x and f(x) go together; we might write them (x, f(x)).

If we write down all such pairs for all x in the domain, we will
have a function in the set theoretic sense! Hence, think of an
element of the set called a function as an ordered pair, where the
first element in the ordered pair is mapped under the function to
the second element in the ordered pair. With this in mind, the
above two criteria will make sense.  The first says that the
function assigns values in the range to ALL values in the domain;
not just some. Our function wouldn't be very good if it didn't
tell us where it sent all of the values in its domain, now would
it?  The second criterion requires that each value in the domain
be assigned to no more than one value in the range.

As you can see, a relation is a generalized function. A relation on a
set A is the same as a function except we don't need to worry about the
two criteria mentioned above. So, a relation on a set A is a set of
ordered pairs (x,y) such that x and y are in A.

It may help to think of relations in a way similar to the way you think
of functions; when (x,y) is in R (or, similarly, when xRy), you can
think of R as "mapping" x to y. Of course, since the rules for "mapping"
are different for relations, x might be mapped to many different
elements of A (this would happen if there were several ordered pairs in
R with x as their first element), and not all elements in the "domain"
of R are assigned values in the "range." Look back at the example of the
relation we discussed earlier. We can think of that relation as
"mapping" 1 to both 1 and 2 and also mapping 5 to 4; thus we see that it
is all right to map an element to more than one element (1 was mapped to
1 and to 2). In addition, it is not necessary that all elements in A be
assigned values in the "range". We can see that 2,3, and 4 are not
"mapped" to any elements of A. This is okay for a relation. Relations
are more flexible than functions, as you can see!

Okay, enough on relations.  Now we'll move on to your questions.
------------------------------------------------------------------

First, let's look at the definition of relation composition; it is the
analogue of function composition modified for relations.

Suppose Q and P are relations on the set A.  Then Q o P is the relation
defined as follows:

(x,y) is an element of the set Q o P if and only if there exists a z
in A such that xQz and zPy.

How are you to make sense of this? Well, if x is "mapped" to y
by Q o P, then decomposing the composition, we see that Q "maps" x
to some z in A, and P maps that same z to y. Of course Q might "map"
x to other values too - relations can do that. The important thing is that
x is mapped to this z, which in turn gets mapped to y.

Let's move on to the first problem.  Here it is:

1. If R, S, and T are relations on a set A, show that
(R o S) o T = R o (S o T) where "o" stands for composite.
Basically I'm lost here because the only thing I have to
go on is the definition of composite.

So, how can we prove that (R o S) o T = R o (S o T)? Well, each side of
the equation represents a set, right? So, to prove that two sets are
equal, we need to show inclusion on both sides; that is, we need to show
that (R o S) o T is a subset of R o (S o T), and then we must also show
that R o (S o T) is a subset of (R o S) o T. The only things we know
about relations and relation composition are their definitions, right?
So that is the only information we will use in the proof. We will use
definitions over and over again. Whenever you are stuck on problems like
this, try to use your definitions!

I'll start you off on this and hope you can figure out the rest on your
own. Let's first prove that (R o S) o T is a subset of R o (S o T).
When we have done that we will prove the converse.

To prove that (R o S) o T is a subset of R o (S o T), we need to take an
element of (R o S) o T and show that it also belongs to R o (S o T).
Let's suppose that (x,y) is in (R o S) o T. Then, by the definition of
composition, we have that there exists a z such that x(R o S)z and zTy,
right? We get this by plugging (R o S) in for P and T for Q in the
equation above. But if x(R o S)z, then this means that there exists a w
such that xRw and wSz. That is again from the definition of relation
composition. So, we have learned that there exist a z and a w such that
zTy, wSz, and xRw.  (*)

What were we trying to show? We wanted to show that (x,y) is in the set
R o (S o T). What would it mean for (x,y) to be in the set R o (S o T)?
Again, go through the definitions in the exact same way we did above.
Once you have figured out what it would mean for (x,y) to be in this set,
look at what you already know about (x,y) from *. From there, I bet you
can finish the proof on your own.  Don't forget to prove the inclusion the
other way, too!

Now let's move on to your second question:

2. Using (1), prove by induction on n that R o R^n = R^(n+1)

I'm not going to say much here; I have a feeling you can do this.
nth case will be R o R^n = R^(n+1). You want to prove that
R o R^(n+1) = R^(n+2). How might you use the first equation to get
the second? Let me know if you need more help on this one.

Now let's move on to three. Below is the question and what you tried
to do to solve the problem.

3. Suppose R is symmetric. show that R^n is symmetric for all pos
integers n.

On this one I got lost from the start. With my base case = 1, how can
I say that R is symmetric? Then I assume R^n.  Well I've jumped ahead
at this point and assumed that R is symmetric (can I assume twice?).
Well then (a,b) and (b,a) belong to R and (a, b) and (b,a) belong to
R^n. Then applying the the fact that R o R^n = R^(n+1), I get that
(a, a) and (b,b) belong to R^(n+1) but this doesn't prove anything.

You are off to a promising start; you are right that induction will work
best for solving this problem. Before we look at the solution to the
problem, let me respond point by point to what you wrote above.

First, it is fine to say that R is symmetric because in the statement of
the problem, we are told that we are dealing with a symmetric relation.

Second, you must be very careful when you use the definition of
symmetric relation. Above you state that (a,b) and (b,a) belong to R and
that (a,b) and (b,a) belong to R^n. I assume you got that from the
definition. However, the definition says something a little different.
A relation R is symmetric if for all (x,y) in R, we have that (y,x) is
also in R.  Now remember that R and R^n are different sets. So, while
(a,b) might be in R, it is not necessarily in R^n. Can you find an
example of a relation R where an ordered pair is in R but not in the
relation R^n for n>1?

So, your statement should have read "if (a,b) is in R then so is (b,a);
if (c,d) is in R^n so is (d,c)." Thus, your result that (a,a) and (b,b)
are in R^(n+1) is fallacious because of the preceding mistake.

Okay, now that we have that cleared up, let's attack this problem. We
already said that we would do it by induction, so let's take care of our
base case first. We are trying to prove that R^n is symmetric for all n
if R is symmetric, so the n = 1 case corresponds to R^1 = R.  So, we must
show that R is symmetric. But R is symmetric by the very assumption of
the problem! Whew - that was simple!

Let's move on. We assume the nth case holds. Thus, we assume that
R^n is symmetric. We now want to show that the (n + 1)st case holds;
that is, we want to show that R^(n+1) is symmetric. How do we do that?
We use the definition of symmetry. R^(n+1) is symmetric if for all (x,y)
in R^(n+1) we have that (y,x) is in R^(n+1) as well.

Suppose that (x,y) is in R^(n+1). We will show that (y,x) is in R^(n+1),
thus finishing the inductive proof. How can we proceed from this
assumption? What do we know about R^(n+1)? We know from number 2
that R^(n+1) = R o (R^n), right?  By the definition of composition,
we know that if (x,y) is in R o (R^n), there must exist a z in A such
that xRz and z(R^n)y.

Now what do we do? What do we know about R and R^n?  They are symmetric!
So, since xRz we must have that zRx. Similarly, because z(R^n)y, we
have that y(R^n)z.

I bet you can finish the problem from here. Remember that you want to
prove (y,x) is in R^(n+1). Use the facts that z(R^n)y and y(R^n)z to
show that (y,x) is in R^(n+1). We've already done most of the work!

I hope this helps you.  Please write to us if you have any more
questions about relations or any other math topic.

-Doctor Sydney,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
College Logic
High School Logic
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search