]>
Suppose that and are sets. A relation from to is a subset of the product set . As the name suggests, a relation from into is supposed to define a relationship between the elements of and the elements of , and so we usually use the more suggestive notation when . The domain of is the set of first coordinates and the range of is the set of second coordinates.
A relation from a set to itself is said to be a relation on .
Suppose that is a set and recall that denotes the power set of , the collection of all subsets of . The membership relation from to is perhaps the most important and basic relationship in mathematics. Indeed, for us, it's a primitive (undefined) relationship--given and , we assume that we understand the meaning of the statement .
Another basic primitive relation is the equality relation on a given set of objects . That is, given two objects and , we assume that we understand the meaning of the statement .
Other basic relations that you have seen are
Note that a function from into is a special type of relation. To compare the two types of notation (relation and function), note that means that .
Since a relation is just a set of ordered pairs, the set operations can be used to build new relations from existing ones. Specifically, if and are relations from to , then so are , , and . If is a relation from to and , then is a relation from to .
Suppose that and are relations from to . Note that
If is a relation on and is a subset of then is a relation on , called the restriction of to .
If is a relation from to , the inverse of is the relation from to defined by
Equivalently, . Note that any function from into has an inverse relation, but only when the is one-to-one is the inverse relation also a function.
Suppose that is a relation from to and that is a relation from to . The composition is the relation from to defined as follows: for and , if and only if there exists such that and . Note that the notation is inconsistent with the notation used for composition of functions, essentially because relations are read from left to right, while functions are read from right to left. Hopefully, the inconsistency will not cause confusion, since we will always use function notation for functions.
The important classes of relations that we will study in the next couple of sections are characterized by certain basic properties. Suppose that is a relation on .
Suppose that is a relation on . Show that is reflexive if and only if the equality relation on is a subset of .
Suppose that is a relation on . Show that is symmetric if and only if
Suppose that is a relation on . Show that is transitive if and only if .
Suppose that is a relation on . Show that is antisymmetric if and only if is a subset of the equality relation on .
Suppose that and are a relations on . For each property below, show that if both and have the property, then so does .
Suppose that is a relations on a set .
Suppose that is a relations on a set .
Let be the relation defined on by if and only if . Determine if has each of the following properties:
The relation in the previous exercise is a member of an important class of equivalence relations.