Self Online Study - Mathematics - Relations and Functions - Relations

A relation from A to B is a rule that assigns elements of A to elements of B. A relation from a set A to itself is referred to as a relation on A. An example of a relation would be a function but not all relations are functions. Indeed there are two elementary examples to show this. The first is the relation that assigns to each element of A every element of B. The second is the empty relation that assigns no element of A to any in B.

A relation expresses just what we think of in every day life. For example we might have two sets of students and say that a student in the first set is related to a student in the second set if they have taken a class together. Certainly we might envisage a situation where a student in the first set is related to several students in the second set as well as a student in the first set who is not related to anyone in the second set.

Another way to view a relation is as a subset of the Cartesian product A×B . For our two elementary examples above, the relations would be φ and A×B respectively. You have probably seen relations on the real numbers, R. For example, a real number x is related to a real number y if x2 + y2 =1 . The picture of this in the plane is the unit circle.

To picture a relation between finite sets we can draw a table. The columns are indexed by the elements of A and the rows by the elements of B. If a belong to A is related to b belongs to B then we put a 1 in the (a,b) position of the table, otherwise we put a 0. Here is an example for A={1,2,3} and B={x,y}.



This shows that 3 is related to both x and y but 2 is not related to either. As we can think of a relation from A to B as a subset of A×B then if A has n elements and B has m elements then there are 2mn possible relations. Relations can also be specified by a formula (as in the unit circle above) or in a descriptive way (as for the student example).

However, it is possible that two apparently different relations yield the same subset of A×B. Another way to represent a relation between finite sets is to use a digraph. We represent each element of the sets A and B as dots or vertices. If a is related to b we draw an arrow from the vertex representing a to the vertex representing b. Note that if the same symbol is used in both sets, we think of each as distinct objects and draw a vertex for each. The picture below gives a digraph of the example that we tabulated above.



Relations on a set
In this section we restrict ourselves to talking about relations on a set A and define some properties a relation may have.

A relation on A is said to be reflexive if for each a belongs to A a is related to a. If we let R denote the relation then we have aRa for each a is belong to A.. An example of a non reflexive relation is the relation "is the father of" on a set of people. As no person is the father of themself the relation is not reflexive. As another example consider the relation on {1,2,3} defined by a b if is odd. Then 11 and 3 3 but 00 and so the relation is not reflexive.

A relation on A is said to be irreflexive if for each a is belongs to A a is not related to a. This is not the negation of the definition of reflexive. The relation "is the father of " is irreflexive.

A relation R on A is symmetric if given a ~ b, b ~ a The relation "is the sister of" is not symmetric on a set that contains a brother and sister but would be symmetric on a set of females. The empty relation on a set is an example of a symmetric relation since the statement "if aRb" is always false.

A relation R on A is antisymmetric if given a ~ b, b a . Again, it is possible to have relations that are neither symmetric nor antisymmetric.

A relation R on A is transitive if given aRb and bRc then aRc. The relation "is an ancestor of" on a set of people is transitive as is the empty relation on a set.

For a finite set, if we use a table to represent a relation then it is easy to spot some of these properties provided we list the column elements across the top of the tabe in the same order as the row elements down the table. The relation is reflexive if the diagonal entries are all 1 and irreflexive if all the diagonal entries are zero. The relation is symmetric if the lower triangle below the diagonal is the reflection across the diagonal of the upper triangle. It is antisymmetric if whenever the (a,b) position is 1 then the (b,a) position is 0. Note that it is OK to have both positions 0 in this case. Unfortunately, we can not observe transitivity so readily.

Equivalence relations
A relation ~ on A is an equivalence relation if it is reflexive, symmetric and transitive. An example of such is equality on a set. One might think of equivalence as a way to glob together elements that can be considered the same relative to a property. That is elements become indistinguishable relative to the relation. For example in arithmetic we don’t think twice about 1/2 and 2/4 as having the same value but they are different objects. In geometry, similarity of triangles is an equivalence relation. A right angled triangle with legs of length 3 and 4 and hypotenuse of length 5 is not the same as one with lengths 6, 8 and 10. Yet, we think of them as equivalent because the ratios of the corresponding sides are the same.

For each a belongs to A , we define the equivalency class containing a to be the set of those elements which are equivalent to a. We denote this set by [a] although you should be aware that there is no standard notation for this. Some authors use and so on. The equivalence classes have some interesting properties.
First, no equivalence class is empty since a| A | . Two equivalence classes are either equal or disjoint. In fact, a and b are equivalent if and only if [a] = [b]. Each element of A belongs to some equivalence class ( in fact). The union of all the equivalence classes is A. We say that the equivalence classes partition A. A partition of A is a collection of non empty disjoint subsets of A and whose union is A. Thus the equivalence classes of a relation are a partition. Each equivalence relation on a set partitions the set into its equivalence classes but also for each partition of the set there is an equivalence relation whose equivalence classes are the sets in the partition. As an example, if A={1,2,3}one partition is {1,2} and {3}. Consequently, there is an equivalence relation on A whose equivalence classes are these two subsets.

One problem is how should we refer to the equivalence classes? As we noted above [a] = [b] whenever a and b are equivalent. What we do is choose one and only one element of each equivalence class to represent the class. That element is called a class representative. The set of representatives is called the set of equivalence class representatives. There are usually many such ways to construct this set of representatives.

If is an equivalence relation on A then the factor set denoted by A/~ is the set consisting of the equivalence classes of For the example we gave above, our equivalence classes are [1] and [3]. Thus the factor set is {[1], [3]}. We have chosen 1 to represent the equivalence class {1,2} and (no choice) 3 to represent the equivalence class {3}. Thus the set of class representatives is {1,3}. Note the similarity with the factor set. The only difference is that the elements of the factor set have [ and ] around the number (and of course are subsets of A whereas the things in the set of class representatives are elements of A). Because of this, we often abuse notation and write the set of class representatives for the factor set, letting the context make it clear how we are using a class representative.