3. Relation

relation

A (binary) relation R from a set X to a set Y is a subset of XxY.

If (x, y)∈R, we write xRy and say that x is relation to y.

If X=Y, we call R a (binary) relation on X.

domain of R is Dom(R) = { x∈X| (x, y)∈R for some y∈Y}.

range of R is Rng(R) = { y∈Y|(x,y)∈R for some x∈X}

digraph of a relation R on a set X

① draw dots to represent the elements of X.

② If the element (x,y) is in R, draw an arrow from x to y.

Properties of a relation R on a set X

- reflexive             xRx for all x∈X.

- symmetric           if xRy, then yRx.

- anti-symmetric    if xRy and yRx, then x=y.

- transitive            if xRy  and yRz, then xRz.

- If R is reflexive, anti-symmetric, transitive, then R is a partial order. and If (x, y) or (y, x)∈R for      every pair of elements in X, then R is total order.

inverse of R

Let R be a relation from X to Y.

the inverse of R, denoted R^-1, is the relation from Y to X defined by

R^-1 = { (y, x)| (x, y)∈R}

composition

Let R1 be a relation from X to Y and R2 be a relation from Y to Z.

the composition of R1 and R2, denote R2∘R1, is the relation from X to Z defined by

R2∘R1 = { (x, z)| (x, y)∈R1 and (y, z)∈R2 for some y∈Y}.

equivalence relation

R is an equivalence relation if R is reflexive, symmetric and transitive.

equivalence relations and partitions

Let S be a partition of a set X. if for some set T in S, x, y are in T, Define xRy on X. Then R is an equivalence relation on X. 

---

Let R be an equivalence relation on a set X. For each a∈X, let

[a] = { x∈X | xRa }

then 

S = { [a] | a∈X}

is a partition of X.

the sets [a] are called the equivalence classes of X given by the relation R.

The matrix of relation

Let X,Y be sets and R a relation from X to Y.

Write the matrix A of the relation R as follows:

- Rows of A = elements of X

- Columns of A = elements of Y

- Element a(ij) = if the element of X in low i and the element of Y in column j are related, it is 1 else 0.

Example:

Let X = {1,2,3}, Y={a,b,c,d}

Let R = {(1.a), (1,d), (2,a), (2,b), (2,c)}

The matrix A of the relation R is

The product of matrices

Let R1 be the relation from X to Y and let R2 be the relation from Y to Z.

Let A1 be the matrix of R1 and let A2 be the matrix of R2.

The product of these matrices is A1A2.

if the (i,k)th entry in A1A2 is nonzero, then (Xi, Zk)∈R2∘R1.

since the (1,1)th entry in A1A2 is nonzero, (X1,Z1)∈R2∘R1.

The matrix of a relation on a set X

Let A be the square matrix of a relation R from X to itself.

Let A^2 is the matrix product AA.

- R is reflexive if and only if all terms a(ii) in the main diagonal of A are 1.

- R is symmetric if and only if a(ij) = a(ji) for all i and j.

- R is transitive if A^2=A(whenever c(ij) in C = A^2 in nonzero then entry a(ij) is A is also nonzero.).