M122 Class Discussion Notes Chapter 8 Relations

Section 8.1 Relations and Their Properties

Section 8.3 Representing Relations

Section 8.4 Closures of Relations (Not covered this year)

Section 8.5  Equivalence Relations

.

Section 8.1 Relations and Their Properties

• Definition: A (binary) relation from set A to set B is a subset of the Cartesian product A X B.

• Relations are important in the theory of database management as seen by Example 1 and 2 page 375

• See also Example 3.

• Functions as Relations: Note that functions are a special kind of relation, but not every relation is a function. Relations are more general than functions since they can be used to represent one-to-many relationships.

• Relations on a Set. A relation on A is a relation from set A to set A (i.e. a subset of the Cartesian product A X A).

• See Example 4 and related figure 2, page 376

Properties of Relations

• A relation R on set A is:

• Reflexive: if (a,a) is an element of R for every element in A
• Symmetric: if whenever (a,b) is an element of R, then (b,a) is also an element of R
• Antisymmetric: both (a,b) and (b,a) are in R only when a = b.
• Transitive: if whenever (a,b) and (b,c) are in R, then (a,c) is also in R.

 Example:  Relationship "Divides" on the set of positive integers.

• Reflexive:  Yes   -- every positive integers divides itself
• Symmetric:  No  -- since   3 divides 6, but 6 does not divide 3
• Transitive:  Yes -- since if a divides b and b divides c, then a also divides c

( since if a = nb and b = mc  then a = n(mc) = (nm)c

• Antisymmetric:  Yes  -- if a divides b and b divides a, then a = b.   Proof:
• if a = nb and b = ma  then a = (nm)a.  Thus nm = 1, where n and m are postive integers. This can only be true if n = m = 1.  Thus a = nb = 1b = b.

Combining Relations

• Two relations from A to B can be combined with any set operations – for example union, intersection, difference.

• Example 18: A = students. B = courses.
• R1 = set of all pairs (a,b) such that student a has taken course b.
• R2 = set of all ordered pairs (a,b) where a is a student who requires course b to graduate.
• Interpret union, intersection, exclusive or, differences.
• Composite relations: Let R be a relation from A to B and S a relation from B to C.

Composite of R and S is the relation consisting of all ordered pairs (a,c) where both (a,b) is in R and (b,c) is in S.

• See Example 19.

• Powers of a relation are the composites R² = R composed with R; …. R ⁿ⁺¹ = R composed with Rⁿ

Section 8.3 Representing Relations

Representing Relations with Matrices

• A relation R between finite sets A = {a₁, a₂, …a_m| and B = {b₁, b₂, b₃, …, b_n} can be represented by an m X n zero-one matrix, M_R = { m_ij }, where m_ij = 0 if (a_i, a_j) is an element of R.
• See Examples 1 and 2.

• If R is a relation on A, then M_R is a square matrix.
• Inspection of the matrix allows one to determine whether the relation is

a) symmetric: if the matrix is symmetric.

b) antisymmetric : if i is not equal to j and if a_ij = 0, a_ji must equal 1.

c) reflexive: if a_ii = 1 (i.e. all 1's on the main diagonal).

d) transitive: whenever a_ii = 1 and a_jk = 1, then a_ik = 1.

Representing Relations using Digraphs (directed graphs).

• A directed graph can be used to represent a relation R on a finite set A. Each element of A is a vertex in the graph. An edge exists from a_ito a_j is (a_i,a_j) is an element of R.

• Inspection of the graph allows one to determine whether the relation is

a) symmetric: if there is an edge from a_i to a_j there is an edge from a_j to a_i.

b) antisymmetric : if i is not equal to j and if there is an edge from a_i to a_j there is not an edge from a_j to a_i.

c) reflexive: if every vertex has a loop.

d) transitive: if there is an edge from a to b and an edge from b to c, then there is an edge from a to c. Another way of expressing is that if there is a path form a to c then there is an edge from a to c.

Section 8.4 Closures of Relations

• Reflexive Closure of a Relation R on A :

The smallest relation that contains R and is reflexive, which is R È {(a,a) | a Î A }

• See Example 1

• Symmetric closure of the relation R is the smallest relation that contains R and is symmetric, which is R È R^-1 where R^-1 = { (b,a) | (a,b) Î R}

• See Example 2

Transitive Closures of Relations

• The transtitive closure of a relation R on a set A is the smallest relation that contains R and is transitive. It will be the connectivity relation R* defined as the set of all pairs (a,b) such that there is a path form a to b in R.
•  Many applications of transitive closures: See Examples 4, 5, 6
• Warshall's Algorithm provides a method for finding the transitive closure of a relation R.

Section 8.5 Equivalence Relations

• Definition: A relation is an equivalence relation if it is reflexive, symmetric, and transitive.
• See Examples 1, 2, 3, 4 for examples of equivalence relations.

Equivalence Classes

• Definition: Let R be an equivalence relation on A and a an element of A. The equivalence class of a, denoted by [a]_R is the set of all elements that are related to a. Any element in the equivalence class is called a representative of the equivalence class.

• Examples 5 and 6 determine the equivalence classes for examples 2, and 4.

Equivalence Classes and Partitions

• An equivalence relation R on A divides A into a set of disjoint equivalence classes whose union is all of A. In other words, the set of equivalence classes for the relation R forms a partition of A.
•  See Example 8