Next: Equivalence relations Up: NOTES ON RELATIONS Previous: Relations

# 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 is related to a. If we let R denote the relation then we have aRa for each . 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 defined by if is odd. Then 1 1 and 3 3 but 0 0 and so the relation is not reflexive.

A relation on A is said to be irreflexive if for each 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 then . 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 then . 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.

Next: Equivalence relations Up: NOTES ON RELATIONS Previous: Relations

Peter Williams
Wed Nov 20 00:52:35 PST 1996