Discrete Mathematics for Computer Science

Operations on Binary Relations 163

For three distinct positions on the board, define the relation Between to consist of the or-

dered triples (pj, Pi, Pk) where pj is between pi and Pk in some row, column, or diag-

onal on the board. So, Between contains, for example, the ordered triples (P2, P3, P0),

(P5, P4, P6), (p5, pi, p9), and (Ps, P7, P3). Both (P5, P2, P8) and (Ps, P8, P2) are also

elements of the relation. E

Example 5. We define a ternary relation R on the set A = {1, 2, 3,4, 5, 6, 7} as follows:

such that for any nI, n2, n3 E A we have (nI, n 2 , n 3 ) E R if and only if n 1 I n2 = n3.

Find all elements of R.

Solution. The triples in R are

((1, 1, 1), (1, 2, 2), (2, 1, 2), (1, 3, 3), (3, 1, 3), (1, 4, 4), (4, 1, 4), (2, 2, 4),

((1, 5, 5), (5, 1, 5), (1, 6, 6), (6, 1, 6), (2, 3, 6), (3, 2, 6), (1, 7, 7), (7, 1, 7)) U

A 1-ary relation is also called a unary relation (pronounced "u"-nary relation) or a

property. A unary relation on a set X is a set of 1-tuples of elements of X, but a 1-tuple of

X is just an element of X. Hence, a unary relation on a set X is a subset of X.

Example 6. Hearts names a unary relation on a deck of cards. This unary relation on the

standard 52-card deck is the set {2 of Hearts, 3 of Hearts ... , Ace of Hearts).

If R is an n-ary relation with n > 2, one can either write R(xl, x2. Xn) or

(Xl, X2, .., Xn) E R.

Theorem 1 points out that an n-ary relation on a set X is the same thing as a unary

relation on the set Xn.

Theorem 1. A set R is an n-ary relation on a set X if and only if R C Xn.

rnOperations on Binary Relations

Since relations are sets, the set operations of union, intersection, and difference are well

defined for relations. If only binary relations on a set X are considered, then X^2 can be

considered as the universal relation, and the complement X^2 - R of a relation R can also

be formed. In this section, two other especially important operations on binary relations

are considered, namely forming the inverse and taking the composition of two relations.

The inverse operation is performed on a single binary relation; the composition operation

is performed on two binary relations.

3.2.1 Inverses

For the real numbers 3 and 5, we can write 3 < 5, but we can convey the same information

by writing 5 > 3. The two relations, < and >, are different. More generally, for any real

numbers x and y, we have x < y if and only if y > x. This is an example of two relations

being inverses of each other. In terms of the ordered pair notation,