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 
kick in and help you out.

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, 
go on to the dotted line; we'll answer your questions there.

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.

Okay, enough on functions. After all, your question is about relations! 
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. 
Carefully write down your base case - it's pretty simple.  Your 
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/