next up previous
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 tex2html_wrap_inline124 a is related to a. If we let R denote the relation then we have aRa for each tex2html_wrap_inline124 . 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 tex2html_wrap_inline188 on tex2html_wrap_inline190 defined by tex2html_wrap_inline192 if tex2html_wrap_inline194 is odd. Then 1 tex2html_wrap_inline188 1 and 3 tex2html_wrap_inline188 3 but 0 tex2html_wrap_inline200 0 and so the relation is not reflexive.

A relation on A is said to be irreflexive if for each tex2html_wrap_inline124 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 tex2html_wrap_inline208 then tex2html_wrap_inline210 . 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 tex2html_wrap_inline208 then tex2html_wrap_inline218 . 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 up previous
Next: Equivalence relations Up: NOTES ON RELATIONS Previous: Relations

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