Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
18.4. Composition of Relations
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we're exploring how we can treat relations as sets! Can anyone tell me what set operations we know?
Union and intersection!
Exactly! Let's consider two relations R1 and R2 where R1 contains pairs (x, y) such that x < y, and R2 contains (x, y) such that x > y. What do you think happens if we take the union of these two relations?
It would include all pairs where x is not equal to y.
Correct! So, the union has all (x, y) pairs where x is different from y. What about the intersection? What do you think we would get?
An empty set, because x can't be both less than and greater than y at the same time.
Well done! The intersection indeed results in an empty set. Let's summarize: The union brings together different pairs while the intersection shows us when neither holds.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now, let’s shift gears and talk about composition of relations. If R is a relation from A to B and S from B to C, can anyone explain how we would write the composition?
It would be written as S o R, right? We apply R first and then S!
Exactly! This gives the ordered pairs of the form (a, c). If a is related to b in R and b is related to c in S, then a is related to c in S o R. Why do you think this order is important?
Because if we did R o S, it would mean something different!
Absolutely! Order is critical in relations. So remember, S o R is different from R o S. Let's wrap this up: composition allows us to connect relations across sets!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Next, let’s discuss the powers of relations. If I have a relation R, what do we mean by R squared or R cubed?
R squared would be the composition of R with itself.
Right! And it follows recursively. Can anyone define R to the power of n?
It’s the composition of R with itself n times?
Exactly! Remember though, the order matters. R squared is not the same as squaring R and it might not be equal to R o R. Can someone think of a scenario where this would matter?
If the relations are not commutative! Like multiplication.
Great analogy! Non-commutativity makes a significant difference in the results.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now let’s visualize relations. How does representing relations on directed graphs help us understand them better?
We can see the connections between elements more clearly!
Exactly! If we have a directed path of length m between nodes, it relates to powers of the relation. How so?
If there's a directed path from a to a of length m, it shows that the ordered pair (a, a) is present in that power.
Right! Visualizing these relations helps in grasping the concept of paths and powers better. In summary, graphical representations offer crucial insights into our relations!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Lastly, let’s talk about closure of relations. What does it mean when we say closure under certain properties like reflexivity?
It's about expanding the relation to satisfy that property, right?
Good point! If relation R isn’t reflexive, we’ll add pairs of the form (a, a) for each a in set A. What about symmetry?
We check if (a, b) exists, then we should add (b, a) if it's not there.
Exactly! To ensure symmetry, we take the union of R and its inverse. So to conclude, closures help us adjust relations to meet specific properties.
Overview
Short Summary
This section discusses important operations on relations including set operations (union, intersection, difference) and introduces the concepts of composition of relations and their powers.
Medium Summary
In this section, we explore operations that can be performed on relations, such as union, intersection, difference, and the composition of relations. We also define the powers of a relation and understand these concepts through examples, demonstrating their significance in relational mathematics.
Detailed Summary
Composition of Relations
In the study of discrete mathematics, particularly in relation to set theory, understanding relations is crucial. This section delves into the operations one can perform on relations, some of which include:
1. Set Operations on Relations:
Relations can be treated as sets, enabling the use of set theoretic operations:
- Union: If two relations, R1 and R2, are defined where R1 includes all (x, y) such that x < y and R2 includes all (x, y) such that x > y, their union contains all pairs (x, y) where x is not equal to y.
- Intersection: The intersection of R1 and R2 results in an empty set since there cannot be real numbers where one is less than and greater than the other simultaneously.
- Difference: The difference R1 - R2 results in the relation R1 itself while R2 - R1 yields R2.
2. Composition of Relations:
The section introduces the concept of composing relations, denoted by S o R, where R is a relation from set A to set B, and S from B to C. Composition is performed by connecting related elements from each set:
- If a is related to b in R and b is related to c in S, then a is related to c in the composition S o R.
3. Powers of Relations:
Powers of a relation are defined recursively. R1 is R itself, and R(n+1) is the composition of R(n) with R. The order of composition matters, as it does not imply commutativity.
4. Graphical Interpretation:
Directed graphs represent relations, where nodes signify elements and directed edges indicate the relationships. The presence of a directed path of length m between two nodes corresponds directly to the powers of relations.
5. Closure of Relations:
Further explained is the concept of closure involving certain properties like reflexivity, symmetry, and transitivity, with examples demonstrating the construction of various types of closures.
Overall, this section is pivotal for understanding more complex concepts in mathematics related to relations and their operations. The examples provided lay a foundational understanding that will be built upon in subsequent sections.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountNow, we can perform another interesting operation on the relations which is called as composition of relations. So, imagine you are given two relations R and S, the relation R is from the set A to B. So, R is a subset of A x B. And your relation S is from the set B to C, so S is a subset of B x C, I am taking here three arbitrary sets A, B, C; A, B, C may be same, they may be different there is no relationship, they are just arbitrary sets here.
Detailed Explanation
In this section, we explore the concept of composing two relations, R and S. Here, R connects elements from set A to set B, while S connects elements from set B to set C. When we talk about the composition of these two relations (denoted as S o R), we are defining a new relation that connects A directly to C through the intermediary set B. This means we are looking for pairs where an element in A is related to an element in B via R and that B is related to an element in C via S.
Examples & Analogies
Think of it like a delivery service. If Company A (set A) delivers packages to a distribution center (set B) and Company B (set B) then delivers those packages from the center to customers (set C), the composition of these services (S o R) represents the entire delivery process from Company A directly to the customers.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountAnd I am numbering the naming the elements of this set A as a to a. Similarly, the elements of B are named as b to b and elements of C are named as c to c. Now the composition of these two relations is defined as follows. So, first of all we use this notation S o R, and this means that I am going to apply the relation R first and then the relation S.
Detailed Explanation
In defining the composition of relations, we specifically denote it as S o R. This indicates the order in which the relations are applied: we first use relation R to connect elements in set A to those in set B, and then we apply relation S to connect these elements in B to corresponding elements in set C. The order matters significantly here—S o R is not the same as R o S because the operations are dependent on the sequence in which the relations are applied.
Examples & Analogies
Consider a relay race. If Runner A (from set A) passes the baton to Runner B (in set B), and then Runner B passes it on to Runner C (in set C), the sequence of passing is crucial. If Runner A handed off to Runner C directly without involving Runner B, it would disrupt the race's order.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountSo, this will be a relation from the set A to C and that is why these ordering matters are lots. If I am saying S composed with R, so this operation o is called as the composition operator here and right now, I am composing the relation S with the relation R.
Detailed Explanation
The composition S o R results in a relation that connects elements from set A to set C. This new relation includes ordered pairs (a, c), indicating that if an element a is related to b by the relation R, and b is related to c by the relation S, then a can be said to be related to c through the composition. This showcases how relationships can be 'transitive' through intermediate connections.
Examples & Analogies
Imagine a chain of friends. If Alice (a) knows Bob (b), and Bob knows Charlie (c), then through this friendship connection, we can say that Alice indirectly knows Charlie through Bob. Thus, Alice and Charlie are connected, illustrating the transitive nature of relationships.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountThis will be a relation from the set A to C. That means it will have ordered pairs of the form (a, c) and definition here is it will have all ordered pairs of the form (a, c) provided, you have some element b in the set B such that a is related to b as for the relation R and b is related to c as per the relation S.
Detailed Explanation
The composed relation S o R consists of all ordered pairs (a, c) where there exists an intermediary element b such that a is related to b via R, and b is related to c via S. This definition emphasizes the necessity of this intermediate step, visualizing the composition of relations as networks of connections rather than direct links.
Examples & Analogies
Think of a university education. A student (set A) gets accepted into a program (set B), and then graduates (set C). The relationship of the student being accepted to the program and then graduating connects the student directly to the outcome of graduation through the intermediary process of attending that program.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Union of Relations:
Combines all pairs from both relations.
- Intersection of Relations:
The common pairs from both relations, often resulting in an empty set for contrasting relations.
- Composition of Relations:
Connects two relations by chaining them together based on shared elements.
- Powers of Relations:
Recursive application of relations to establish transitive connections.
- Closure of Relations:
Adjusts relations to meet defined properties such as reflexivity, symmetry, or transitivity.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
Example of Union: If R1 consists of pairs (1,2) and (2,3) while R2 contains (2,1) and (3,2), the union R1 ∪ R2 would contain ((1,2), (2,3), (2,1), (3,2)).
Example of Composition: Consider relations R = {(1, 2), (2, 3)} and S = {(2, 4)}. The composition S o R would yield {(1, 4)}.
Memory aids
Once a pair went looking for friends. Together they formed alliances in a union that never ends.
Flash Cards
Glossary
Union of Relations
The combination of all ordered pairs from both relations.
Intersection of Relations
The set of ordered pairs common to both relations.
Difference of Relations
The ordered pairs in the first relation that are not in the second.
Composition of Relations
A relation derived from two relations where the elements of one relation connect with the elements of another.
Powers of a Relation
Repeated application of a relation; defined recursively.
Closure of a Relation
The smallest extension of a relation to satisfy a given property.
Reflexive Property
A relation where every element is related to itself.
Symmetric Property
A relation where if (a, b) exists, then (b, a) also exists.
Transitive Property
A relation where if (a, b) and (b, c) exist, then (a, c) must also exist.