232 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7
ordered pair contained in the relation. Using this approach, we might refer
to R,, as the subset relation on the set A. We might agree to name this
relation by the symbol c and write M c N instead of (M, N) E R,, to
symbolize that the sets M and N are related by the relation. R13 is usually
called the relation congruence modulo 5 on 2, and we customarily write
13 r 18 mod 5, rather than (13, 18) E R, ,. More generally, we often deal
with a generic relation R by using the notation x y, rather than (x, y) E R.
Also, it is common to identify a generic relation by some symbol, such as
--, rather than by a letter, so that x - y means the same thing as (x, y) E R.
The relation "equality" on any set X (as in R14) can be described by either
the symbol = or by the notation I, = ((x, x)lx E XI. This relation is often
referred to as the identity relation on X.
We next consider four properties that a given relation may, or may fail
to, possess. These properties are fundamental to the definitions of equiva-
lence relation and partial ordering, as we will see in Articles 7.2 and 7.4.
DEFINITION 3
Let A be a set and R a relation on A. We say that:
(a) R is reflexive on A if and only if x R x for all XE A [in symbols,
(Vx E A)( (x, X) E R)1.
(b) R is symmetric if and only if, for every x, y E A, if x R y, then y R x [in symbols,
(QXEA)(QYEA)((X, y) E R + (y, x)~R)l.
(c) R is transitive if and only if, for every x, y, and z in A, if x R y and y R z, then
x R z.
(d) R is antisymmetric if and only if, for every x, y, E A, if x R y and y R x, thenFrom the point of view of a relation R as a set of ordered pairs, the re-
flexive property means that R contains all pairs (x, x) where x ranges over
all the elements of A. Dynamically, the reflexive property means "every
element of A is related to itself." Symmetry means that whenever we "flip
over" an ordered pair in R, the resulting ordered pair is also in R. On the
other hand, antisymmetry says that the ordered pair (y, x) we get from flip-
ping over an ordered pair (x, y) in R is never in R, unless x = y. Finally,
transitivity may be regarded as a property by which ordered pairs in a rela-
tion are "linked together*' to form new ordered pairs in the relation. We
will occasionally refer to these properties as R, S, T, and AS, and to their
negations as NR, NS, NT, and NAS.EXAMPLE 7 Consider the relation less than on R; that is, a pair (x, y) is
an element of this relation if and only if x < y. This relation is not re-
flexive since, for instance, it is false that 5 < 5. It is not symmetric since,
for example, 8 < 9, whereas it is not the case that 9 < 8. The relation
clearly is transitive since if x < y and y < z, then x < z for any real