 Combining relationsSince relations from A to B are subsets of , two relations from A to B can be combined in any way two sets can be combined.
Example. Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relations R_{1} = {(1, 1), (2, 2), (3, 3)} and R_{2} = {(1, 1), (1, 2), (1, 3), (1, 4)} can be combined to obtain , , .
There is another way that relations are combined which is analogous to the composition of functions.
Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs (a, c), where , and for which there exists an element such that and . We denote the composite of R and S by .
Example. What is the composite of the relations R and S where R is the relation from {1, 2, 3} to {1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}?
Solution: is constructed using all ordered pairs in R and ordered pairs in S, where the second element of the ordered pair in R agrees with the first element of the ordered pair in S. For example, the ordered pair (2, 3) in R and (3, 1) in S produce the ordered pair in S. For example, the ordered pair (2, 3) in R and (3, 1) in S produce the ordered pair (2, 1) in . Computing all the ordered pairs in the composite, we find .
The powers of a relation R can be inductively defined from the definition of a composite of two relations.
Let R be a relation on the set A. The powers R^{n}, n = 1, 2, 3, … are defined inductively by R^{1} = R and . The definition shows that , , and so on.
Example. Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers R^{n}, n = 2, 3, 4, …
Solution: Since , we find that Furthermore, since , Additional computation shows that R^{4} is the same as R^{3}, so It is also follows that for n = 5, 6, 7, …
Theorem 1. The relation R on a set A is transitive iff for n = 1, 2, 3, …
nary relations
Let A_{1}, A_{2}, …, A_{n} be sets. An nary relation on these sets is a subset of . The sets A_{1}, A_{2}, …, A_{n} are called the domains of the relation, and n is called its degree.
Example. Let R be the relation consisting of triples (a, b, c), where a, b and c are integers with a < b < c. Then , but . The degree of this relation is 3. Its domains are all equal to the set of integers.
Example. Let R be the relation consisting of 5tuples (A, N, S, D, T) representing airplane flights, where A is the airline, N is the flight number, S is the starting point, D is the destination, and T is the departure time. For instance, if Nadir Express Airplanes has flight 963 from Newark to Bangor at 15:00, then (Nadir, 963, Newark, Bangor, 15:00) belongs to R. The degree of this relation is 5, and its domains are the set of all airlines, the set of flight numbers, the set of cities, the set of cities (again), and the set of times.
Date: 20150102; view: 551
