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

           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) }.

                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.
                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