Composition of Relations in Discrete Mathematics: Combining Relations to Create New Relationships

Understand the composition of relations in discrete mathematics. This guide explains how to compose relations, the notation used for composition, provides examples illustrating the composition of relations, and explores the concept of composing a relation with itself.

Composition of Relations in Discrete Mathematics

Introduction to Composition of Relations

In discrete mathematics, a relation R is a set of ordered pairs that relates elements from one set to another. Given relations R (from set A to set B) and S (from set B to set C), we can define a new relation, called the composition of R and S, which relates elements from set A to set C. This new relation is denoted as R ◦ S (or sometimes just RS).

Definition of Relation Composition

The composition R ◦ S is defined as:

R ◦ S = {(a, c) | ∃b ∈ B such that (a, b) ∈ R and (b, c) ∈ S}

In simpler terms, (a, c) is in the composition R ◦ S if there's an element b in B such that (a, b) is in R, and (b, c) is in S. This means that you can get from 'a' to 'c' by going through 'b'.

Composition of a Relation with Itself

If R is a relation on a set A (meaning it relates elements within the same set), then the composition of R with itself (R ◦ R) is always defined. This is often written as R². Further compositions are denoted as R³, R⁴, and so on. In general, Rn is defined for any positive integer n.

Example 1: Composition of Relations

Let X = {4, 5, 6}, Y = {a, b, c}, Z = {l, m, n}. Given relations:

  • R₁ = {(4, a), (4, b), (5, c), (6, a), (6, c)}
  • R₂ = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find R₁ ◦ R₂ and R₁ ◦ R₁⁻¹.

(The solutions for R₁ ◦ R₂ and R₁ ◦ R₁⁻¹ should be shown here.)

Composition of Relations Using Matrices

Relation composition can also be computed using matrix representation. If MR and MS are the matrices representing relations R and S, respectively, then the matrix representing R ◦ S is given by the matrix product MRMS.

Example 2: Composition Using Matrices

Let P = {2, 3, 4, 5}. Given relations:

  • R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
  • S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}

Find R ◦ S, R ◦ R, and S ◦ R.

(The solutions for R ◦ S, R ◦ R, and S ◦ R using matrix multiplication should be shown here. Images of the matrices would be highly beneficial for understanding this process.)

Conclusion

Composition of relations is a fundamental concept in discrete mathematics. It allows for combining relations to create new relations, providing a powerful tool for analyzing relationships between sets. Understanding relation composition is important in various areas, including database design and graph theory.