Next: Equivalence relations Up: Binary relations Previous: The general case   Contents

# Binary relations between elements of a set

Let be the Cartesian square of , i.e. the set of pairs of elements of , . A binary relation on is a subset of . We write iff . We can think of as a directed graph with an edge from to iff . For example, take , together with the relation denoted by and defined as follows: for any and in , if, and only if, is a multiple of . For this relation, the graph is

This can be dispayed as in Figure 2. A loop on an element means that the element is related to itself (here this occurs for every element as every natural number is a multiple of itself).

Definition 4.2.1   A relation on the set is reflexive if

Example 4.2.2   Let be a set and let be the binary relation on determined by the diagram in Figure 3.

The relation is reflexive.

Example 4.2.3   Let be the set of inhabitants of a given town. We define two relations:
1. For any two inhabitants and of , we denote if lives next door to . This relation is not reflexive, as a single inhabitant cannot live next door to himself (actually, we should give a counter-example).
2. In the same set , we denote if they live in a flat with the same number of rooms. This is a reflexive relation.

Definition 4.2.4   A relation on the set is symmetric if

Example 4.2.5   Take and let be the binary relation on determined by the diagram in Figure 4.

This relation is symmetric.

Note that the relation in this example is not reflexive, as the element is not related to itself (in the diagram, there is no point at ).

Example 4.2.6
1. Let be the set of students of an institution. If and are two students in , we write when and come from the same town. The relation is symmetric: for any two students and , saying that  and come from the same town'' is equivalent (thus implies) saying that  and come from the same town''.
2. Let be the set of children in a kindergarden. For two children and , we write if is the sister of . Being symmetric or not depends on the set itself. If is the sister of and is a boy, then .

Definition 4.2.7   A relation on the set is transitive if

Example 4.2.8
1. The binary relation of Example 2.5 is not transitive. There we have: and , but .
2. Let be the set of all the students in a class. We define the relation on as follows: if and are two students in , we write if and have the same eye color. This relation is transitive: suppose that , and are any three students in such that and have the same eye color and and have the same eye color; then and have the same eye color.

Note that transitivity is not an immediate constatation from a cartesian diagram; it is more easily seen on an arrow diagram (how?).

Definition 4.2.9   A relation on the set is antisymmetric if

Example 4.2.10   Let be the set of all positive integers. We define the binary relation by:

In other words if, and only if, is a multiple of . For instance, and , but . The relation is transitive. Let , and be three positive integers such that and , i.e.

 and

It follows that , and is an integer. Whence the result.

We will discover later the great importance of this relation in Mathematics.

Next: Equivalence relations Up: Binary relations Previous: The general case   Contents
root 2002-06-10