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 A be a set and let R be a binary relation on A, that is, a subset of A × A.
R is said to be reflexive if ∀a ∈ A (a R 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 ≤ 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, ∀b ∈ A, ∀c ∈ A ((a R b ∧ b R c) → (a R c)). Transit- ivity allows us to ‘chain together’ two true statements a R b and b R c, which are ‘linked’
by the b that occurs in each statement, to deduce that a R c. For example, suppose P is the set of people, and define the relation C on P such that xPy if and only if x 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 P such that x D y if and only if x is a descendent of y. Then D 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 ∈ A, ∀b ∈ B(aRb → bRa). That is, whenever a is related to b, it follows that b is related to a. The relation “is a first cousin of” on the set of people is symmetric, since whenever x is a first cousin of y, we have automatically that y 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 n ≤ m, we cannot conclude that m ≤ n. It is true for some n and m in N that n ≤ m → m ≤ n, but it is not true for all n and m in N.
Finally,R is antisymmetric if ∀a∈A,∀b∈B (aRb∧bRa)→a=b .The relation R is antisymmetric if for any two distinct elements x and y of A, we can’t have both x R yand y R x. The relation ≤ on N is antisymmetric because from the facts that n ≤ m and m ≤ n, we can deduce that n = m. The relation ‘child of’ on the set of people is antisymmetric since it’s impossible to have both that x is a child of y and y 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 A is a binary relation on A that is reflexive, antisymmetric, and transitive.
Another example of a partial order is the subset relation, ⊆, on the power set of any set. If X 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 A and B of P(X) are related by ⊆ if and only if A ⊆ 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 n and m are natural numbers, then at least one of the statements n ≤ m and m ≤ n must be true. However, if A and B are subsets of a set X, it is certainly possible that both A ⊆ B and B ⊆ A are false. A binary relation R on a set A is said to be a total order if it is a partial order and furthermore for any two elements a and b 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 L be the set of strings that can be made from lowercase letters. L contains both English words and nonsense strings such as “sxjja”. There is a commonly used total order on the set L, namely alphabetical order.