Discrete Mathematics for Computer Science

168 CHAPTER 3 Relations

3.4.1 Reflexive and Irreflexive Relations

Clearly, 3 < 3 is true, but 3 < 3 is not true. This distinction between < and < is captured

in the next definition.

Definition 1. Let R be a binary relation on a set X. R is reflexive if (x, x) E R for each

x E X.

It is obvious from the definition of reflexive that IdM, the equality relation on the real

numbers R, and LeR, the less than or equal relation on R, are reflexive. It is also obvious

that LtR, the less than relation on R, is not reflexive since there is no element x E R for

which (x, x) E LtR. That is, x < x is never true since no number can be strictly less than

itself.

The relation IsSameGeneration defined in Section 3.1 is reflexive since each person

is in the same generation as themselves.

Theorem 1. A binary relation R on a set X is reflexive if and only if Idx C R.

A picture of IdR is shown in Figure 3.3. The points (x, y) of the plane that represent

elements of IdR are darkened. The picture is just the familiar graph of the line x = y.

y

(0,0)

Figure 3.3 Graph of IdR.

In general, for a binary relation R defined on the real numbers IR, one can draw a

picture of the relation by darkening the point (x, y) in the plane if the ordered pair of real

numbers (x, y) is in R. Such a picture is called the graph of the relation R. Sometimes,

relations have graphs that consist of a single line, but in general, graphs of relations consist

of entire regions of points.

The usual convention in graphing LeR is to draw the diagonal line x = y as a darker,

heavier line to show that the line is included in the graph. One can see that LeR is reflexive

from its graph since the graph of the line x = y is a subset of the graph of LeR (see

Figure 3.4). Of course, making deductions from a graph is risky for essentially the same

reason that making deductions from a Venn diagram is risky.

Y

Figure 3.4

Graph of

LeR./(

°'