Binary Relations

Relation, a mathematical concept, is a set of ordered pairs. (More precisely, the concept is called binary relation, but usually “binary” is omitted.) Relation is defined in a branch of mathematics called set theory, a vital branch underpinning all branches of mathematics and those fields that use mathematics. One interprets a relation as a relationship (in the quotidian parlance) from the first coordinate to the second coordinate of the ordered pair. Three particularly useful and pervasive types of relations are equivalence relations, (partial) orderings, and functions. These three are found in every branch of mathematics.

Introduction

Relation is an idea that predates its specific and restricted mathematical namesake. It seems likely that, when human beings began to think, relations were part of thought. The human mind, in its pursuit of the ancient and venerable discipline of philosophy, must have tried to create order out of its unknown world. Things were not just independent from each other. No, the mind, in its early labors, linked certain things with others because these things had some relation between them. Hence, fathers recognized their relationship to their sons; sons, their fathers. Husbands recognized their wives; wives, their husbands. Denizens dwelled in their villages; villages contained its denizens. These relations are fundamental relationships, but their formulation is vague. How can this fundamental, yet vague, concept be brought into the rigor of mathematics?

Set Theory Provides the Requisite Formalism

Because mathematicians are familiar with sets, set theory is a likely candidate for defining relation in mathematics. After choosing set as a candidate, one must try to distill the vague idea of relation into a mathematically useful concept. Consider the son to father relation. As an example, let the father be Isaac. Let the son be Jacob. One could form the (unordered) set {Jacob, Isaac}. Will this formulation do? One can try to interpret this set as Jacob is the son of Isaac. But, a problem immediately arises because the set {Isaac, Jacob} is equal to the set {Jacob, Isaac}. Hence, Isaac is the son of Jacob. Unfortunately, Isaac is the son of Abraham. Thus the (unordered) set will not suffice.

Clearly, the order of the elements matter. To preserve this order, one tries an ordered set, the ordered pair. The son to father relation can, then, be expressed by denoting the son as the first coordinate and the father as the second coordinate. (Jacob, Isaac) and (Isaac, Abraham) express the son to father relationship correctly. No confusion arises as to who is father and who is son. Hence, the ordered pair correctly shows the relationship of son to father. If one calls the set of sons, S, and the set of fathers, F, then Jacob is in S and Isaac is in F. Consequently, the ordered pair (Jacob, Isaac) is an element in S × F. Since every ordered pair of son to father is an element in S × F, the son to father relation is a subset of S × F. But, note well that, although Jacob is also an element in F and Isaac is also an element in S since both men had a father and at least one son, the ordered pair (Isaac, Jacob) is not in the subset of S × F that is the son to father relation. Hence, this son to father relation is a proper subset of S × F. (Although an arbitrary relation can be any subset of the Cartesian product including the empty or full set.)

The Definition of Relation

Let X and Y be sets. A relation, R, from X to Y is a subset of the Cartesian product X × Y. (Recall that elements of X × Y are called ordered pairs.) Let x be an element of X and y be an element of Y. The notations (x, y) is an element of R and x R y (say x is in relation R to y) are equivalent.

If X = Y, then R is called a relation on X and is, of course, a subset of X × X.

The domain of R, denoted by dom R, is the set of elements in the first component of every ordered pair in R. The range of R, denoted by ran R, is the set of elements in the second component of every ordered pair in R. Examples will elucidate.

Elementary Examples of Relation

Let X and Y be sets. The trivial relation is the empty set, which is, of course, a subset of every set including X × Y. (Note that every element of the empty set is an element of X × Y vacuously.) Because the empty set is a subset of every subset of X × Y, the trivial relation is a subset of every relation from X to Y. Also, the domain and range are both equal to the empty set.

The Cartesian product, X × Y, is also a relation. It is obviously the largest relation from X to Y since, by definition of relation, it contains every relation from X to Y. Also, the domain is X and the range is Y.

If X = Y, then the relation of equality is another example of a relation. Denote the relation of equality by I. Let x and y be in X. Define I as follows: x I y if x = y (in X). Consequently, every element in I is an ordered pair that has the same first and second component and every element in X forms such an ordered pair in I. In symbols, I = {(x, x) : for all x in X}. Here, dom I = ran I = X.

Subset membership is another relation. Let X be a set. Let P(X) be its power set. Define Ε, the subset membership relation from X to P(X), as x Ε A if x belongs to the subset A. Here, dom Ε = X; ran Ε = P(X) \ {ø} where ø is the empty subset of X. Note that the empty set is excluded from the range because there are no elements that have set membership in it.

The Algebra of Relations: Inverses and Composites

With the definition of a relation explicitly stated, one is able to not only construct examples, but also define an algebra (used vaguely, not as the mathematical concept in the branch of mathematics called algebra) on relations. To start, let R be a relation from X to Y. The inverse of R, denoted by R-1, is a relation from Y to X such that y R-1 x means that x R y. Thus one switches the order of the first and second coordinates of each ordered pair in R to obtain R-1.

One can also form the composites of relations. These are called relative products. Start with two relations: R from X to Y and S from Y to Z. Denote the relative product of R and S by RS. Define RS to be the relation from X to Z such that x RS z if and only if there exists a y in Y such that x R y and y S z. (Note that many mathematicians prefer to write the relative product above as SR, instead of RS.)

There are many properties of relative products and inverses. One of these is that relative products do not, in general, commute. In symbols, for a relation R from X to Y and S from Y to X, RS is not, in general, equal to SR. In particular, RS is a relation on X and SR is a relation on Y. If X is not equal to Y, then there is no chance of these relations being equal. What if X = Y? Consider this example. Let X be the set of human beings. Let x R y mean that x is married to y; let x S y mean that x is the child of y. What does a RS b mean? A moment’s reflection reveals that a is the son or daughter in law of b. What about a SR b? a is son, stepson, daughter, or stepdaughter of b. Hence, RS and SR are not equal.

However, (RS)-1 = S-1R-1 is valid. To show this, let (x, y) be in (RS)-1. Then (y, x) is in RS. Hence, there exists a z in ran R and in dom S such that (y, z) is in R and (z, x) is in S. Thus (x, z) is in S-1 and (z, y) is in R-1. Hence, (x, y) is in S-1R-1. Therefore, any, and hence every, element of (RS-1 lies in S-1R-1. What is shown above is easily seen to be reversible and, hence, any and every element of S-1R-1 also lies in (RS)-1. These last two results together imply that (RS)-1 = S-1R-1. Note that this result is sometimes called the commutativity rule for relative products and inverses.

The relative product is also associative. One wishes to show that R(ST) = (RS)T. Let (x, y) be in R(ST). Then there exists a u in ran R and dom (ST) such that (x, u) is in R and (u, y) is in ST. Then there exists a v in ran S and dom T such that (u, v) is in S and (v, y) is in T. Hence, (x, v) is in RS. And (x, y) is in (RS)T. Since these steps are reversible, R(ST) = (RS)T. Associativity, non-commutativity, and the commutativity rule for relative products and inverses should suffice as an introduction to the algebra of relations.

Elementary Types of Relations on X

Another interesting topic in the study of relation is the study of relation on a set X. In this case, both the domain and range of the relation are subsets of X. On these relations, mathematicians use a few adjectives to describe the different elementary types of relation on a given set. Three important ones, reflexive, symmetric, and transitive, will be defined and described. These require definitions. Start with a given set, X.

A relation, R, on X is reflexive if x R x for all x in X.

A relation, R, on X is symmetric if x R y implies that y R x.

A relation, R, on X is transitive if x R y and y R z imply that x R z.

A relation on X may have any combination of these three properties including none, as the following eight examples will demonstrate.

Examples of the Elementary Types of Relations on X

None. Let R be the son to father relation on the set of males, M. Since no one is also his father, s R s cannot exist for any s in M. Hence, R is not reflexive. If s R f exists, then s is the son of f. Clearly, f cannot be the son of s. Hence, R is not symmetric. If s R f and f R g, then s is the son of f and f is the son of g. But, s is not the son of g. s is the grandson of g. Hence, R is not transitive.

Reflexive only. Let W be the set of writers. Let R be the relation defined by x R y if x has read one of y’s work. Clearly every writer has read himself. Hence, R is reflexive. I have read Nietzsche, but Nietzsche has not read me. Hence, R is not symmetric. Nietzsche, however, did read Goethe, but I have not. Hence, R is not transitive.

Symmetric only. Let H be the set of human beings. Let R be the marriage relation. No one is married to himself. Hence, R is not reflexive. If Pierre is married to Marie, then Marie is married to Pierre. Hence, R is symmetric. However, even if Sarah is married to Abraham and Abraham is married to Hagar, Sarah and Hagar are not married. (Note the society that Sarah, Abraham, and Hagar lived in was polygamous.) Hence, R is not transitive.

Transitive only. A common and useful example of a transitive relation can be found in number theory. Let N be the set of natural numbers. Consider the strict less than relation (denoted of course by <) on N. Since n < n is not true, < is not reflexive. Also if n < m, then m < n is not true. Hence, < is not symmetric. However, if n < m and m < r, then n < r. Thus, < is transitive.

Reflexive and Symmetric only. Let X be a non-empty set. Let X1 and X2 be subsets of X such that X1 U
X2 = X and neither subset is contained in the other. Let a be an element in X1 ∩ X2 (in particular this intersection is non-empty). Define a relation, R, on X by x R y if x and y both lie in X1 or both lie in X2. If x and y do not lie in the same subset, then x R y (and y R x) is false. Since every element lies in X1 or X2 (or both), x R x is valid for every x in X. Thus, R is reflexive. If x R y, then x and y lie in the same subset. Hence, y R x is valid. Thus, R is symmetric. Now choose x to be in X1, but not in X2. Choose y to be in X2, but not in X1. x and y exist because neither subset contains the other. Note that x R a and a R y are valid, but x R y is not. Hence, R is not transitive.

Reflexive and Transitive only. Consider the natural numbers again with the less than or equal to relation denoted by ≤). Since n ≤ n for all natural numbers n, ≤ is reflexive. If n ≤ m and m ≤ r, then n ≤ r. Hence, ≤ is transitive. However, 1 ≤ 2, but 2 ≤ 1 is false. Hence, ≤ is not symmetric.

Symmetric and Transitive only. Consider again the natural numbers. Define a relation, R, on the natural numbers by n R m if both n and m are even. If n R m, then both n and m are even. Hence, m R n is valid too. Thus, R is symmetric. If n R m and m R r, then n, m, and r are all even. Hence, n R r is also valid. But, 3 R 3 is not valid; hence, R is not reflexive.

Reflexive, Symmetric, and Transitive. This case has a special name, equivalence relation. Because equivalence relations abound in mathematics, they deserve extra study. More details and examples can be found in a study of equivalence relation.

More amusing examples can be constructed to show that a general relation on X does not necessarily satisfy any combination of the reflexive, symmetric, or transitive properties. That such examples exist is important to remember.

Equivalence Relations, Orderings, and Functions

Amusing and edifying examples aside, the most useful types of relations are equivalence relations, orderings, and functions. The first two are two types of relation on a set; the last is a type of relation from one set to another. Among these, functions are ubiquitous in mathematics. And the others are very common. Consequently, these deserve extra study. More details of these three types of relation may be found in a study of them.

A Generalization

It is worthwhile to cursorily consider a generalization of binary relation. One can, after developing the natural numbers (a task that requires work), generalize the concept of binary relation to n-ary relation where n is any natural number. The reader can probably guess that the definition of, say, a 17-ary relation by comparison with and inference from the binary type is a set of ordered 17-tuples. A common example of an n-ary relation is a multi-variable function. Even though the theory of n-ary relations can be developed, it will be omitted in the present exposition.

Coda

(Binary) relation is subset of a Cartesian product of two sets and, hence, is a set of ordered pairs. The power invested in relation comes from two sources: the set structure of relation and its interpretation as a relationship (in the quotidian parlance) from an element in the first set to an element in the second set. Once relations are defined, much can be done with them. For example, one can consider their algebraic properties or consider their generalization to n coordinates. Familiar, useful, and used relations are equivalence relation, ordering, and function. No mathematician should be without these.