Relations

DefinitionRelation
Let A and B be sets. A binary relation from A into B is any subset of the Cartesian product A x B.

Example1:
nbsp;    Let's assume that a person owns three shirts and two pairs of slacks.
More precisely, let A = {blue shirt, mint green shirt} and B = {gray slacks, tan slacks}.
Then certainly A x B is the set of all possible combinations (six) of shirts and slacks that
nbsp;    the individual can wear. However, the individual may wish to restrict himself to
combinations which are color coordinated, or "related". This may not be all possible
pairs in A x B but will certainly be a subset of A x B. For example, one such subset
may be { (blue shirt, gray slack), (black shirt, tan slacks), (mint green shirt, tan slacks) }.

Example2:
Let A = {2, 3, 5, 6) and define a relation R from A into A by (a, b) R if and only if
a divides evenly into b.
So, R = {(2, 2), (3, 3), (5, 5), (6, 6), (2,6), (3, 6)}.

A typical element in R is an ordered pair (x, y). In some cases R can be described by
actually listing the pairs which are in R, as in the previous example. This may not be
convenient if R is relatively large. Other notations are used depending on the past practice.
Consider the following relation on real numbers.

R = { (x, y) | y is the square of x} and S = { (x, y) | x <= y}.

R could be more naturally expressed as R(x) = x2 . or R(x) =y where y = x2 .

Relation on a Set
A relation from a set A into itself is called a relation on A.

R and S of Example 2 above are relations on A = {2, 3, 5, 6}.
Let A be a set of people and let P = {(a, b) | a A ^ b A ^ a is a child of b } . Then P is a relation on A which we might call a parent-child relation.
Composition
Let R be a relation from a set A into set B, and S be a relation from set B into set C. The
composition of R and S, written as RS, is the set of pairs of the form(a, c) A x C, where
(a, c) RS if and only if there exists b B such that (a, b) Rand (b, c) S.
For example PP, where P is the parent-child relation given above, is the composition of P with itself and it is a relation which we know as grandparent-grandchild relation.

PropertiesOf Relations
Assume R is a relation on set A; in other words, R A x A. Let us write a R b to denote (a, b) R .

1.    Reflexive: R is reflexive if for every a A, a R a.

2.    Symmetric: R is symmetric if for every a and b in A, if aRb, then bRa.

3.    Transitive: R is transitive if for every a, b and c in A, if aRb and bRc, then aRc.

4.    Equivalence: R is an equivalence relation on A if R is reflexive, symmetric and transitive.

Click here for Review Excercises

Back to Study Schedule

Back to Table of Contents