2.3. Pictorial Representatives of Relations a. Relations on f

Let ^ be a relation on the set F of real numbers. That is, ^ is a subset of

F ² = F X F. Frequently, ^ consists of all ordered pairs of real numbers which satisfy some given equation F (.x, y )= 0 (such that .x² + y² = 25).

Since F ² can be represented by the set of points in the plane, we can picture ^ emphasizing those points in the plane which belong to The pictorial representation of the relation in sometimes called the graph of the relation. For example, the graph

of the relation ..² + y² = 25is a circle having its center at the origin and radius 5.

B. Directed Graphs of Relations on Sets

There is an important way of picturing a relation ^ on a finite set. First we write down the elements of the set, and then we draw an arrow from each element .. to each element y whenever .. is related to y. This diagram is called the directed graph of the relation.

Let us find the directed graph of the following relation ^ on the set ^ = {1,2,3,4}:

^ = {(1,2), (2,2), (2,4), (3,2), (3,4 )(4, l), (4,3)}

There is an arrow from 2 to itself, since 2 is related to 2 under ^ .

C. Pictures of Relations on Finite Sets

Suppose ^ and R are finite sets. There are two ways of picturing a relation ^ from ^ to R.

a) Form a rectangular array (matrix) whose rows are labeled by the elements of ^ and whose columns are labeled by the elements of R. Put 1 or 0 in each position of the array according as ^ E ^ is or is not related to ^ E R. This array is called the matrix of the relation.

For the relation ^ = {(1, y), (1, z), (3, y)} we have

Such matrix is called a Boolean matrix since its elements are only 0 or 1. b) Let us write down the elements of ^ and the elements of R in two disjoint disks, and then draw an arrow from ^ E ^ to ^ E R whenever ^ is related to This picture will be called the arrow diagram of the relation.

D. Composition of Relations

Let R and C be sets, and ^ be a relation from ^ to R and let ^ be a relation from R to C. That is, ^ is a subset of ^ x R (^ c ^ x R) and ^ ^ R x C. Than ^ and ^ give rise to a relation from ^ to C denoted by ^^ and derived by: )c if for some ^ E R we have ^^^ and ^^c.

That is, ^^ = {(a, c) there exists ^ E R for which (^, ^) E R and (^, c) E ^}. The relation ^^ is called the combination of ^ and

and

let

Let ^ = {1,2,3,4}, R = {¿7, c, ^}, C = {.., y, z} ^ = {(1, ^), (2, ^), (3, ^), (3, ^), (3, ^)} and ^ = .), z), (c, y), (^, z)}. Consider the arrow diagrams of ^ and

Observe that there is an arrow from 2 to ^ which is followed by an arrow ^om ^ to z. We can view two arrows as a "path" which "connects" the element 2 E ^ to the element z E C. Thus )z since 2 ^^ and Similarly there is a path from 3 to .. and a path ^om 3 to z. ). and )z . Accordingly ^^ = {(2, z), (3,.), (3, z)}.

2.4. Inverse Relation

Let ^ be any relation from a set ^ to a set R. The inverse of denoted by ^ "¹, is the relation ^om R to ^ which consists of those ordered pairs, when reversed, belong to that is,

^-¹ ={(^, ^) ^)E

For example, let ^ = {1,2,3} and R = {.., y, z}. Then the inverse of ^ = {(1, y), (1, z), (3, y )}is ^-¹ = {(y,1), (z,1), (y,3)}.

Clearly, if ^ is any relation, then (^ ) = ^ . Also, the domain and range of ^ are equal, respectively, to the range and domain of Moreover, if ^ is a relation on then ^ is also a relation on