Relations Binary relation:
There are many relations in mathematics :"less than" , "is parallel to ","is a subset of", etc. These relations consider the existence or nonexistence of a certain connection between pairs of objects taken in a definite order. We define a relation simply in terms of ordered pairs of objects.
Product sets:
Consider two arbitrary sets A and B. The set of all ordered pairs (a,b) where a?A and b?B is called the product, or cartesian product, of A and B.
A × B = {(a,b) : a?A and b?B}
Example: Let A = {1,2} and B = {a ,b ,c} then
A × B = {(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)}
Also, A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}
- The order in which the sets are considered is important, so A×B ? B ×A.
Let A and B be sets. A binary relation, R, from A to B is a subset of A×B. If )x,y) ?R, we say that x is R-related to y and denote this by xRy
if )x,y) ?R, we write y and say that x is not R-related to y .
if R is a relation from A to A ,i.e. R is a subset of A × A, then we say that R is a relation on A.
The domain of a relation R is the set of all first elements of the ordered pairs which belong to R, and the range of R is the set of second elements.
Example 1:
Let A = {1, 2, 3, 4}. Define a relation R on A by writing (x, y) ? R if x < y. Then R = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}.
Example 2:
let A = {1,2,3} and R = {(1,2),(1,3),(3,2)}. Then R is a relation on A since it is a subset of A×A with respect to this relation:
1R2, 1R3, 3R2 but (1,1)?R & (2,1)?R
The domain of R is {1,3} and The range of R is {2,3} Example 3:
Let A = {1, 2, 3}. Define a relation R on A by writing (x, y) ? R , such that a?b, list the element of R
aRb ? a?b , a,b?A
? R = {(1,1),(2,1), (2,2), (3,1), (3,2), (3,3)}.
Example 4:
A relation on the set Z of integers is “m divides n.” A common notation for this relation is to write m|n when m divides n. Thus 6 | 30 but 25.
Representation of relations:
1) By language
2) By ordered pairs
3) By arrow form
4) By matrix form
5) By coordinates
6) By graph form
Example:
Let A = {1,2,3}, the relation R on A such that: aRb ? a>b; a,b?A
1) By language:
R={(a,b) : a,b ?A and aRb ? a>b}
2) By ordered pairs
R = {(2,1),(3,1),(3,2)}
3) By arrow form
4) By matrix form
5) By coordinates
6) By graph form
TYPES OF RELATIONS:
Properties of relations: Let R be a relation on the set A
1) Reflexive : R is reflexive if : ? a ?A ? aRa or (a,a) ? R ; ? a, b ?A. . Thus R is not reflexive if there exists a ? A such that (a, a) ? R.
2) Symmetric : aRb ? bRa ? a,b ?A. if whenever (a, b) ? R then (b, a) ? R. Thus R is not symmetric if there exists a, b ? A such that (a, b) ? R but (b, a) ? R.
3) Transitive : aRb ? bRc ? aRc. that is, if whenever (a, b), (b, c) ? R
then (a, c) ? R. Thus R is not transitive if there exist a, b, c ? R such that (a, b), (b,
c) ? R but (a, c) ? R.
4) Equivalence relation : it is Reflexive & Symmetric & Transitive. That is, R is an equivalence relation on S if it has the following three properties:
a - For every a ?S, aRa. b- If aRb, then bRa.
c- If aRb and bRc, then aRc.
5) Irreflexive : ? a ?A (a,a) ? R
6) AntiSymmetric : if aRb and bRa ? a=b
the relations ?,? and ? are antisymmetric
Example 5: Consider the relation of C of set inclusion on any collection of sets:
1) A ? A for any set, so ? is reflexive
2) A ? B dose not imply B ? A, so ? is not symmetric
3) If A ? B and B ? C then A ? C, so ? is transitive
4) ? is reflexive, not symmetric & transitive, so ? is not equivalence relations
5) A ? A, so ? is not Irreflexive
6) If A ? B and B ? A then A = B, so ? is anti-symmetric
Example 6: If A ={1,2,3} and R={(1,1),(1,2),(2,1),(2,3)}
Is R equivalence relation ?
1) 2 is in A but (2,2) ? R, so R is not reflexive
2) (2,3) ? R but (3,2) ? R, so R is not symmetric
3) (1,2) ? R and (2,3) ? R but (1,3) ? R, so R is not transitive So R is not Equivalence relation
Example 7 : What is the properties of the relation =?
1) a=a for any element a ? A, so = is reflexive
2) If a = b then b = a, so = is symmetric
3) If a = b and b = c then a = c, so = is transitive
4) = is (reflexive + symmetric + transitive), so = is equivalence
5) a = a, so = is not Irreflexive
6) If a = b and b = a then a = b, so = is anti-symmetric
Remark:The properties of being symmetric and being antisymmetric are not negatives of each other. For example, the relation R = {(1, 3), (3, 1), (2, 3)} is neither symmetric nor antisymmetric. On the other hand, the relation R = {(1, 1), (2, 2)} is both symmetric and antisymmetric.
-Reflexive Closures
Let R be a relation on a set A. Then:
R ? {(a, a) | a ? A} is the reflexive closure of R. In other words, reflexive(R) is obtained by simply adding to R those elements (a, a) in the diagonal which do not already belong to R.
-Symmetric Closures
R ? R?1 is the symmetric closure of R. in other words, symmetric(R) is obtained by adding to R all pairs (b, a) whenever (a, b) belongs to R.
EXAMPLE : Consider the relation R = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)} on
the set A = {1, 2, 3, 4}.Then
reflexive(R) = R ? {(2, 2), (4, 4)} and
symmetric(R) = R ? {(4, 2), (3, 4)}
-Transitive Closure
R* is the transitive closure of R, where:
R*= R ? R2 ? R3 ? …. ? Rn and R2 = R?R and Rn = Rn?1?R
Theorm : Suppose A is a finite set with n elements and Let R be a relation on a set A
with n elements. Then : transitive (R) = R ? R2 ? R3 ? …. ? Rn
EXAMPLE : Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then:
R2 = R?R = {(1, 3), (2, 3), (3, 3)} and
R3 = R2?R = {(1, 3), (2, 3), (3, 3)} then
transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}
Inverse relations:
R-1 = {(b,a) : (a,b) ? R}
Example 1 :
Let R be the following relation on A ={1,2,3} R = {(1,2),(1,3),(2,3)}
? R-1 = {(2,1),(3,1),(3,2)}
The matrix for R :
and
MR-1 is the transpose of matrix R
Composition of relations: Let A, B, C be sets and let :
R : A ? B ( R? A ? B)
S : B ? C (S ? B ?C)
There is a relation from A to C denoted by R ? S (composition of R and S) : A ? C
R ? S = {(a,c) : ? b ? B for which (a,b) ? R and (b,c) ? S}
Example : let A ={1,2,3,4}
B = {a, b, c, d}
C = {x, y, z}
R = {(1,a),(2,d),(3,a),(3,d),(3,b)}
S = {(b,x),(b,z),(c,y),(d,z)}
Find R ? S ? Solution :
1) The first way by arrow form
There is an arrow (path) from 2 to d which is followed by an arrow from d to z 2Rd and dSz ? 2(R ? S) z
and 3(R?S)x and 3(R?S)z
so R ? S = {(3,x),(3,z),(2,z)}
2) The second way by matrix:
R ? S = MR . MS =
R ? S = {(2,z),(3,x),(3,z)}
Theorem 2.1: Let A, B, C and D be sets. Suppose R is a relation from A to B, S is a relation from B to C, and
T is a relation from C to D. Then (R ? S) ? T = R ? (S ? T )
n-ARY RELATIONS
All the relations discussed above were binary relations. By an n-ary relation, we mean a set of ordered n-tuples. For any set S, a subset of the product set Sn is called an n-ary relation on S. In particular, a subset of S3 is called a ternary relation on S. EXAMPLE
(a) Let L be a line in the plane. Then “betweenness” is a ternary relation R on the points of L; that is, (a, b, c) ? R, if b lies between a and c on L.
(b) The equation x2 +y2 +z2 = 1 determines a ternary relation T on the set R of real numbers. That is, a triple (x, y, z) belongs to T if (x, y, z) satisfies the equation, which means (x, y, z) is the coordinates of a point in R3 on the sphere S with radius 1 and center at the origin O = (0, 0, 0).
Home work:
1) Consider the following relations on the set A = {1, 2, 3}:
R = {(1, 1), (1, 2), (1, 3), (3, 3)},
S = {(1, 1)(1, 2), (2, 1)(2, 2), (3, 3)},
T = {(1, 1), (1, 2), (2, 2), (2, 3)}
? = empty relation
A× A = universal relation
Determine whether or not each of the above relations on A is:
(a) reflexive; (b) symmetric; (c) transitive; (d) antisymmetric.
2) for the relation R = {(a, a), (a, b), (b, c), (c, c)} on the set A = {a, b, c}. Find: (a) reflexive(R); (b) symmetric(R); (c) transitive(R).