Study Guides for Discrete Mathematics
Section 6.1 - Relations and Their Properties
Relations, in their most intuitive form, are relationships between objects. For example "Less Than" is a relationship between integers.
It is important to note that not all ordered pairs of objects are related. The ordered pair (1,2) is part of the less than relation but (2,1) is not. In fact some objects may not be related in either order. For example, "son of" may define a relation on the males of a species. However, given two males A and B, it is likely that neither (A,B) nor (B,A) is a member of the relation. I.e. A is not the son of B and B is not the son of A.
More formally, a binary relation, R, may be defined to be a subset of the crossproduct of two sets.
I.e. R Í A X B
It is quite common for a relation to be defined on the crossproduct of set, say A, and itself, A X A.
Relations may be illustrated by using matrices and graphs (see pages 356 and 357 in the text).
Reflexive Relations
A relation is reflexive iff (a,a) is a member of the relation for every element, a, of A. (See definition 3 on page 358).
Symmetric Relations
In plain language, a relation, R, is said to be symmetric iff the "reverse mate" of every ordered pair in the relation is also in the relation. I.e. if (a,b) is in the relation then so is (b,a). (See definition 4 on page 359 for a formal definition).
Antisymmetric Relations
A relation, R, is said to be antisymmetric iff the "reverse mate" of every ordered pair in the relation is not also in the relation. I.e. if a is not the same as b and if (a,b) Î R then (b,a) Ï R.
Another way of stating this is the following:Example: Determine if the less than relation is antisymmetric.
If a < b then it is not true that b < a. Therefore the less than relation is antisymmetric.
In fact the less than or equal to relation is also antisymmetric sinceTransitive Relations
It is a little more difficult to give an intuitive definition of transitive relations. One might characterize a transitive relationship as a relationship that may be inherited. A more formal definition follows.
A relation R Í A X A is transitive iff (a,b) Î R /\ (b,c) Î R Þ (a,c) Î R.
Examples of transitive relations are easy to find.
Example: The relation "Taller Than" defined on people is transitive.
If A is taller than B and B is taller than C then A is taller than C.
Example: Determine if the relation R = {(a,b) | b = 2·a /\ a,b Î Z} is transitive.
Note that the elements of R are those where the second integer of the ordered pair is twice the first integer of the ordered pair.
(1,2) Î R and (2,4) Î R but (1,4) Ï R. Therefore, R is not transitive.
The Relation Dichotomy
It is important to keep in mind that relations have a split personality both of which parts are completely compatible mathematically. Intuitively, a relation defines a relationship between the elements of a set.
For example, greater than defines a relationship between integers.
A relation is defined mathematically to be simply a subset of the crossproduct of two sets. As such it has all the properties of sets. We studied many of these properties earlier in the semester.
Combining Relations
Since relations are sets we may combine relations by the same means we combine sets. I.e. we may define the union, intersection, and difference of two relations just as we would for any two sets whose elements come from a common universe.
Example:
Let Z be the integers and let R1 and R2 be the relations defined below.
R1 = {(a,b) | a <= b /\ a,b Î Z}
R2 = {(a,b) | a >= b /\ a,b Î Z}
Then,
R1 Ç R2 is the equal to relation,
R1 - R2 is the less than relation,
R2 - R1 is the greater than relation, and
R1 È R2 is the universal relation, i.e. all pairs of Z X Z are included.
Composition of Relations
We may compute the composition of two relations in a manner similar to the method of computing the composition of two functions.
The composition of two relations R1 and R2 denoted R2 o R1 is defined as follows:
R2 o R1 = {(a,c) | $ b, (a.b) Î R1 /\ (b,c) Î R2}
Note that R2 o R1 consists of precisely those ordered pairs defined above; no more, no less.
Also, pay close attention to the fact that the notation seems to be backwards. I.e. the first ordered pair in the definition comes from R1 and the second comes from R2 yet the composition is written in the opposite order, R2 o R1. Although this notation is consistent with functional composition it can be confusing. It is important to keep the order straight in one's mind in order to obtain correct results.
Example: Let R1 = {(a,b) | b = 2·a /\ a,b Î Z} i.e. R1 is those pairs of integers where the second component is twice the first.
Let R2 = {(a,b) | b = a + 3 /\ a,b Î Z} i.e. R2 is those pairs where the second component is 3 more than the first.
Determine R2 o R1 and R1 o R2
R2 o R1 = {(a,c) | c = 2· a + 3}
R1 o R2 = {(a,c) | c = 2· (a + 3)}
Clearly R2 o R1 ¹ R1 o R2.
Powers of a Relation
When a relation is repeatedly composed with itself the result is written in exponential notation and is defined recursively.
R1 = R and RN+1 = RN o R
Example: Use the definition of composition of relations to define R2.
Recall the definition R2 o R1 = {(a,c) | $ b, (a.b) Î R1 /\ (b,c) Î R2}.
Substituting R for both R2 and R1 yields the following:
R2 = R o R = {(a,c) | $ b, (a.b) Î R /\ (b,c) Î R}
Similarly we may define RN+1 = RN o R = {(a,c) | $ b, (a.b) Î R /\ (b,c) Î RN}
The above can be used to help prove several results about relations including Theorem 1 on page 364.