Relations on Sets

In Chapter Ten we discuss the mathematics of relations defined on sets, focusing on ways to represent relations and exploring various properties they may have. In Section 10.2 the reflexivity, symmetry, and transitivity properties of binary relations are introduced and explored. In Section 10.3 the concept of an equivalence relation is introduced. In Section 10.5 we will discuss partial order relations and an application showing how to use these relations to help coordinate and guide the flow of individual tasks that must be performed to accomplish a complex, large-scale project.

Let’s begin by introducing some concepts and notation. Once we learn the definitions the challenge is to simply think things through to apply them in any given instance.

Example 10.1.1 Let A = {0, 1, 2} and B ={1, 2, 3}. Let us say that an element x in A is related to an element y in B if, and only if, x is less than y. Let us use the notation x R y as a shorthand for the sentence "x is related to y." Then

0 R 1 since 0 < 1, 0 R 2 since 0 < 2, 0 R 3 since 0 < 3,
1 R 2 since 1 < 2,1 R 3 since 1 < 3,
and 2 R 3 since 2 < 3.

Now consider the Cartesian product A X B whose elements are related, we have

(x, y) Î A X B | (x, y) Î R Û x < y.
A X B= {(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)},
R = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}.

Definition: Let A and B be sets. A (binary) relation R from A to B is a subset of A X B. Given an ordered pair (x, y) in A X B, x is related to y by R, written x R y, if, and only if, (x, y) is in R.

So we can think of the relation itself as a totality of ordered pairs whose elements are related by the given condition.

Example 10.1.2 The Congruence Modulo 2 Relation
Define a binary relation E from Z to Z as follows:

" (m, n) Î Z X Z, m E n Û m – n is even.
  1. Is 4 E 0? Is 2 E 6? Is 3 E (-3)? Is 5 E 2?
  2. List five integers that are related by E to 1.
  3. Prove that if n is any odd integer, then n E 1.
  1. Yes, 4 – 0 = 4. Yes, 2 – 6 = -4. Yes, 3 – (-3) = 6. No, 5 – 2 = 3, not an even number.
  2. Any 5 odd numbers will suffice.
  3. Proof: Suppose n is any odd integer. Then n = 2k + 1 for some integer k. Now by definition of E, n E 1 iff, n – 1 is even. By substitution,
n – 1 = (2k + 1) – 1 = 2k. \\

Example 10.1.3 The Circle Relation
Define a binary relation C from R to R as follows:

" (x, y) Î R X R, x C y Û x2 + y2 = 1.
  1. Is (1, 0) Î C? Is (0, 0) Î C? Is (-1, 0) Î C? Is (1, 1) Î C?
  2. Draw a graph for C by plotting the points of C in the Cartesian plane.
Arrow Diagram of a Relation
Suppose R is a relation from a set A to a set B. The arrow diagram for R is obtained as follows:
  1. Represent the elements of A as points in one region and the elements of B as points in another region.
  2. For each x in A and y in B, draw an arrow from x to y iff, x is related to y by R. Symbolically:
Draw an arrow from x to y Û x R y Û (x, y) Î R.

Example 10.1.5 Arrow Diagrams of Relations
Let A = {1, 2, 3} and B = {1, 3, 5} and define relations S and T from A to B as follows:

" (x, y) Î A X B, (x, y) Î S Û x < y,
T = {(2, 1), (2, 5)}.

As we saw in Example 10.1.1, binary relations are subsets of Cartesian products. We can extend this notion to define algebraic binary relations and consequently functions using set theory.

Definition: A function F from a set A to a set B is a relation from A to B that satisfies the following two properties:

  1. " x Î A $ y Î B | (x, y) Î F.
  2. " x Î A and y, z Î B if (x, y) Î F and (x, z) Î F then y = z.
If F is a function from A to B, we write
y = F(x) Û (x, y) Î F.

Note: y = F(x) iff y is the second element of an ordered pair in F whose first element is x. A less formal statement: A binary relation F from A to B is a function iff:

  1. every element of A is the first element of an ordered pair of F
  2. no two distinct ordered pairs in F have the same first element.
Are the relations S, T, or C from examples 10.1.3, 5 functions? Explain.

The Inverse of a Relation
If R is a relation from A to B, then a relation R-1 (read R inverse) from B to A can be defined by interchanging the elements of all the ordered pairs of R.

Example 10.1.8 The Inverse of a Finite Relation
Consider A = {2, 3, 4} and B = {2, 6, 8} and let R be the "divides" relation from A to B. State explicitly which ordered pairs are in R and R-1, and draw arrow diagrams for R and R-1. R = {(2, 2), (2, 6), (2, 8), (3, 6), (4, 8)}. Clearly R is not a function as there are distinct ordered pairs in R that have the same first element. Is R-1 a function?

Directed Graph of a Relation
When a binary relation R is defined on a set A, the arrow diagram of the relation can be modified so that it becomes a directed graph.
Example 10.1.10 Directed Graph of a Relation
Let A = {3, 4, 5, 6, 7, 8} and define a binary relation R on A as follows:

" x, y Î A, x R y Û 2|(x – y).