4.7.A Properties of relations

In many applications, attention is restricted to relations that satisfy some property or set of properties. (This is, of course, just what we do when we study functions.) We begin our discussion of binary relations by considering several important properties. In this discussion, let be a set and let R be a binary relation on A, that is, a subset of × A.

R is said to be reflexive if ∀∈ (a). That is, a binary relation on a set is reflexive 4 if every element of the set is related to itself. This is true, for example, for the relation≤onthesetN, since n ≤ for every n ∈ N. On the other hand, it is not true for the relation < on N, since, for example, the statement 17 < 17 is false.

R is called transitive if ∀∈ A, ∀∈ A, ∀∈ ((∧ c) → (c)). Transit- ivity allows us to ‘chain together’ two true statements and c, which are ‘linked’

by the that occurs in each statement, to deduce that c. For example, suppose is the set of people, and define the relation C on such that xPy if and only if is a child of y. The relation P is not transitive because the child of a child of a person is not a child of that person. Suppose, on the other hand, that we define a relation D on such that x if and only if is a descendent of y. Then is a transitive relation on the set of people, since a descendent of a descendent of a person is a descendent of that person. That is, from the facts that Elizabeth is a descendent of Victoria and Victoria is a descendent of James, we can deduce that Elizabeth is a descendent of James. In the mathematical world, the relations ≤ and < on the set N are both transitive.

R is said to be symmetric if ∀∈ A, ∀∈ B(aRb → bRa). That is, whenever is related to b, it follows that is related to a. The relation “is a first cousin of” on the set of people is symmetric, since whenever is a first cousin of y, we have automatically that is a first cousin of x. On the other hand, the “child of” relation is certainly not symmetric. The relation ≤ on N is not symmetric. From the fact that ≤ m, we cannot conclude that ≤ n. It is true for some and in N that ≤ → ≤ n, but it is not true for all n and in N.

Finally,R is antisymmetric if ∀aA,∀b(aRbbRa)→a=.The relation R is antisymmetric if for any two distinct elements and of A, we can’t have both yand x. The relation ≤ on N is antisymmetric because from the facts that ≤ and ≤ n, we can deduce that m. The relation ‘child of’ on the set of people is antisymmetric since it’s impossible to have both that is a child of and is a child of x.

During lectures, we’ll think about how to draw relations graphically. See the figure in Section 4.4.3 for one kind of graphical depiction.

There are a few combinations of properties that define particularly useful types of binary relations. The relation ≤ on the set N is reflexive, antisymmetric, and transitive. These properties define what is called a partial order: a partial order on a set is a binary relation on that is reflexive, antisymmetric, and transitive.

Another example of a partial order is the subset relation, ⊆, on the power set of any set. If is a set, then of course P(X) is a set in its own right, and ⊆ can be considered to be a binary relation on this set. Two elements and of P(X) are related by ⊆ if and only if ⊆ B. This relation is reflexive since every set is a subset of itself. The fact that it is antisymmetric follows from Theorem 4.1. The fact that it is transitive was Exercise 11 in Section 4.1.

The ordering imposed on N by ≤ has one important property that the ordering of subsets by ⊆ does not share. If and are natural numbers, then at least one of the statements ≤ and ≤ must be true. However, if and are subsets of a set X, it is certainly possible that both ⊆ and ⊆ are false. A binary relation R on a set is said to be a total order if it is a partial order and furthermore for any two elements and of A, either aRb or bRa. The relation ≤ on the set N is a total order. Therelation⊆on P(X) is not. (Note once again the slightly odd mathematical language: A total order is a kind of partial order—not, as you might expect, the opposite of a partial order.)

For another example of ordering, let be the set of strings that can be made from lowercase letters. contains both English words and nonsense strings such as “sxjja”. There is a commonly used total order on the set L, namely alphabetical order.