Definition 1.1. Any subset of A × B is called a relation between A and B.

Any subset of A × A is called a relation on A.

In other words, if A is a set, any set of ordered pairs with components in A is a relation on A. Since a relation R on A is a subset of A × A, it is an element of the powerset of A × A, i.e. R ⊆ P(A × A). If R is a relation on A and 〈x,y〉 ∈ R,  then we also write xRy, read as “x is in R-relation to y”, or simply, x is in relation to y, if R is understood.

Example 1.1 Let A = {2, 4, 6, 8}, and define the relation R on A by hx,yi ∈ R iff x divides y. Then,

Observe that each number is a divisor of itself.

2. Let A = N, and define R ⊆ A × A by

                  xRy iff x and y have the same remainder when divided by 3.

Since A is infinite, we cannot explicitly list all elements of R; but, for example

Observe, that xRx for x ∈ N and, whenever xRy then also yRx.

3. Let A = R, and define the relation R on R by xRy iff y = x² . Then R consists of all points on the parabola y = x².

4. Let A = R, and define R on R by xRy iff x · y = 1. Then R consists of all pairs 〈x, 1/x〉, where x is non-zero real number.

5. Let A = {1, 2, 3}, and define R on A by xRy iff x + y = 7. Since the sum of two elements of A is at most 6, we see that xRy for no two elements of A; hence, R = ∅.

For small sets we can use a pictorial representation of a relation R on A: Sketch two copies of A and, if xRy then draw an arrow from the x in the left sketch to the y in the right sketch.

Let A = {a, b,c, d,e}, and consider the relation

(1.1)

An arrow representation of R is given in Fig. 1.1

We observe that e does not appear at all in the elements of R, and that, for example,  b is not the first component of any pair in R. In order to give names to the sets of those elements of A which are involved in R, we make the following

Definition 1.2. Let R be a relation on A. Then,

                        dom R = {x ∈ A : There exists some y ∈ A such that 〈x,y〉 ∈ R}.

dom R is called the domain of R.

                  ran R = {y ∈ A : There exists some x ∈ A such that 〈x,y〉 ∈ R}

is called the range of R.

Finally, fld R = dom R ∪ ran R is called the field of R. Observe that dom R,  ran R, and fld R are all subsets of A.

Example 1.2. Let A and R be as in (1.1); then

               dom R = {a,c, d}, ran R = {a, b,c, d}, fld R = {a,b, c, d}.

2. Let A = R, and define R by xRy iff y = x² ; then,

                   dom R = R, ran R = {y ∈ R : y > 0}, fld R = R.

3. Let A = {1, 2, 3, 4, 5, 6}, and define R by xRy iff and x divides y;

R = {(1, 2),(1, 3), .. . ,(1, 6),(2, 4),(2, 6),(3, 6)},

and

dom R = {1, 2, 3}, ran R = {2, 3, 4, 5, 6}, fld R = A.

4. Let A = R, and R be defined as 〈x,y〉 ∈ R iff x²+y² = 1. Then 〈x,y〉 ∈ R iff hx,yi is on the unit circle with centre at the origin. So, dom R = ran R =

Definition 1.3. Let R be a relation on A; then R˘ = {〈y, x 〉: 〈x,y〉 ∈ R} is called the converse of R.

We obtain the converse R˘ of R if we turn around all the ordered pairs of R;  if we have a pictorial representation of R, this means that all existing arrows are reversed.

In our next definition we combine two relations to form a third one:

Definition 1.4. Let R and S be relations on A; then R ◦ S = {〈x,z〉: there is a y ∈ A such that xRy and ySz}. The operation ◦ is called the composition or the relative product of R and S.

Example 1.3.

1. Suppose that we have a pictorial representation of the relations R and S. The relation R ◦ S is the set of all pairs 〈x,z〉  such that x is in the left copy of A,z is in the right copy, and there is an arrow from x to z via an element in the centre copy of A.

2. Let A = N and R defined by xRy iff x + 1 = y, S defined by ySz iff z = 2y. Then 〈x,z〉: ∈ R ◦ S iff z = 2(x + 1):  

   〈x,z〉: ∈ R ◦ S ⇐⇒ There is some y ∈ A with xRySz

   ⇐⇒ y = x + 1 and z = 2y,

       ⇐⇒ z = 2(x + 1).

3. Let R be any relation on A; then

R◦R˘ = {〈x,z〉:: x,z ∈ dom R and there is some y ∈ ran R with xRy and zRy} :

Note that on both sides of = we have a set, so, we have to show that two sets are equal.

Proof. “⊆”: Let hx,zi ∈ R ◦ R˘; then there exists some y ∈ A such that xRyR˘z, i.e. 〈x,y〉 ∈ R and 〈 y, z 〉 ∈ R˘. Since 〈x,y〉, we have

x ∈ dom R, and since 〈 y, z 〉 ∈ R˘, we have (z, y) ∈ R; hence z ∈ dom R.

Furthermore, y ∈ ran R, as well as xRy and zRy.

“⊇”: Let 〈x,y〉 ∈ R and (z,y) ∈ R; then, 〈 y, z 〉 ∈ R˘, and thus, xRyR˘z,  i.e. 〈x,y〉 ∈ R and 〈 y, z 〉 ∈ R˘.