Binary Relations on Sets

The term 'relation' is used to describe a relationship between one thing and another. In this case, the 'one thing and another' we are discussing happen to be the elements of sets.  Given elements a and b, a relationship between a and b can be described in any number of ways. For instance: a < b, a = b, and a² + 1 > b are all potentially legitimate relationships between these 2 elements.

The notation used to indicate a relation between 2 elements a and b is denoted by a R b .  Suppose that a relation is defined as a + 1 = b.  If a and b are both elements of the set of integers (a, b  Z), then 0 R 1, 5 R 6, -3 R -2 are all legitimate relations. If, on the other hand, you wish to describe elements which are not related by a defined relationship, the notation ab is used; for example, 62.  

A binary relation describes a relationship between the elements of 2 sets. If A and B are sets, then a binary relation R from A to B is a subset of the Cartesian product of A and B (A x B).

Example: Let A = {1, 2, 3} and B = {4, 5, 6}. Let R be a binary relation from A to B as follows:

List the ordered pairs in A x B and determine which pairs are in R, then check your results against our answer.

Like functions, binary relations can be represented by arrow diagrams. To create an arrow diagram for the above example, create a region for A and list the elements as points, then do the same for B. Draw an arrow from each x in A to each y in B where x R y., then check your answer.

Inverse Relations

An inverse relation is pretty much what its name implies. If R is a relation from A to B, then the inverse relation R^-1 goes from B to A, and inverts the order of elements in the ordered pairs in R.

Note that for (y, x) to belong to R^-1 the original relation, (x, y) R, must exist.

Functions and Relations

Drawing from what has been covered so far, a binary relation is a subset of Cartesian products, and Cartesian products are defined as sets of ordered pairs. Therefore, binary relations can be defined using only set theory. We have already defined functions in Section 4.1; now, it is possible to define a function in terms of binary relations as follows:

A function F from set A to set B is a relation from A to B with 2 properties:

1. for every element x in A, there exists an element y in B such that (x, y)  F; and
   
   
2. for all elements x in A and y and z in B, if (x, y)  F and (x, z)  F, then y = z.
   

A function F from A to B is represented symbolically as:

y = F(x)  (x, y)  F

It is important to remember that the elements are ordered pairs - in other words, x and y must be used in the correct order! y = F(x) if and only if y is the second element of an ordered pair in F where x is the first element.

It is also possible to define a binary relation on a single set. Let S be a set. A binary relation on set S is relation from S to S.  For example, let S = {-2, -1, 0, 1, 2}, and define a relation R on S as follows:

for all x, y  S,        x R y x = -y

R = {(-2, 2), (-1, 1), (0, 0), (1, -1), (2, -2)}.  Any element of S may be used as an x or y element and the same element may be used for both.  Because the relation has been defined on a single set, an arrow diagram for S becomes a directed graph. Instead of creating 2 regions, and mapping from one region into another, we list the elements of S as points, and draw the appropriate lines and arrows from one point to another.

Try to draw the arrow diagram for the above example, then check your work.

N-ary Relations

Thus far, we have covered only relation concepts in terms of unary and binary relationships. But it should be intuitively obvious that a relationship may involve more than 1 or 2 sets, such as a ternary (3 way) or quaternary (4 way) relationship.  These terms specify the number of participating entities (sets) in a relationship; otherwise known as the degree of the relationship.

So, if it is possible to define a relationship with 1-4 entities, it is also possible to define relationships upon 5, 6, 7, etc. entities. In other words, a relationship may be defined upon n entities, which is known as an n-ary relation. Just as a binary relation is a subset of the Cartesian product of 2 sets, an n-ary relation is a subset of the Cartesian Product of n sets.

More formally, given sets A₁, A₂, . . ., A_n, an n-ary relation R defined on these sets is a subset of the Cartesian product of A₁ x A₂ x . . . x A_n,

Reflexive, Symmetric, & Transitive Properties

Let S = {-1, 1, 2}, and let R be some relation defined on S.

A relation R is reflexive iff, for any x  S, x R x.

Example: let R be defined as follows:

for all x, y  S,        x R y xy > 0

Then R is reflexive, since:

-1 R -1		-1 * -1 > 0
1 R 1		1 * 1 > 0
2 R 2		2 * 2 > 0

A relation R is symmetric iff, for all x, y  S, if x R y then y R x.

Example: let R be defined as follows:

for all x, y  S,        x R y x²+y > 0

R is symmetric as follows:

-12+ 1 > 0	and	12+ -1 > 0
-12+ 2 > 0	and	22+ -1 > 0
12+ 2 > 0	and	22+ 1 > 0

Note that this relationship is also by definition reflexive: if x R x. then x R x.

A relation R is transitive iff, for all x, y  S, if x R y and y R z then x R z.

Example: let R be defined as follows:

for all x, y, z  S,        x R y x²+1 > y

R is transitive as follows:

for x = -1, y = 1, and z = 2;

-12+ 1 > 1		x2+1 > y
12+ 1 > 2		y2+1 > z
-12+ 1 > 2		x2+1 > z

This relationship holds for any other combination of x, y, z  S.

It is important to realize that, when defining these properties, the elements are not defined as distinct; that is, the property must hold even where the same value is used for x, y and z. Also note that these properties are universal in nature; if just one example can be found that contradicts a property, then the relation does not have that property.

Transitive Closure

Suppose you are given a set A = {a, b, c, d, e}, and a relation R defined on set A as R = {(a, e), (e, d), (d, c), (c, b)}.

Consider the directed graph of R, diagram 4.5.a.

What lines would have to be added to make this directed graph transitive?

Beginning from a and working our way around the graph, you would need to add an arrow from a to d (a,d), from e to c (e, c), and from d to b (d, b), as in diagram 4.5.b. What you have done in essence is to add ordered pairs to R to form a new relation, which we will call R⁺.

Consider diagram 4.5.b; R⁺ = {(a, e), (e, d), (a,d), (d, c), (e, c), (c, b), (d, b)}.  Also note that R R⁺ -- that is, all ordered pairs contained in R are also contained in R⁺.

However, R⁺ is still not transitive. Adding new lines has created new subsets of elements which are not transitive - for instance, a R d and d R b, but a  b. More lines must be added to create a transitive graph, as shown in diagram 4.5.c.  The new relationship which has been created, R^t, is transitive.

The process of creating a transitive relation R^t from an intransitive one, R, has been accomplished by systematically adding ordered pairs to R. More specifically, we wish to add the least number of ordered pairs possible in order to obtain a transitive relation; the new relation created is called the transitive closure of R.

The transitive closure of a relation R must satisfy 3 properties:

1. R^t must be transitive;
   
   
2. R must be a subset of R^t,  (R R⁺); and
   
   
3. If S is any other transitive relation such that R  S, then R^tS.
   
   
   
   

   Go to next section review.
   Go to Class Agenda.